On the complexity of circuit satisfiability

DOI10.1145/1806689.1806724zbMath1293.68173OpenAlexW2090871895MaRDI QIDQ2875150

Ramamohan Paturi, Pavel Pudlák

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806724

zbMATH Keywords

NP-completenesscircuit satisfiability

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)

Related Items (7)

Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ On the Berlekamp/Massey algorithm and counting singular Hankel matrices over a finite field ⋮ Satisfiability Certificates Verifiable in Subexponential Time ⋮ Unnamed Item ⋮ On some FPT problems without polynomial Turing compressions ⋮ Does Looking Inside a Circuit Help

This page was built for publication: On the complexity of circuit satisfiability