DocumentCode :
2722439
Title :
P-productivity and polynomial time approximations
Author :
Wang, Jie
Author_Institution :
Dept. of Comput. Sci., Boston Univ., MA, USA
fYear :
1990
fDate :
8-11 July 1990
Firstpage :
254
Lastpage :
265
Abstract :
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)
Keywords :
computability; computational complexity; function approximation; NP; computable p-productive set; honest K-creative set; p-creativity; polynomial time approximations; polynomials; time constructible function; Computer science; Internet; Natural languages; Polynomials; Productivity; Resumes; Turing machines;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
Conference_Location :
Barcelona
Print_ISBN :
0-8186-6072-4
Type :
conf
DOI :
10.1109/SCT.1990.113974
Filename :
113974
Link To Document :
بازگشت