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.
展开▼
