Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Limit, logic, and computation

M H Freedman1

  • 1Microsoft Research 9N, 1 Microsoft Way, Redmond, WA 48052, USA.

Proceedings of the National Academy of Sciences of the United States of America
|January 14, 1998
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Quantitative Phenotyping of Childhood Leukemia Identifies Variable and Invariable Cell Surface Antigens.

Leukemia & lymphoma·2016
Same author

In vitro cytotoxicity of deferoxamine on human marrow haematopoietic progenitors.

Toxicology in vitro : an international journal published in association with BIBRA·2010
Same author

Rh-D isoimmunization.

Canadian Medical Association journal·2010
Same author

Topological quantum computing with only one mobile quasiparticle.

Physical review letters·2006
Same author

Adenovirus-mediated p53 gene therapy in osteosarcoma cell lines: sensitization to cisplatin and doxorubicin.

Cancer gene therapy·2005
Same author

In vitro cytoprotective activity of squalene on a bone marrow versus neuroblastoma model of cisplatin-induced toxicity. implications in cancer chemotherapy.

European journal of cancer (Oxford, England : 1990)·2003
Same journal

Chemotactic self-organization captures the dynamics of mammalian hair follicle patterning.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Tomographic imaging of superconducting order using particle-hole interference.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Inhibitory potential of autologous neutralizing antibodies sets quantitative limits on the rebound-competent HIV-1 reservoir.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Inferring epidemiological parameters under an infectious phylogeography model with visitor dynamics.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Analytical modeling for suction cup designs for skin-interfaced wearable devices.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Improving cell-free metabolism through direct integration of artificial respiratory chains.

Proceedings of the National Academy of Sciences of the United States of America·2026
See all related articles

We introduce "ultrafilter limits" to the Turing model, reframing the P versus NP problem as a decidability challenge. This approach may prove problems outside P by showing their limits are undecidable.

Area of Science:

  • Theoretical Computer Science
  • Mathematical Logic
  • Computational Complexity Theory

Background:

  • The P versus NP problem is a major unsolved question in computer science, concerning whether every problem whose solution can be quickly verified can also be quickly solved.
  • Classical Turing machines provide a foundational model for computation, defining the limits of what is algorithmically computable.
  • Decidability, the property of a problem that an algorithm can always arrive at a correct yes/no answer, is a core concept in computability theory.

Purpose of the Study:

  • To introduce a novel concept, "ultrafilter limits," into the classical Turing model of computation.
  • To develop a new paradigm for interpreting the P versus NP problem as a logical problem of decidability.
  • To establish a potential method for distinguishing problems in class P from those outside of it.

Related Experiment Videos

Main Methods:

  • Integration of "ultrafilter limits" into the established Turing model of computation.
  • Development of a logical framework to analyze computational problems through the lens of decidability.
  • Utilizing the concept of limits to assess the decidability of problems within polynomial time (P) and nondeterministic polynomial time (NP).

Main Results:

  • A new computational paradigm is proposed by incorporating "ultrafilter limits" into the Turing model.
  • The problem of distinguishing P from NP is reframed as a logical decidability problem.
  • A potential method is outlined: if a problem's "ultrafilter limit" is undecidable, it implies the problem lies outside of P.

Conclusions:

  • The "ultrafilter limits" concept offers a novel perspective on computational complexity.
  • This approach may provide a pathway to resolve the P versus NP problem by leveraging principles of mathematical logic and decidability.
  • Problems proven to have undecidable limits could be definitively classified as not belonging to class P.