Predicting When P=NP Is Resolved
rjlipton.wordpress.com
Predicting When P=NP Is Resolved
1–10 of 63 posts
Re: Predicting When P=NP Is Resolved
#2My pure amateur, possibly muddled understanding is that P=!NP is rather different from most open conjectures.
A) It's extremely general or even "foundational" in the sense that it's asking whether any algorithm at all exists to solve an extremely general sort of problem in polynomial time.
B) All of the standard methods used to solve problems of this sort have at least been pronounced exhausted at this point.
C) Very few theorems that inherently limit the speed of a class of problems actually have ever been proven. Very few methods for proving these constraints are known.
D) A lot of famous theorems have yielded results through being embedded in a larger, different field where they are just one result of many proved with a new machinery (Fermet most prominently). But given P=!NP is so general it can't really embedded in a larger, tractible space - lots of things are equivalent to it but all these things are kind of the same.
Re: Predicting When P=NP Is Resolved
#3Should we even care for a mathematical proof that P=NP? We know that in practice we haven't been able to come up with algorithms that solve NP problems in polynomial time. Suppose we'll be told that this is possible (i.e. P=NP): will this help up us to invent such algorithms? I don't see how, unless the proof will be by construction.
Re: Predicting When P=NP Is Resolved
#4Is it possible to prove that a proof exists for either P=NP or P!=NP? Conversely, is it possible to prove that the conjecture is unprovable?
Re: Predicting When P=NP Is Resolved
#5Should we even care for a mathematical proof that P=NP? We know that in practice we haven't been able to come up with algorithms that solve NP problems in polynomial time. Suppose we'll be told that this is possible (i.e. P=NP): will this help up us to invent such algorithms? I don't see how, unless the proof will be by construction.
This is an over simplification, but since the np hard problems are reducible to each other, finding polynomial time solution for one problem will give us polynomial time solutions for all np hard problems.
Re: Predicting When P=NP Is Resolved
#6Is it possible to prove that a proof exists for either P=NP or P!=NP? Conversely, is it possible to prove that the conjecture is unprovable?
Yes, and yes. P != NP could be independent from Peano Arithmetic (PA) or the Zermelo-Fraenkel set theory with Axiom of Choice (ZFC) models. That is a separate conjecture which is also presently open.
Re: Predicting When P=NP Is Resolved
#7Next top story on HackerNews:
"Predicting when a new article will be published about how P=NP is not solved yet."
My prediction: Pretty soon :-(
Re: Predicting When P=NP Is Resolved
#8Should we even care for a mathematical proof that P=NP? We know that in practice we haven't been able to come up with algorithms that solve NP problems in polynomial time. Suppose we'll be told that this is possible (i.e. P=NP): will this help up us to invent such algorithms? I don't see how, unless the proof will be by construction.
> will this help up us to invent such algorithms?
In addition to the obvious polynomial reduction between NP problems - which is usually not very practical - it is quite possible that this will help.
> I don't see how
“When I was a child, I spake as a child, I understood as a child, I thought as a child: but when I became a man, I put away childish things. For now we see through a glass, darkly; but then face to face: now I know in part; but then shall I know even as also I am known.” -1 Corinthians 13:11,12
Re: Predicting When P=NP Is Resolved
#9Should we even care for a mathematical proof that P=NP? We know that in practice we haven't been able to come up with algorithms that solve NP problems in polynomial time. Suppose we'll be told that this is possible (i.e. P=NP): will this help up us to invent such algorithms? I don't see how, unless the proof will be by construction.
More likely it will be proving p!=np. Which, yes, would not really teach anything except we would finally know how to prove it, which could be useful for something else.
Re: Predicting When P=NP Is Resolved
#10Should we even care for a mathematical proof that P=NP? We know that in practice we haven't been able to come up with algorithms that solve NP problems in polynomial time. Suppose we'll be told that this is possible (i.e. P=NP): will this help up us to invent such algorithms? I don't see how, unless the proof will be by construction.
This is an over simplification, but since the np hard problems are reducible to each other, finding polynomial time solution for one problem will give us polynomial time solutions for all np hard problems.
NP complete, not NP hard