ON GENERIC NP-COMPLETENESS OF THE BOOLEAN SATISFIABILITY PROBLEM

DOI10.17223/20710410/36/8zbMath1457.68117OpenAlexW2730915531MaRDI QIDQ5151063

Alexander N. Rybalov

Publication date: 16 February 2021

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

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

zbMATH Keywords

NP-completenessBoolean satisfiability problemgeneric complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of algorithms (68W01) Other nonclassical models of computation (68Q09) Computational aspects of satisfiability (68R07)

Related Items (2)

ON BINARY SOLUTIONS TO SYSTEMS OF EQUATIONS ⋮ ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY

Cites Work

• Unnamed Item
• Unnamed Item
• Average case completeness
• Generic-case complexity, decision problems in group theory, and random walks.
• Average Case Complete Problems
• ON GENERIC COMPLEXITY OF THE VALIDITY PROBLEM FOR BOOLEAN FORMULAS
• The complexity of theorem-proving procedures

This page was built for publication: ON GENERIC NP-COMPLETENESS OF THE BOOLEAN SATISFIABILITY PROBLEM