nach oben

Problems of Information Transmission

Erschienen in:

01.01.2023 | LARGE SYSTEMS

Testing the Satisfiability of Algebraic Formulas over the Field of Two Elements

verfasst von: M. N. Vyalyi

Erschienen in: Problems of Information Transmission | Ausgabe 1/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel Overparameterized Maximum Likelihood Tests for Detection of Sparse Vectors

Nächster Artikel Batch Poissonian Arrival Models of Multiservice Network Traffic

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Agrawal, M., Proving Lower Bounds via Pseudo-random Generators, Proc. 25th Int. Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2005), Hyderabad, India, Dec. 15–18, 2005), Ramanujam, R. and Sen, S., Eds., Lect. Notes Comput. Sci., vol. 3821, Berlin: Springer, 2005, pp. 92–105. https://doi.org/10.1007/11590156_6

Saxena, N., Progress on Polynomial Identity Testing, Bull. Eur. Assoc. Theor. Comput. Sci., 2009, no. 90, pp. 49–79.

Saxena, N., Progress on Polynomial Identity Testing-II, Perspectives in Computational Complexity, Agrawal, M. and Arvind, V., Eds., Progr. Comput. Sci. Appl. Logic, vol. 26, Cham: Birkhäuser, 2014, pp. 131–146. https://doi.org/10.1007/978-3-319-05446-9_7

Gupta, A., Kamath, P., Kayal, N., and Saptharishi, R., Arithmetic Circuits: A Chasm at Depth 3, SIAM J. Comput., 2016, vol. 45, no. 3, pp. 1064–1079. https://doi.org/10.1137/140957123MathSciNetCrossRefMATH

Valiant, L.G. and Vazirani, V.V., NP Is as Easy as Detecting Unique Solutions, Theor. Comput. Sci., 1986, vol. 47, no. 1, pp. 85–93. https://doi.org/10.1016/0304-3975(86)90135-0MathSciNetCrossRefMATH

Hemaspaandra, L.A., Naik, A.V., Ogihara, M., and Selman, A.L., Computing Solutions Uniquely Collapses the Polynomial Hierarchy, SIAM J. Comput., 1996, vol. 25, no. 4, pp. 697–708. https://doi.org/10.1137/S0097539794268315MathSciNetCrossRefMATH

Dell, H., Kabanets, V., van Melkebeek, D., and Watanabe, O., Is Valiant–Vazirani’s Isolation Probability Improvable?, Comput. Complexity, 2013, vol. 22, no. 2, pp. 345–383. https://doi.org/10.1007/s00037-013-0059-7MathSciNetCrossRefMATH

Grenet, B., Koiran, P., Portier, N., and 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, Chakraborty, S. and Kumar, A., Eds., Leibniz Int. Proc. Inform. (LIPIcs), vol. 13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Germany: Dagstuhl Publ., 2011, pp. 127–139. https://doi.org/10.4230/LIPIcs.FSTTCS.2011.127

Arvind, V. and Guruswami, V., CNF Satisfiability in a Subspace and Related Problems, Algorithmica, 2022, vol. 84, no. 11, pp. 3276–3299. https://doi.org/10.1007/s00453-022-00958-4MathSciNetCrossRefMATH

10.

Leont’ev, V.K. and Moreno, O., On the Zeros of Boolean Polynomials, Zh. Vychisl. Mat. Mat. Fiz., 1998, vol. 38, no. 9, pp. 1608–1615 [Comput. Math. Math. Phys. (Engl. Transl.), 1998, vol. 38, no. 9, pp. 1542–1549]. https://www.mathnet.ru/eng/zvmmf1832MathSciNetMATH

Titel: Testing the Satisfiability of Algebraic Formulas over the Field of Two Elements
verfasst von: M. N. Vyalyi
Publikationsdatum: 01.01.2023
Verlag: Pleiades Publishing
Erschienen in: Problems of Information Transmission / Ausgabe 1/2023
Print ISSN: 0032-9460
Elektronische ISSN: 1608-3253
DOI: https://doi.org/10.1134/S0032946023010052

Neuer Inhalt

Bildnachweise

VDI-Icon, Profil Icon, inhalt2, Springer Professional Modul/© Springer Fachmedien Wiesbaden GmbH, Die Gewinner und Laudatoren des Sustainability Award in Automotive 2024/© Uli Regenscheit | ATZlive, Search Icon, Banner Hanser, Suresh Vittal/© Alteryx, Additiv gefertigte Teile/© Marina_Skoropadskaya | Getty Images | iStock, Warnschild "Land unter"/© Bluedesign / Fotolia, Zeitschrift Wissensmanagement Cover, PatentFit-Logo/© Springer Fachmedien Wiesbaden GmbH, ATZ-Webinar: Prototypenfreie Entwicklung durch Offline- und Driver-in-the-Loop-HiL-Tests /© (c) VI-grade, chassis.tech plus 2023/© [M] ATZlive / TÜV SÜD PRODUCT SERVICE GMBH, adäsion-Webinar-Matinee/© krystiannawrocki_ Getty Images

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2023

Overparameterized Maximum Likelihood Tests for Detection of Sparse Vectors

Design and Decoding of Polar Codes with Large Kernels: A Survey

Codes for Exact Support Recovery of Sparse Vectors from Inaccurate Linear Measurements and Their Decoding

Series of Formulas for Bhattacharyya Parameters in the Theory of Polar Codes

Batch Poissonian Arrival Models of Multiservice Network Traffic

Neuer Inhalt

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.