Portal de Periódicos da CAPES

The polynomial-time hierarchy

1976; Elsevier BV; Volume: 3; Issue: 1 Linguagem: Inglês

10.1016/0304-3975(76)90061-x

1879-2294

Larry J. Stockmeyer,

Logic, programming, and type systems

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.