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

Обложка

Цитировать

Полный текст

Аннотация

Построен вероятностный полиномиальный алгоритм проверки выполнимости алгебраических формул глубины 3 над полем из двух элементов, верхней операцией в которых является сложение. Алгоритм с теми же характеристиками существует для проверки равенства нулю многочлена (задача PIT), задаваемого формулами указанного вида. Однако эти задачи и алгоритмы их решения существенно отличаются. Вероятностный алгоритм для задачи PIT основан на лемме Шварца - Зиппеля, а предложенный в этой статье алгоритм проверки выполнимости основан на лемме Вельянта - Вазирани.

Об авторах

Михаил Николаевич Вялый

Федеральный исследовательский центр “Информатика и управление” РАН;Национальный исследовательский университет Высшая школа экономики”;Московский физико-технический институт государственный университет)

Email: vyalyi@gmail.com
Москва, Россия

Список литературы

  1. Agrawal M. Proving Lower Bounds via Pseudo-random Generators // FSTTCS 2005: 1 Foundations of Software Technology and Theoretical Computer Science (Proc. 25th Int. Conf. Hyderabad, India. Dec. 15-18, 2005). Lect. Notes Comput. Sci. V. 3821. Berlin: Springer, 2005. P. 92-105. https://doi.org/10.1007/11590156_6
  2. Saxena N. Progress on Polynomial Identity Testing // Bull. Eur. Assoc. Theor.Comput. Sci. 2009. № 90. P. 49-79
  3. Saxena N. Progress on Polynomial Identity Testing-II // Perspectives in Computational Complexity. Progr.Comput. Sci. Appl. Logic. V. 26. Cham: Birkh ¨a user, 2014. P. 131-146. https://doi.org/10.1007/978-3-319-05446-9_7
  4. Gupta A., Kamath P., Kayal N., Saptharishi R. Arithmetic Circuits: A Chasm at Depth 3 // SIAM J.Comput. 2016. V. 45. № 3. P. 1064-1079. https://doi.org/10.1137/140957123
  5. Valiant L.G., Vazirani V.V. NP Is as Easy as Detecting Unique Solutions // Theor.Comput. Sci. 1986. V. 47. № 1. P. 85-93. https://doi.org/10.1016/0304-3975(86)90135-0
  6. Hemaspaandra L.A., Naik A.V., Ogihara M., Selman A.L.Computing Solutions Uniquely Collapses the Polynomial Hierarchy // SIAM J.Comput. 1996. V. 25. № 4. P. 697-708. https://doi.org/10.1137/S0097539794268315
  7. Dell H., Kabanets, V., van Melkebeek, D., Watanabe O. Is Valiant-Vazirani's Isolation Probability Improvable? // Comput.Complexity. 2013. V. 22. № 2. P. 345-383. https://doi.org/10.1007/s00037-013-0059-7
  8. Grenet B., Koiran P., Portier N., Strozecki Y. The Limited Power of Powering: Polynomial Identity Testing and a Depth-Four Lower Bound for the Permanent // Proc. 31st IARCS Annu. Conf. on Foundations of Software Technology and Theoretical Computer Science ( FSTTCS 2011). Mumbai, India. Dec. 12-14, 2011. Leibniz Int. Proc. Inform. (LIPIcs). V. 13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany: Dagstuhl Publ., 2011. P. 127-139. https://doi.org/10.4230/LIPIcs.FSTTCS.2011.127
  9. Arvind V., Guruswami V. CNF Satisfiability in a Subspace and Related Problems // Algorithmica. 2022. V. 84. № 11. P. 3276-3299. https://doi.org/10.1007/s00453-022-00958-4
  10. Леонтьев В.К., Морено О. О нулях булевых полиномов // Ж. вычисл. матем. и матем. физ. 1998. Т. 38. № 9. С. 1608-1615. https://www.mathnet.ru/rus/zvmmf1832

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2023

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).