On generic NP-completeness of the Boolean satisfiability problem

DOI10.17223/20710410/36/8MaRDI QIDQ5151063zbMATH OpenOpenAlexFDO

Authors Alexander 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, https://semanticscholar.org/paper/0e9c97072fb435b457b1a319caca1ebbb5da395d

zbMATH Keywords

Boolean satisfiability problemgeneric complexityNP-completeness

Mathematics Subject Classification ID

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

Recommendations

• ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY
• On generic complexity of the validity problem for Boolean formulas
• Generic hardness of the Boolean satisfiability problem
• Relativized generic classes P and NP
• Generic undecidability of universal theories

Cites work

• Average Case Complete Problems
• Average case completeness
• Generic-case complexity, decision problems in group theory, and random walks.
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• On generic complexity of the validity problem for Boolean formulas
• The complexity of theorem-proving procedures

Cited in

(11)

• Generic hardness of the Boolean satisfiability problem
• Generic undecidability of universal theories
• Generic complexity of the Diophantine problem
• NP-Completeness of (k-SAT,r-UNk-SAT) and (LSAT ≥ k ,r-UNLSAT ≥ k )
• scientific article; zbMATH DE number 2090049 (Why is no real title available?)
• The Complexity of Boolean Surjective General-Valued CSPs
• On generic complexity of the validity problem for Boolean formulas
• Relativized generic classes P and NP
• On binary solutions to systems of equations
• ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY
• The Complexity of Boolean Surjective General-Valued CSPs

This page was built for publication: On generic NP-completeness of the Boolean satisfiability problem

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