1978 · 76 citations · 11 references
ComputingComputer ScienceMathematicsAlgorithmsSyntaxTheory Of ComputationAlgorithmic ComplexityComplexity TheoryComputational ComplexityPredicate LogicSyntactic ComplexityTime ComplexityComplexity Of SatisfiabilityPolynomial Time Complexity
We analyze the computational complexity of determining whether F is satisfiable when F is a formula of the classical predicate calculus which obeys certain syntactic restrictions. For example, for the monadic predicate calculus and the Gödel or ∃ ... ∃∀∀∃ ... ∃ prefix class we obtain lower and upper nondeterministic time bounds of the form cn/log n. The main tool in in these proofs is a finite version of Wang's domino problem, about which we present an interesting open question.
11
The complexity of theorem-proving procedures
Stephen Cook · 1971 · 6.2K citations · Full text
C. T. Bhunia · IETE Journal of Education · 1997 · 2.7K citations
The undecidability of the domino problem
Robert E. Berger · Memoirs of the American Mathematical Society · 1966 · 974 citations
Proving Theorems by Pattern Recognition - II
Hao Wang · Bell System Technical Journal · 1961 · 871 citations
Turing machines and the spectra of first-order formulas
Neil D. Jones, Alan L. Selman · Journal of Symbolic Logic · 1974 · 124 citations