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