The complexity of theorem-proving procedures

DOI10.1145/3588287.3588297MaRDI QIDQ6979512zbMATH OpenFDO

Authors Stephen Cook

Publication date 25 May 2025

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

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Computer science (68-XX) Theory of computing (68Qxx)

Cites work

• A Computing Procedure for Quantification Theory
• An Efficient Algorithm for Graph Isomorphism
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• scientific article; zbMATH DE number 3222108 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• PREDICTABLY COMPUTABLE FUNCTIONALS AND DEFINITION BY RECURSION

Cited in

(9)

• On distance-d independent set problems for some graph classes
• The relative strength of \#SAT proof systems
• On the parameterized complexity of diverse SAT
• Understanding the thermodynamics of computation: a pedagogical overview
• A backtracking algorithm for solving the nearly equitable strong edge-coloring problem on transportation network
• Average case complexity theory
• On the parameterized complexity of diverse SAT
• Closure properties and characterizations of TotP
• The relative strength of \#SAT proof systems

This page was built for publication: The complexity of theorem-proving procedures

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