• DocumentCode
    342842
  • Title

    Some decision problems of enormous complexity

  • Author

    Friedman, Harvey M.

  • Author_Institution
    Dept. of Math., Ohio State Univ., Columbus, OH, USA
  • fYear
    1999
  • fDate
    1999
  • Firstpage
    2
  • Lastpage
    12
  • Abstract
    We present some new decision and comparison problems of unusually high computational complexity. Most of the problems are strictly combinatorial in nature; others involve basic logical notions. Their complexities range from iterated exponential time completeness to ∈ 0 time completeness to θ(Ωω,0) time completeness to θ(Ωω,0) time completeness. These three ordinals are well known ordinals from proof theory, and their associated complexity classes represent new levels of computational complexity for natural decision problems. Proofs will appear in an extended version of this manuscript to be published elsewhere
  • Keywords
    computational complexity; decision theory; computational complexity; decision problems; iterated exponential time completeness; logical notions; natural decision problems; proof theory; Computational complexity; Formal languages; Mathematics; Polynomials; Terminology; Turing machines;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Logic in Computer Science, 1999. Proceedings. 14th Symposium on
  • Conference_Location
    Trento
  • ISSN
    1043-6871
  • Print_ISBN
    0-7695-0158-3
  • Type

    conf

  • DOI
    10.1109/LICS.1999.782577
  • Filename
    782577
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=342842