Nonstandard propositional logics and their application to complexity theory.
Michael Evangelist · Notre Dame Journal of Formal Logic · 1982
Introduction and backgroundLet 2* be the set of all finite-length strings over some fixed alphabet 2. Then a language (over 2) is a set L Q 2*.Define P = \L\L is accepted by a deterministic Turing machine (DTM) in a polynomial number of steps \, where the argument to the polynomial function is the length of the input string.NP is the analogous family for nondeterministic Turing machines (NDTMs).The family P is widely considered to represent the class of feasibly solvable computational problems.Representative of this class, in a sense to be defined precisely, is the set S of satisfiable propositional formulas.Cook [3] has shown that S is a member of P if, and only if, P = NP.(The proof method is similar to that used by Buchi [ 1 ] for establishing the unsolvability of the decision problem for the predicate calculus.)Cook's result has far-reaching implications for the theory of computational complexity, because many interesting combinatorial problems are in the family NP but are not known to be in P. (See Karp [7]) That is, each of these problems can be solved in polynomial time if, and only if, there is a polynomial time decision procedure for S. In addition, as Cook and Reckhow [4] observe, P = NP would also imply an interesting philosophical