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

DOI10.1134/S0032946023010052MaRDI QIDQ6137613zbMATH OpenFDO

Authors Mikhail Vyalyi

Publication date 4 September 2023

Published in Problems of Information Transmission (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/S0032946023010052

zbMATH Keywords

algebraic formulasprobabilistic algorithmsatisfiability of Boolean formulas

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Arithmetic circuits: a chasm at depth 3
• CNF satisfiability in a subspace and related problems
• Computing Solutions Uniquely Collapses the Polynomial Hierarchy
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Is Valiant-Vazirani's isolation probability improvable?
• NP is as easy as detecting unique solutions
• On the zeros of Boolean polynomials
• Progress on polynomial identity testing
• Progress on polynomial identity testing. II
• The limited power of powering: polynomial identity testing and a depth-four lower bound for the permanent

Cited in

(1)

• The length of an unsatisfiable subformula

This page was built for publication: Testing the satisfiability of algebraic formulas over the field of two elements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6137613)