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
Link To Document