1975 · 166 citations · 4 references
HumanitiesComputer ScienceMathematicsLogicSet TheoryTheory Of ComputationDeductive ReasoningDeductive SystemsProof TheoryPropositional LogicTheorem ProvingConstructive Proof TheoryConstructive ProofsProof SystemsPropositional CalculusResolutions
The motivation for this work comes from two general sources. The first source is the basic open question in complexity theory of whether P equals NP (see [1] and [2]). Our approach is to try to show they are not equal, by trying to show that the set of tautologies is not in NP (of course its complement is in NP). This is equivalent to showing that no proof system (in the general sense defined in [3]) for the tautologies is “super” in the sense that there is a short proof for every tautology. Extended resolution is an example of a powerful proof system for tautologies that can simulate most standard proof systems (see [3]). The Main Theorem (5.5) in this paper describes the power of extended resolution in a way that may provide a handle for showing it is not super.
4
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
Stephen Cook · Journal of Symbolic Logic · 1970 · 387 citations
Existence and feasibility in arithmetic
Rohit Parikh · Journal of Symbolic Logic · 1971 · 331 citations