×

Limit, logic, and computation. (English) Zbl 0891.68041

Summary: We introduce “ultrafilter limits” into the classical Turing model of computation and develop a paradigm for interpreting the problem of distinguishing the class P from NP as a logical problem of decidability. We use P (NP) to denote decision problems which can be solved on a (nondeterministic) Turing machine in polynomial time. The concept is that in an appropriate limit it may be possible to prove that problems in P are still decidable, so a problem whose limit is undecidable would be established as lying outside of P.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] THEORY OF ALGORITHMS 44 pp 387– (1985)
[2] J DIFF GEOM 2 pp 1– (1968)
[3] DOKL AK NAUK USSR 105 pp 32– (1955)
[4] PUBLICATIONS MATHEMATIQUES IHES 53 pp 53– (1981) · Zbl 0474.20018
[5] THEOR COMPUT SCI 18 pp 105– (1982) · Zbl 0484.03003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.