Проблемы передачи информации
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Пробл. передачи информ.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Проблемы передачи информации, 2023, том 59, выпуск 1, страницы 64–70
DOI: https://doi.org/10.31857/S0555292323010059 (Mi ppi2391) 		 
Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Большие системы

О проверке выполнимости алгебраических формул над полем из двух элементов

М. Н. Вялыйabc

a Федеральный исследовательский центр “Информатика и управление'' РАН, Москва
b Национальный исследовательский университет “Высшая школа экономики”, Москва
c Московский физико-технический институт (государственный университет), Москва
PDF полного текста (157 kB) Первая страница Список цитирования (1)
Список литературы:
PDF
HTML
DOI: https://doi.org/10.31857/S0555292323010059
Аннотация: Построен вероятностный полиномиальный алгоритм проверки выполнимости алгебраических формул глубины 3 над полем из двух элементов, верхней операцией в которых является сложение. Алгоритм с теми же характеристиками существует для проверки равенства нулю многочлена (задача PIT), задаваемого формулами указанного вида. Однако эти задачи и алгоритмы их решения существенно отличаются. Вероятностный алгоритм для задачи PIT основан на лемме Шварца – Зиппеля, а предложенный в этой статье алгоритм проверки выполнимости основан на лемме Вельянта – Вазирани.
Ключевые слова: выполнимость булевых формул, вероятностный алгоритм, алгебраические формулы.
Финансовая поддержка Номер гранта
Министерство науки и высшего образования Российской Федерации 0063-2019-0003
Программа фундаментальных исследований НИУ ВШЭ
Работа выполнена в рамках Программы фундаментальных исследований НИУ ВШЭ, а также частично финансировалась в рамках госзадания 0063-2019-0003.
Поступила в редакцию: 18.12.2022
После переработки: 12.02.2023
Принята к печати: 13.02.2023
Англоязычная версия:
Problems of Information Transmission, 2023, Volume 59, Issue 1, Pages 57–62
DOI: https://doi.org/10.1134/S0032946023010052
Реферативные базы данных:
Тип публикации: Статья
УДК: 621.391 : 519.16
Образец цитирования: М. Н. Вялый, “О проверке выполнимости алгебраических формул над полем из двух элементов”, Пробл. передачи информ., 59:1 (2023), 64–70; Problems Inform. Transmission, 59:1 (2023), 57–62
Цитирование в формате AMSBIB
\RBibitem{Vya23}
\by М.~Н.~Вялый
\paper О проверке выполнимости алгебраических формул над полем из двух элементов
\jour Пробл. передачи информ.
\yr 2023
\vol 59
\issue 1
\pages 64--70
\mathnet{http://mi.mathnet.ru/ppi2391}
\crossref{https://doi.org/10.31857/S0555292323010059}
\edn{https://elibrary.ru/RMKBBO}
\transl
\jour Problems Inform. Transmission
\yr 2023
\vol 59
\issue 1
\pages 57--62
\crossref{https://doi.org/10.1134/S0032946023010052}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/ppi2391
  • https://www.mathnet.ru/rus/ppi/v59/i1/p64
    • Эта публикация цитируется в следующих 1 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Проблемы передачи информации Problems of Information Transmission
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025