Testing the satisfiability of algebraic formulas over the field of two elements

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

We construct a probabilistic polynomial algorithm for testing the satisfiability of algebraic formulas of depth 3 over the two-element field, with addition as the top operation in the formulas. An algorithm with the same characteristics exists for the problem of testing whether a polynomial given by formulas of this type is identically zero (PIT problem). However, these problems and algorithms for their solution are essentially different. The probabilistic algorithm for the PIT problem is based on the Schwartz-Zippel lemma, whereas the satisfiability testing algorithm proposed in this paper is based on the Valiant-Vazirani lemma.

Авторлар туралы

M. Vyalyi

Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences;National Research University-Higher School of Economics;Moscow Institute of Physics and Technology (State University)

Email: vyalyi@gmail.com
Moscow, Russia

Әдебиет тізімі

  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
Жүктеу

© Russian Academy of Sciences, 2023