A foundational delineation of poly-time
type: Item
instance of: scholarly article
title: A foundational delineation of poly-time
zbMATH Open document ID: 0799.03042
author: Daniel M. Leivant
published in: Information and Computation
publication date: 1994-06-19T00:00:00Z
review text: It is shown that a function is computable in polynomial time if and only if it is computed by an equational program which can be proved to be everywhere converging in constructive second-order logic with set- existence restricted to positive quantifier-free formulas, or alternatively, with set-existence for positive existential formulas. These set-existence principles convey an ontology of infinite sets as evolving, not completed, totalities. These characterization results can be viewed as a foundational justification for identifying polynomial time with feasibility.
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 590747
zbMATH Keywords: descriptional complexity theory
zbMATH Keywords: polynomial time
zbMATH Keywords: constructive second- order logic
zbMATH Keywords: set-existence principles
zbMATH Keywords: feasibility
MaRDI profile type: Publication
full work available at URL: inco.1994.1038
OpenAlex ID: W2041616904
DOI: 10.1006/INCO.1994.1038
description: scientific article; zbMATH DE number 590747