• DocumentCode
    1992382
  • Title

    Predicate classes and promise classes

  • Author

    Borchert, Bernd

  • Author_Institution
    Heidelberg Univ., Germany
  • fYear
    1994
  • fDate
    28 Jun- 1 Jul 1994
  • Firstpage
    235
  • Lastpage
    241
  • Abstract
    Considering computation trees produced by polynomial time nondeterministic computations one can define a complexity class by any predicate on computation trees, such classes will be called predicate classes. It will be shown that these classes are exactly the principal ideals of the polynomial time many-one reducibility. Additionally, the set of classes-which are called promise classes-definable by promise functions instead of predicates are shown to be equal to the set of countable ideals
  • Keywords
    Turing machines; computational complexity; trees (mathematics); complexity class; computation trees; nondeterministic Turing machines; polynomial time many-one reducibility; polynomial time nondeterministic computations; predicate classes; promise classes; promise functions; Lattices; Polynomials;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
  • Conference_Location
    Amsterdam
  • Print_ISBN
    0-8186-5670-0
  • Type

    conf

  • DOI
    10.1109/SCT.1994.315800
  • Filename
    315800