P-productivity and polynomial time approximations
J. Wang · 2002
P-productivity and p-creativity are useful concepts for studying polynomial-time approximations to sets not in P. It is shown that every deterministic O(T(n)) time computable p-productive set for P contains infinite subsets in P and moreover does not contain a largest P subset, where T is any time constructible function which dominates all polynomials. It is then shown that the complement of any honest K-creative set in NP contains infinite subsets in P and no largest one. This settles an open problem of S. Homer (1986).>