@article{Stockmeyer:TCS:1976,
    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 {$\omega$}-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.},
    Author = {Stockmeyer, Larry J.},
    File = {The polynomial-time hierarchy - a - a - a - g.pdf},
    ISSN = {0304-3975},
    Journal = {Theoretical Computer Science},
    Keywords = {classic},
    Number = {1},
    Pages = {1--22},
    Title = {The polynomial-time hierarchy},
    URL = {http://www.sciencedirect.com/science/article/pii/030439757690061X},
    Volume = {3},
    Year = {1976},
    bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/030439757690061X},
    bdsk-url-2 = {https://doi.org/10.1016/0304-3975(76)90061-X},
    date-added = {2020-02-23 15:18:23 +0100},
    date-modified = {2021-08-12 13:13:24 +0200},
    doi = {10.1016/0304-3975(76)90061-X}
}

@article{Stockmeyer:TCS:1976, 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 {$\omega$}-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.}, Author = {Stockmeyer, Larry J.}, File = {The polynomial-time hierarchy - a - a - a - g.pdf}, ISSN = {0304-3975}, Journal = {Theoretical Computer Science}, Keywords = {classic}, Number = {1}, Pages = {1--22}, Title = {The polynomial-time hierarchy}, URL = {http://www.sciencedirect.com/science/article/pii/030439757690061X}, Volume = {3}, Year = {1976}, bdsk-url-1 = {http://www.sciencedirect.com/science/article/pii/030439757690061X}, bdsk-url-2 = {https://doi.org/10.1016/0304-3975(76)90061-X}, date-added = {2020-02-23 15:18:23 +0100}, date-modified = {2021-08-12 13:13:24 +0200}, doi = {10.1016/0304-3975(76)90061-X} }