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)

zbMATH Keywords

probabilistic algorithmalgebraic formulassatisfiability 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

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)