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

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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