DocumentCode :
2517684
Title :
On the relativized power of additional accepting paths
Author :
Beigel, Richard
Author_Institution :
Dept. of Comput. Sci., Johns Hopkins Univ., Baltimore, MD, USA
fYear :
1989
fDate :
19-22 Jun 1989
Firstpage :
216
Lastpage :
224
Abstract :
The author defines Uk(n)P as the class of languages in NP that are accepted by machines with at most k(n) accepting paths on each input of length n. Then P ⊆ UP ⊆ Uk(n)P ⊆ Uk(n)+1P ⊆ FewP $4 for every polynomial k(n)⩾2, where FewP is the class of languages in NP that are accepted by machines with a polynomial-bounded number of accepting paths on each input. The author considers whether any of the containments is proper
Keywords :
computational complexity; NP; accepting paths; additional accepting paths; languages; polynomial-bounded number; relativized power; Computer science; Polynomials; Testing; Turing machines;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Structure in Complexity Theory Conference, 1989. Proceedings., Fourth Annual
Conference_Location :
Eugene, OR
Print_ISBN :
0-8186-1958-9
Type :
conf
DOI :
10.1109/SCT.1989.41827
Filename :
41827
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2517684
بازگشت