Limit, logic, and computation.
Where this comes from
- Record sourced from PubMed, PMID 9419334.
- Also identified by PMC identifier 18137.
- No licence information is recorded for this record.
- Because redistribution is not established, this page shows the abstract only. Follow the links below for the full text.
Abstract
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.