For definition of productive set, see here and here, that is defined with computability, or computable function. Restricting computable function as function of polynomial computational complexity, is there counterpart of productive set with polynomial computational complexity? That is the set has infinite sets of polynomial computational complexity, and there is no function of polynomial computational complexity which output all element of the set.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Jie Wang published some papers on the topic, see Polynomial time productivity, approximations, and levelability. SIAM Journal on Computing, 21:1100-1111, 1992 and On p-creative sets and p-completely creative sets. Theoretical Computer Science, 85:1-31, 1991.
