P vs NP undecidable consequences

Dragonfall · Oct 9, 2014

I don't understand why if P vs NP can't be decided in ZFC, then there exist "near" polynomial time algorithms for NP. How would that possibly work?

David Carroll · Oct 9, 2014

A solution to one of the NP-complete problems, whose proof would involve some other formal language (say, if one found a polynomial time solution to the subset sum problem using number theory or algebra), and then reducing all the other problems to this solution might work.

P vs NP undecidable consequences

Discussion

Undergrad Is infinity a necessary concept?

High School Ant on a stretchy rope puzzle

High School Potato paradox

Undergrad Descartes’ Geometry of Square Roots

High School Does this equation (Einstein’s field equations in general relativity) equal 12?

Mathematica NDSolve with forcing function via "digital waveguide"

MATLAB Unable to produce desired results using state-space model with observer for inverted pendulum

Insights Revisiting the Velocity-Time Function

Insights Remote Operated Gate Control System

Insights AI Enriched Problem Solving

Insights Thinking Outside The Box Versus Knowing What’s In The Box

Insights Why Entangled Photon-Polarization Qubits Violate Bell’s Inequality

Insights Quantum Entanglement is a Kinematic Fact, not a Dynamical Effect

P vs NP undecidable consequences

Discussion

Similar threads

Graduate Relationship between P vs NP and Gödel's incompleteness theorems

Insights P vs. NP conjecture and what is a Turing Machine (TM)?

Graduate Working on the P vs. NP Problem for a Shot at $1,000,000?

Graduate P vs NP Guessing and process of elimination

Can the P vs NP Problem Explain the Mechanics of Comedy?

Graduate The P vs. NP millennial prize problem

Graduate Can Freecell Algorithms Solve the P vs NP Problem?

Will the P vs NP problem ever be solved?

Graduate P vs NP. What if we just assumed P=NP?

Graduate Understanding the P vs NP Problem: Factoring and Its Impact on Internet Security