P-Creative Sets vs. P-Completely Creative Sets* (Extended Abstract)
Jie Wang · 2003
We study p-creative sets and p-completely creative sets. sets, p-creativeness and p- complete creativeness are equivalent, and Myhill's theorem still holds in the polynomial setting. We then consider p-creativity and p-complete creativity for time complexity classes. We show that for P (NP), p-creativeness is equivalent to p-complete cre- ativeness. The existence of p-creative sets for P (NP) in EXP (NEXP) is given. Moreover, we show that every p-m-complet,e 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. k-creative sets and k-completely creative sets in NP are next studied. Although whether k-completely creative sets are equiv- alent to k-creative sets is still open, we can show that in some sense this is true. It is known that k-completely creative sets are R'P-romplete (!JY-85)), but it is not known whether the con- verse is true. We approach this problem based on the technique of showing that every p-m-complete set for EXP is p-creative for P. From this approarh, a new rlass of k-rompletely creative sets is defined as well. An interesting property of this rlass is shown. Finally, we give a sufficient condition for impossibility results. We first show that for r.e.