On p-creative sets and p-completely creative sets
Jie Wang · Theoretical Computer Science · 1991
We study p-creative sets and p-completely creative sets. We first prove that for recursively enumerable sets, p-creativeness is equivalent to p-complete creativeness and Myhill's theorem still holds in the polynomial setting. We then consider p-creativity and p-complete creativity for time complexity classes. We prove that for P, p-creativeness is equivalent to p-complete creativeness. Moreover, we prove that a set A is p-m-complete for DEXT iff A is p-creative for P in DEXT. Since every p-m-complete set for DEXT is p-1-complete (Berman, 1977), we know that Myhill's theorem still holds for P in DEXT. These results can also be proved for NP in NEXT. k-creative sets and k-completely creative sets in NP are next studied. (k,l)-creative sets and (k,l)-completely creative sets in a more general setting are defined and shown to exist. It is known that k-completely creative sets are NP-complete (Joseph and Young, 1985), but it is not known whether the converse is true. We approach this problem based on our “double diagonalization” technique of showing that every p-m-complete set for DEXT is p-creative for P. A new class of k-completely creative sets is constructed as well.