The polynomial-time hierarchy

Abstract

The polynomial-time hierarchy is that subrecursive analog of the Kleene arithmetical hierarchy in which deterministic (nondeterministic) polynomial time plays the role of recursive (recursively enumerable) time. Known properties of the polynomial-time hierarchy are summarized. A word problem which is complete in the second stage of the hierarchy is exhibited. In the analogy between the polynomial-time hierarchy and the arithmetical hierarchy, the first order theory of equality plays the role of elementary arithmetic (as the ω-jump of the hierarchy). The problem of deciding validity in the theory of equality is shown to be complete in polynomial-space, and close upper and lower bounds on the space complexity of this problem are established. © 1977.