Paper: There is no recursive axiomatization for feasible functionals of type 2 (at LICS 1992)
Authors: Seth, A.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
BibTeX
@InProceedings{Seth-Thereisnorecursivea, author = {Seth, A.}, title = {There is no recursive axiomatization for feasible functionals of type 2 }, booktitle = {Proceedings of the Seventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1992}, year = 1992, editor = {Andre Scedrov}, month = {June}, pages = {286--295}, location = {Santa Cruz, CA, USA}, publisher = {IEEE Computer Society Press} }