Limit, logic, and computation
收藏PubMed Central1998-01-06 更新2026-04-25 收录
下载链接:
https://pmc.ncbi.nlm.nih.gov/articles/PMC18137/
下载链接
链接失效反馈官方服务:
资源简介:
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.
提供机构:
National Academy of Sciences
创建时间:
1998-01-06



