A foundational delineation of computational feasibility
- 10 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A principle directly pertinent to feasibility, which justifies the identification of P-time with feasible computing, is proposed. It is shown that the computable functions justified on the basis of positive quantifier-free comprehension are precisely the functions computable in deterministic polynomial time. This shows that the class P-time arises naturally from a foundational analysis of feasibility, and that terms using exponentiation can be justified as meaningful only under the admission of infinite sets as completed totalities.Keywords
This publication has 17 references indexed in Scilit:
- Complexity for type-$2$ relations.Notre Dame Journal of Formal Logic, 1990
- Characterizations of the Basic Feasible Functionals of Finite TypePublished by Springer Nature ,1990
- Bounded Linear Logic: A Modular Approach to Polynomial Time ComputabilityPublished by Springer Nature ,1990
- Languages that Capture Complexity ClassesSIAM Journal on Computing, 1987
- Fixed-point extensions of first-order logicAnnals of Pure and Applied Logic, 1986
- Algebras of feasible functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- AlternationJournal of the ACM, 1981
- The typed λ-calculus is not elementary recursiveTheoretical Computer Science, 1979
- Definierbare Funktionen imλ-Kalkül mit TypenArchive for Mathematical Logic, 1975
- Formalized recursive functionals and formalized realizabilityMemoirs of the American Mathematical Society, 1969