• DocumentCode
    2956148
  • Title

    On Heuristic Time Hierarchies

  • Author

    Pervyshev, Konstantin

  • Author_Institution
    Univ. of California, San Diego
  • fYear
    2007
  • fDate
    13-16 June 2007
  • Firstpage
    347
  • Lastpage
    358
  • Abstract
    We study the existence of time hierarchies for heuristic algorithms. We prove that a time hierarchy exists for heuristic algorithms in such syntactic classes as NP and co-NP, and also in semantic classes AM and MA. Further, we present an alternative approach to proving time hierarchies for heuristic algorithms in BPP. This leads to a simpler proof than the one known before.
  • Keywords
    optimisation; probability; NP classes; heuristic algorithms; semantic classes; time hierarchies; Complexity theory; Computational complexity; Computational modeling; Computer science; Drives; Error correction; Game theory; Heuristic algorithms; Polynomials; Stress;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 2007. CCC '07. Twenty-Second Annual IEEE Conference on
  • Conference_Location
    San Diego, CA
  • ISSN
    1093-0159
  • Print_ISBN
    0-7695-2780-9
  • Type

    conf

  • DOI
    10.1109/CCC.2007.20
  • Filename
    4262775
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2956148