DocumentCode :
2517430
Title :
p-creative sets vs. p-completely creative sets
Author :
Wang, Jie
Author_Institution :
Dept. of Comput Sci., Boston Univ., MA, USA
fYear :
1989
fDate :
19-22 Jun 1989
Firstpage :
24
Lastpage :
33
Abstract :
It is shown that for recursively enumerable sets, p-creativeness and p-complete creativeness are equivalent, and Myhill´s theorem still holds in the polynomial setting. For P (NP), p-creativeness is shown to be equivalent to p-complete creativeness. The existence of p-creative sets for P (NP) in EXP (NEXP) is given. Moreover, it is shown that every p-m-complete set for EXP (NEXP) is p-completely creative for P (NP), and every p-creative set for NP is NP-hard via many-one reductions. Other results for k-completely creative sets are obtained
Keywords :
computational complexity; recursive functions; Myhill´s theorem; NP; NP-hard; p-complete creativeness; p-creativeness; recursively enumerable sets; Complexity theory; Computational modeling; Computer science; Polynomials; Sufficient conditions; 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.41811
Filename :
41811
Link To Document :
بازگشت