Journal of the ACM · 1987 · 451 citations · 10 references
ComputingComputer ScienceFormal MethodsLogicTheory Of ComputationAxiomatic Set TheoryFirst-order LogicPredicate LogicProof ComplexityPropositional LogicTheorem ProvingExpander GraphsLower Bounds For Proof SystemsLower Bounds For Resolution ProofsProof Complexity Of Propositional LogicProof Complexity Of Resolution RefutationsPropositional CalculusPropositional ReasoningResolutions
Exponential lower bounds are proved for the length-of-resolution refutations of sets of disjunctions constructed from expander graphs, using the method of Tseitin. Since these sets of clauses encode biconditionals, they have short (polynomial-length) refutations in a standard axiomatic formulation of propositional calculus.
10
Introduction to Mathematical Logic.
Angelo Margaris, Alonzo Church · American Mathematical Monthly · 1957 · 935 citations
The intractability of resolution
Armin Haken · Theoretical Computer Science · 1985 · 829 citations
The relative efficiency of propositional proof systems
Stephen Cook, Robert A. Reckhow · Journal of Symbolic Logic · 1979 · 827 citations