Proof Complexity Publications

Publications in Proof Complexity

Explore the most influential research papers and scholarly works that have shaped Proof Complexity. Use the concept filter below to focus on a specific sub-area of research.

Proof Complexity

3.3K

Publications

202K

Citations

Showing yearly statistics from 2000-2026.

Page 1

	Year	Citations
The complexity of theorem-proving procedures Stephen Cook EngineeringVerificationAutomated ProofComputational ComplexityRecognition Problem	1971	6.1K
Strips: A new approach to the application of theorem proving to problem solving Richard Fikes, Nils J. Nilsson Artificial Intelligence EngineeringAutomated ReasoningProof ComplexityFormal MethodsProof Assistant	1971	4K
The Knowledge Complexity of Interactive Proof Systems Shafi Goldwasser, Silvio Micali, Charles Rackoff SIAM Journal on Computing Theory Of ComputingComputational Complexity TheoryEngineeringAutomated ReasoningProof Complexity	1989	3.2K
A machine program for theorem-proving Martin Davis, George Logemann, Donald Loveland Communications of the ACM Mathematical ProgrammingEngineeringVerificationAutomated ProofSoftware Analysis	1962	3.1K
CONJECTURES AND REFUTATIONS Peter Alexander Philosophical Books Unknown WorldConjectures And RefutationsEngineeringRational ProcedureSocial Sciences	1963	2.9K
The complexity of satisfiability problems Thomas J. Schaefer Propositional FormulaEngineeringAutomated ReasoningSatisfiability ProblemsProof Complexity	1978	1.7K
Proof verification and the hardness of approximation problems Sanjeev Arora, Carsten Lund, Rajeev Motwani, Journal of the ACM Computational Complexity TheoryEngineeringMembership ProofsVerificationComputational Complexity	1998	1.4K
Probabilistic checking of proofs Sanjeev Arora Journal of the ACM Class NpEngineeringMembership ProofsVerificationInformation Forensics	1998	1.2K
A completeness theorem in modal logic Saul A. Kripke Journal of Symbolic Logic EngineeringSubstructural LogicAutomated ReasoningMulti-sorted LogicProof Complexity	1959	1.1K
The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory Tomás Feder, Moshe Y. Vardi SIAM Journal on Computing Mathematical ProgrammingComputational Complexity TheoryEngineeringComputational ComplexityComputational Structure	1998	1.1K
Analytic and Algorithmic Solution of Random Satisfiability Problems Marc Mézard, Giorgio Parisi, Riccardo Zecchina Science Mathematical ProgrammingEngineeringComputational ComplexityThreshold AlphacFormal Verification	2002	1K
Zero-knowledge proofs of identity Uriel Feige, Amos Fiat, Adi Shamir Journal of Cryptology EngineeringProof ComplexityVerificationData PrivacyProof Theory	1988	1K

Page 1