On some direct encodings of nondeterministic Turing machines operating in polynomial time into p-complete problems

Abstract

Cook [1] and Karp [2] introduced the notion of complete problems. Meyer and Stockmeyer [3] showed that some problems require exponential time. All these problems have a common property which in the latter case implies that they cannot be solved in polynomial time.