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 C 2 provides a clear computational procedure for functionals of C 2. Using functionals of class C 2 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
Link To Document