Paper: A foundational delineation of computational feasibility (at LICS 1991)
Authors: Daniel LeviantAbstract
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
BibTeX
@InProceedings{Leviant-Afoundationaldeline, author = {Daniel Leviant}, title = {A foundational delineation of computational feasibility}, booktitle = {Proceedings of the Sixth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1991}, year = 1991, editor = {Giles Kahn}, month = {July}, pages = {2--11}, location = {Amsterdam, The Netherlands}, publisher = {IEEE Computer Society Press} }