• DocumentCode
    2894138
  • Title

    There is no recursive axiomatization for feasible functionals of type 2

  • Author

    Seth, Anil

  • Author_Institution
    Comput. Sci. Group, Tata Inst. of Fundamental Res., Bombay, India
  • fYear
    1992
  • fDate
    22-25 Jun 1992
  • Firstpage
    286
  • Lastpage
    295
  • Abstract
    The author shows a class of type-two feasible functionals, C 2, that satisfies Cook´s conditions, (1990) and cannot be expressed as the lambda closure of type-one poly-time functions and any recursively enumerable set of type-two feasible functionals. Further, no class of total type-two functionals containing this class is representable as the lambda closure of a recursively enumerable set of type-two total computable functionals and type-one poly-time functions. The definition of C2 provides a clear computational procedure for functionals of C2. Using functionals of class C2 a more general notion of polynomial-time reducibility between two arbitrary type-one functions can be introduced
  • Keywords
    Turing machines; computational complexity; recursive functions; Turing machines; computational procedure; feasible functionals; lambda closure; polynomial-time reducibility; recursive axiomatization; recursively enumerable set; time complexity; type-one poly-time functions; type-two feasible functionals; Calculus; Computer science; Polynomials; Turing machines;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Logic in Computer Science, 1992. LICS '92., Proceedings of the Seventh Annual IEEE Symposium on
  • Conference_Location
    Santa Cruz, CA
  • Print_ISBN
    0-8186-2735-2
  • Type

    conf

  • DOI
    10.1109/LICS.1992.185541
  • Filename
    185541