On generic complexity of the validity problem for Boolean formulas

DOI10.17223/20710410/32/9MaRDI QIDQ5150742zbMATH OpenOpenAlexFDO

Authors Alexander Rybalov

Publication date 15 February 2021

Published in Prikladnaya diskretnaya matematika (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/pdm547

zbMATH Keywords

generic complexityvalidity problem for Boolean formulas

Mathematics Subject Classification ID

Boolean functions (06E30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• On generic NP-completeness of the Boolean satisfiability problem
• ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY
• Generic undecidability of universal theories
• On generic complexity of the discrete logarithm problem
• Generic complexity of the Diophantine problem

Cites work

• Average-case complexity and decision problems in group theory.
• Generic complexity of Presburger arithmetic
• Generic complexity of undecidable problems
• Generic-case complexity, decision problems in group theory, and random walks.
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• The complexity of theorem-proving procedures
• The halting problem is decidable on a set of asymptotic probability one

Cited in

(14)

• Generic hardness of the Boolean satisfiability problem
• Generic undecidability of universal theories
• Generic complexity of the Diophantine problem
• Musings on generic-case complexity
• ON GENERIC COMPLEXITY OF THE QUADRATIC RESIDUOSITY PROBLEM
• On generic complexity of the discrete logarithm problem
• On generic NP-completeness of the Boolean satisfiability problem
• ON GENERIC COMPLEXITY OF THE GRAPH CLUSTERING PROBLEM
• ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY
• On generic complexity of the existential theories
• The generic complexity of the graph triangulation problem
• Determination of the class of validity of logical formulas by directed exhaustive search
• Generic complexity of first-order theories
• Computational complexity of quantified Boolean formulas with fixed maximal deficiency

This page was built for publication: On generic complexity of the validity problem for Boolean formulas

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