The Polynomial-Time Hierarchy

This is material related to MAT 504, Topics in Logic, for the Spring term of 1998 (MWF 1:30-2:20, Fine 401), a course on the polynomial-time hierarchy using tools from mathematical logic.

Here is the relevant directory index, and this is my home page.

Here are notes in gzipped ps form, as of 3/9/98, containing:

  1. Strings
  2. Register machines (here is an example)
  3. Ramified recurrence
  4. The Bellantoni-Cook-Leivant theorem
  5. Cook's theorem
  6. First-order languages
  7. Bounded formulas
  8. Hierarchies
  9. Bounded expansions by definition
  10. Flat formulas
  11. Conventions
  12. Quoting strings
  13. Turing machines
  14. Cofinality

References

[AhHoUl] A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms,, Addison-Wesley, Reading, Massachusetts.

[Be] Stephen Bellantoni, Predicative Recursion and Computational Complexity, Technical Report 264/92, 1992, Department of Computer Science, University of Toronto.

[BeCo] Stephen Bellantoni and Stephen Cook, ``A new recursion-theoretic characterization of the polytime functions'', Computational Complexity, 2, 1992, 97-110.

[BaGiSo] T. Baker, J. Gill, and R. Solovay, ``Relativizations of the P=?NP question'', SIAM Journal of Computing, 4, 1975, 431-442.

[Bu] Samuel R. Buss, Bounded Arithmetic, 1986, Bibiopolis, Napoli.

[Cob] Alan Cobham, ``The intrinsic computational difficulty of functions'', in Y. Bar-Hilled (ed.), Logic, Methodology and Philosophy of Science II, 1964, North-Holland, Amsterdam, 24-30.

[Co] Stephen A. Cook, ``The complexity of theorem-proving procedures'', Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971, Association for Computing Machinery, New York, 151-158.

[GaJo] Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, W. H. Freeman, San Francisco.

[HoUl] J. E. Hopcroft and J. D. Ullman, Formal Languages and their Relation to Automata, Addison-Wesley, Reading, Massachusetts.

[Le91] Daniel Leivant, ``A foundational delineation of computational feasibility'', Sixth Annual IEEE Symposium on Logic in Computer Science, 1991.

[Le] Daniel Leivant, ``Ramified recurrence and computational complexity I: Word recurrence and poly-time'', in P. Clote and J. Remmel (eds.), Feasible Mathematics II, 1994, 320-343.

[MeSt] A. R. Meyer and L. J. Stockmeyer, ``The equivalence problem for regular expressions with squaring requires exponential time'', Proceedings of the 13th Annual Symposium on Switching and Automata Theory, 1972, !EEE Computer Society, Long Beach, California, 125-129.

[Ne] Edward Nelson, ``Internal set theory: A new approach to nonstandard analysis'', Bulletin of the American Mathematical Society, 83, 1977, 1165-1198.

[Ne1] Edward Nelson, ``Chapter 1. Internal Set Theory''.

[Ne2] Edward Nelson, ``Chapter 2. Logic and ZFC''.

[Sh] Joseph R. Shoenfield, Mathematical Logic, 1967, Addison-Wesley, Reading, Massachusetts.

[St] Larry J. Stockmeyer, ``The polynomial-time hierarchy'', Theoretical Computer Science, 3, 1976, 1-22.

[Tu] Alan Turing, ``On computable numbers, with an application to the Entscheidungsproblem'', Proceedings of the London Mathematical Society,, 42, 1936, 230-265 ``A correction'', ibid., 43, 1937, 544-546.

[Wr] Celia Wrathall, ``Complete sets and the polynomial time hierarchy'', Theoretical Computer Science, 3, 1976, 23-33.