• 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