Complexity Theory Made Easy

The Formal Language Approach to the Definition of Complexity Classes
  • Heribert Vollmer
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 2710)


In recent years generalized acceptance criteria for different nondeterministic computation models have been examined. Instead of the common definition where an input word is said to be accepted if in the corresponding computation tree an accepting path exists, more general conditions on this tree are used. We survey some recent results from this context, paying particular attention to nondeterministic finite automata as well as nondeterministic polynomial-time Turing machines.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [AS96]
    K. Ambos-Spies. Resource-bounded genericity. In S. B. Cooper, T. A. Slaman, and S. S. Wainer, editors, Computability, Enumerability, Unsolvability. Directions in Recursion Theory, volume 224 of London Mathematical Society Lecture Notes, pages 1–59. Cambride University Press, 1996.Google Scholar
  2. [Bar89]
    D. A. Mix Barrington. Bounded-width polynomial size branching programs recognize exactly those languages in NC1. Journal of Computer and System Sciences, 38:150–164, 1989.CrossRefMathSciNetGoogle Scholar
  3. [BCS92]
    D. P. Bovet, P. Crescenzi, and R. Silvestri. A uniform approach to define complexity classes. Theoretical Computer Science, 104:263–283, 1992.zbMATHCrossRefMathSciNetGoogle Scholar
  4. [BDG95]
    J. L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity I. Texts in Theoretical Computer Science. Springer Verlag, Berlin Heidelberg, 2nd edition, 1995.Google Scholar
  5. [BG81]
    C. Bennett and J. Gill. Relative to a random oracle PA ≠ NPA ≠ coNPA with probability 1. SIAM Journal on Computing, 10:96–113, 1981.zbMATHCrossRefMathSciNetGoogle Scholar
  6. [BGS75]
    T. Baker, J. Gill, and R. Solovay. Relativizations of the P=NP problem. SIAM Journal on Computing, 4:431–442, 1975.zbMATHCrossRefMathSciNetGoogle Scholar
  7. [BI87]
    M. Blum and R. Impagliazzo. Generic oracles and oracle classes. In Proceedings 28th IEEE Symposium on Foundations of Computer Science, pages 118–126. IEEE Computer Society Press, 1987.Google Scholar
  8. [BOC92]
    M. Ben-Or and R. Cleve. Computing algebraic formulas using a constant number of registers. SIAM Journal on Computing, 21:54–58, 1992.zbMATHCrossRefMathSciNetGoogle Scholar
  9. [Büc62]
    J. R. Büchi. On a decision method in restricted second-order arithmetic. In Proceedings Logic, Methodology and Philosophy of Sciences 1960, Stanford, CA, 1962. Stanford University Press.Google Scholar
  10. [BV98]
    H.-J. Burtschick and H. Vollmer. Lindström quantifiers and leaf language definability. International Journal of Foundations of Computer Science, 9:277–294, 1998.CrossRefGoogle Scholar
  11. [CCG+94]
    R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Hastad, D. Ranjan, and P. Rohatgi. The random oracle hypothesis is false. Journal of Computer and System Sciences, 49:24–39, 1994.zbMATHCrossRefMathSciNetGoogle Scholar
  12. [CF91]
    J.-Y. Cai and M. Furst. PSPACE survives constant-width bottlenecks. International Journal of Foundations of Computer Science, 2:67–76, 1991.zbMATHCrossRefMathSciNetGoogle Scholar
  13. [CKS81]
    A. K. Chandra, D. Kozen, and L. J. Stockmeyer. Alternation. Journal of the Association for Computing Machinery, 28:114–133, 1981.zbMATHMathSciNetGoogle Scholar
  14. [CMTV98]
    H. Caussinus, P. McKenzie, D. Thérien, and H. Vollmer. Nondeterministic NC1 computation. Journal of Computer and System Sciences, 57:200–212, 1998.zbMATHCrossRefMathSciNetGoogle Scholar
  15. [Coo71]
    S. A. Cook. Characterizations of pushdown machines in terms of time-bounded computers. Journal of the Association for Computing Machinery, 18:4–18, 1971.zbMATHMathSciNetGoogle Scholar
  16. [EF95]
    H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Perspectives in Mathematical Logic. Springer Verlag, Berlin Heidelberg, 1995.Google Scholar
  17. [FFKL93]
    S. Fenner, L. Fortnow, S. Kurtz, and L. Li. An oracle builder’s toolkit. In Proceedings 8th Structure in Complexity Theory, pages 120–131. IEEE Computer Society Press, 1993.Google Scholar
  18. [Fos93]
    J. A. Foster. The generic oracle hypothesis is false. Information Processing Letters, 45:59–62, 1993.zbMATHCrossRefMathSciNetGoogle Scholar
  19. [GKV03]
    M. Galota, S. Kosub, and H. Vollmer. Generic separations and leaf languages. Mathematical Logic Quarterly, 2003. To appear.Google Scholar
  20. [GR75]
    S. Ginsburg and G. Rozenberg. TOL schemes and control sets. Information and Computation, 27:109–125, 1975.zbMATHMathSciNetGoogle Scholar
  21. [GV01]
    M. Galota and H. Vollmer. A generalization of the Büchi-Elgot-Trakhtenbrot-theorem. In Computer Science Logic, Lecture Notes in Computer Science, pages 355–368, Berlin Heidelberg, 2001. Springer Verlag.CrossRefGoogle Scholar
  22. [GV03]
    M. Galota and H. Vollmer. Functions computable in polynomial space. Technical Report 03-18, Electronic Colloqium in Computational Complexity, 2003.Google Scholar
  23. [HH90]
    J. Hartmanis and L. Hemachandra. Robust machines accept easy sets. Theoretical Computer Science, 74(2):217–226, 1990.zbMATHCrossRefMathSciNetGoogle Scholar
  24. [HLS+93]_U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, and K. W. Wagner. On the power of polynomial time bit-reductions. In Proceedings 8th Structure in Complexity Theory, pages 200–207, 1993.Google Scholar
  25. [HVW96]
    U. Hertrampf, H. Vollmer, and K. W.Wagner. On balanced vs. unbalanced computation trees. Mathematical Systems Theory, 29:411–421, 1996.zbMATHMathSciNetGoogle Scholar
  26. [Jia92]
    J. Jiao. Some questions concerning circuit counting classes and other low-level complexity classes. Master’s essay, 1992.Google Scholar
  27. [JMT96]
    B. Jenner, P. McKenzie, and D. Thérien. Logspace and logtime leaf languages. Information and Computation, 129:21–33, 1996.zbMATHCrossRefMathSciNetGoogle Scholar
  28. [Joh90]
    D. S. Johnson. A catalog of complexity classes. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A, pages 67–161. Elsevier, 1990.Google Scholar
  29. [KSV00]
    S. Kosub, H. Schmitz, and H. Vollmer. Uniform characterizations of complexity classes of functions. International Journal of Foundations of Computer Science, 11(4):525–551, 2000.zbMATHCrossRefMathSciNetGoogle Scholar
  30. [Kur83]
    S. Kurtz. On the random oracle hypothesis. Information and Control, 57:40–47, 1983.zbMATHCrossRefMathSciNetGoogle Scholar
  31. [Lad89]
    R. Ladner. Polynomial space counting problems. SIAM Journal on Computing, 18(6):1087–1097, 1989.zbMATHCrossRefMathSciNetGoogle Scholar
  32. [LFKN90]
    C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. In Proceedings 31st Symposium on Foundations of Computer Science, pages 2–10. IEEE Computer Society Press, 1990.Google Scholar
  33. [LLH]
    Leaf Languages Homepage. Scholar
  34. [Pap94a]
    C. H. Papadimitriou. Computational Complexity. Addison-Wesley, Reading, MA, 1994.zbMATHGoogle Scholar
  35. [Pap94b]
    C. H. Papadimitriou. Personal communication, 1994.Google Scholar
  36. [PV01]
    T. Peichl and H. Vollmer. Finite automata with generalized acceptance criteria. Discrete Mathematics and Theoretical Computer Science, 4:179–192, 2001.zbMATHMathSciNetGoogle Scholar
  37. [Rog67]
    H. Rogers Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York, 1967.zbMATHGoogle Scholar
  38. [Sha92]
    A. Shamir. IP = PSPACE. Journal of the Association for Computing Machinery, 39:869–877, 1992.zbMATHMathSciNetGoogle Scholar
  39. [Sud78]
    I. H. Sudborough. On the tape complexity of deterministic context-free languages. Journal of the Association for Computing Machinery, 25:405–414, 1978.zbMATHMathSciNetGoogle Scholar
  40. [Tho82]
    W. Thomas. Classifying regular events in symbolic logic. Journal of Computer and Systems Sciences, 25:360–376, 1982.zbMATHCrossRefGoogle Scholar
  41. [Tra61]
    B. A. Trakhtenbrot. Finite automata and logic of monadic predicates. Doklady Akademii Nauk SSSR, 140:326–329, 1961. In Russian.Google Scholar
  42. [Ver93]
    N. K. Vereshchagin. Relativizable and non-relativizable theorems in the polynomial theory of algorithms. Izvestija Rossijskoj Akademii Nauk, 57:51–90, 1993. In Russian.Google Scholar
  43. [Vol99a]
    H. Vollmer. Introduction to Circuit Complexity — A Uniform Approach. Texts in Theoretical Computer Science. Springer Verlag, Berlin Heidelberg, 1999.Google Scholar
  44. [Vol99b]
    H. Vollmer. Uniform characterizations of complexity classes. Complexity Theory Column 23, ACM-SIGACT News, 30(1):17–27, 1999.CrossRefGoogle Scholar
  45. [Vol00]
    H. Vollmer. A generalized quantifier concept in computational complexity theory. In J. Väänänen, editor, Generalized Quantifiers and Computation, volume 1754 of Lecture Notes in Computer Science, pages 99–123. Springer Verlag, Berlin Heidelberg, 2000. An extended version appeared in J. Vogel and K. W. Wagner, editors, Komplexität, Graphen und Automaten, Gerd Wechsung zum 60. Geburtstag, Jena, 1999.Google Scholar
  46. [VW97]
    H. Vollmer and K. W.Wagner. Measure one results in computational complexity theory. In D.-Z. Du and K.-I. Ko, editors, Advances in Algorithms, Languages, and Complexity. Kluwer Academic Publishers, 1997.Google Scholar
  47. [Yu97]
    S. Yu. Regular languages. In R. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, volume I, chapter 2, pages 41–110. Springer Verlag, Berlin Heidelberg, 1997.Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2003

Authors and Affiliations

  • Heribert Vollmer
    • 1
  1. 1.Theoretische InformatikUniversität HannoverHannover

Personalised recommendations