Generic hardness of the Boolean satisfiability problem

DOI10.1515/gcc-2017-0008zbMath1422.68095OpenAlexW2762633509MaRDI QIDQ1676251

Alexander N. Rybalov

Publication date: 6 November 2017

Published in: Groups, Complexity, Cryptology (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/gcc-2017-0008

zbMATH Keywords

probabilistic algorithmsBoolean satisfiability problemgeneric complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

The generic complexity of the bounded problem of graphs clustering ⋮ The generic complexity of the graph triangulation problem

Cites Work

• Generic-case complexity, decision problems in group theory, and random walks.
• The complexity of theorem-proving procedures
• Unnamed Item
• Unnamed Item

This page was built for publication: Generic hardness of the Boolean satisfiability problem