17 ms·

Predicting When P=NP Is Resolved

106 points by furcyd 7y ago

joe_the_user 7y ago
My 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.
- someguy12342 7y ago
  Great post. Here are a few things pointers if you want more information about your points: B) The situation is actually worse than exhausted. We know (have proven) that the regular methods simply won't work (check up "the reletaivzation barrier" and "natural proofs" and "algebrization") C) We actually can construct problems which take at least a certain amount of time to solve (though admittedly many of them are kind of unnatural). Search up "time hierarchy theorem". This is probably one of the theorems you mention. However, you're right, as far as natural problems go, it appears to be extreme difficult to prove most natural problems takes at least linear time (https://mathoverflow.net/questions/4953/super-linear-time-complexity-lower-bounds-for-any-natural-problem-in-np https://mathoverflow.net/questions/4953/super-linear-time-co...). Note the log*... factor grows extremely slowly. In fact, it is not known whether SAT requires more than linear time. Since SAT is NP-complete, we expect it to have no polynomial time algorithm... and yet here we are wondering whether it requires even more than linear time. If you are interested in this sort of thing, maybe look up fine-grained complexity. Also note that to solve P != NP, we will have to atleast shown P != PSPACE, since PSPACE contains NP. However, even this seemingly easier problem has had no progress and seems like it would require a huge breakthrough.
  - joe_the_user 7y ago
    >>B) The situation is actually worse than exhausted. We know (have proven) that the regular methods simply won't work (check up "the reletaivzation barrier" and "natural proofs" and "algebrization") I've heard of those, even tried to read the proof. Still, my understanding is those claims are ultimately "informal proofs" despite having formal step so the situation isn't entirely closed-up but still very bad.
    - someguy12342 7y ago
      Maybe this will help with understand the revitalization barrier. Most proof of separations of complexity classes relativize, in that not only do they show A strict subset B they also show A^O strict subset B^O for ANY oracle O. Most of these proofs don't actually explicitly state this is true, but they are readily to be extended this way (e.g. the diagonlizing proofs of the time hierarchy theorem) However, we know (Baker, Gill, Solovay) that there exists and oracle O1 where P^O1 subset NP^O1 as well as an oracle O2 such that P^O2 not subset NP^O2 Therefore, we know we a proof of P != NP must not relativize or else that would contradict the aforementioned result.
      - pwdisswordfish2 7y ago
        P^O is always a subset of NP^O, whatever the O.
        joe_the_user 7y ago
        I think the gp left out the strict before the later subset statements.
        someguy12342 7y ago
        That's right! I completely flubbed that part while doing some other edits! Thanks. What I wanted to say is there are O1 and O2 such that: P^O1 strict subset NP^O1 and P^O2 equals NP^O2
- lacker 7y ago
  It isn’t that different - most complexity theory conjectures are this way. Basically, there are all these classes of algorithm. P can be solved in polynomial time, NP can be solved in polynomial time by a computer that gets really lucky with rng, PSPACE can be solved with polynomial space, L can be solved in logarithmic space. For many of these pairs, it kinda feels like they are not the same, but we can’t prove it. So in particular we don’t know that P != PSPACE, which is a much weaker statement, and a very similar one, compared to P != NP. Similarly, we can’t prove there are cryptographically secure hash functions, and we can’t prove it’s hard to factor numbers. Basically, we just have very few mathematical tools for proving that complexity classes are different. It’s hard to prove that algorithmic problems are hard. We have diagonalization, which shows that the halting problem is impossible and that P != EXPTIME, and that’s about it. Anyway, I would conclude not that P != NP is a uniquely hard problem, as much as that complexity theory is very young compared to most fields of mathematics, and there are still many statements we can’t prove.
- jeromebaek 7y ago
  P vs NP is also distinguished in that many people think it has profound philosophical implications. Nick Land seems to think this (http://www.uf-blog.net/crypto-current-021/ http://www.uf-blog.net/crypto-current-021/), and so does Scott Aaronson (“if P=NP, the word would be a profoundly different place than we usually assume it to be ... there would be no value in “creative gaps””). Though I think Land’s idea is a lot more interesting — he says P vs NP is a paraphrase of the analytic vs synthetic distinction.
AwesomeLemon 7y ago
Should 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.
- enitihas 7y ago
  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.
  - jagraff 7y ago
    NP complete, not NP hard
- einpoklum 7y ago
  > 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
  - ggggtez 7y ago
    Don't respond to a question with a vague quote, if you want to talk about putting away childish things. If anything, it implies you don't actually know the answer either.
    - jakear 7y ago
      The point of the quote is to say that they don't know the answer either. So, yes. Think of it as: we are all children when it comes to the ramifications of the proof of P vs NP. We do not know the impact; we cannot know the impact. We will know it when it arrives.
kibwen 7y ago
Is 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?
- throwawaymath 7y ago
  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.
  - lidHanteyk 7y ago
    Surprisingly, this cannot be the case, not without discovering a completely new kind of independence proof. [0] p26 discusses the problem. > At the end of the day, a polynomial-time algorithm for 3-SAT either exists or it doesn't! [0] https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf
- marcosdumay 7y ago
  Since an algorithm for running NP-complete problems in P-time would be enough to prove whether P=NP, wouldn't the impossibility to prove it just prove that P!=NP?
  - H8crilA 7y ago
    Not really, we don't know if human reasoning is contained in P, BPP, BQP, PP or even PSPACE (is there a ghost in this shell?). It may not be. Though human reasoning probably is contained in P, just like probably P != NP.
    - lonelappde 7y ago
      Human reasoning is constant time. Generalized unbounded humanlike reasoning might not be.
  - bloak 7y ago
einpoklum 7y ago
Next top story on HackerNews: "Predicting when a new article will be published about how P=NP is not solved yet." My prediction: Pretty soon :-(
jacobkg 7y ago
In my mind I always regard P/NP in the same category as the Riemann Hypothesis^. That has been open since 1859 (160 years) and shows no signs of cracking. So in other words we may be in for a long wait. ^Perhaps because one of the hypothesized examples of a hard problem is the factoring of multiples of large primes (though not proved NP Complete). Or perhaps because they are both extremely famous open problems.
- hinkley 7y ago
  One of the things that slows scientific progress is the lack of cross-discipline learning. Every so often you hear about someone taking an old concept from another field and applying it. Quite a few breakout companies have combined interdisciplinary knowledge into one product and made a mint. So many people are affected by NP complete problems that you'd think that someone would have a problem that appeared simpler on the surface and gave insights into a P solution, but either nobody has, or the right phrasing about it has caught nobody's attention. There's an XKCD lamenting something pretty similar. You solved some unsolved problem but nobody will ever know because it's buried in a bug fix for your obscure little product.
  - empath75 7y ago
    It’d be amazing if we found some polynomial solution to an np complete problem buried in some kids Minecraft mod 10 years from now.
  - fovc 7y ago
    https://m.xkcd.com/664/ https://m.xkcd.com/664/
    - raverbashing 7y ago
      I think Academia is more likely to criticize your technique because it doesn't generalize to any ring or you didn't prove a certain assumption you had. Of course the real bug is in some IEEE 754 quirk you forgot to consider.
    - 7y ago
skissane 7y ago
I have no idea what will be proven nor when. (My uneducated guess is not any time soon.) But I hope it isn't "here's a proof that P!=NP". That'd be just too boring... Much cooler possibilities would be "here's a non-constructive proof that P=NP" or "here's a proof that P=NP is independent of ZFC".
- enriquto 7y ago
  for me the most exciting would be "here's a constructive proof that P=NP. It uses polynomials of degree one million".
  - chx 7y ago
    While Knuth has a different take on the P=?NP problem than most others, namely he believes P=NP, nonetheless, he is also saying that the degree won't ever be known and not even an upper bound will be known for it. http://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions http://www.informit.com/articles/article.aspx?p=2213858&WT.m... Certainly "if P=NP it'll be a pure non-constructive proof with no practical consequence whatsoever" feels right.
copperx 7y ago
What is the difference between solving and resolving an open problem?

106 points by furcyd 7y ago

My 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.

someguy12342 7y ago
Great post. Here are a few things pointers if you want more information about your points: B) The situation is actually worse than exhausted. We know (have proven) that the regular methods simply won't work (check up "the reletaivzation barrier" and "natural proofs" and "algebrization") C) We actually can construct problems which take at least a certain amount of time to solve (though admittedly many of them are kind of unnatural). Search up "time hierarchy theorem". This is probably one of the theorems you mention. However, you're right, as far as natural problems go, it appears to be extreme difficult to prove most natural problems takes at least linear time (https://mathoverflow.net/questions/4953/super-linear-time-complexity-lower-bounds-for-any-natural-problem-in-np https://mathoverflow.net/questions/4953/super-linear-time-co...). Note the log*... factor grows extremely slowly. In fact, it is not known whether SAT requires more than linear time. Since SAT is NP-complete, we expect it to have no polynomial time algorithm... and yet here we are wondering whether it requires even more than linear time. If you are interested in this sort of thing, maybe look up fine-grained complexity. Also note that to solve P != NP, we will have to atleast shown P != PSPACE, since PSPACE contains NP. However, even this seemingly easier problem has had no progress and seems like it would require a huge breakthrough.
- joe_the_user 7y ago
  >>B) The situation is actually worse than exhausted. We know (have proven) that the regular methods simply won't work (check up "the reletaivzation barrier" and "natural proofs" and "algebrization") I've heard of those, even tried to read the proof. Still, my understanding is those claims are ultimately "informal proofs" despite having formal step so the situation isn't entirely closed-up but still very bad.
  - someguy12342 7y ago
    Maybe this will help with understand the revitalization barrier. Most proof of separations of complexity classes relativize, in that not only do they show A strict subset B they also show A^O strict subset B^O for ANY oracle O. Most of these proofs don't actually explicitly state this is true, but they are readily to be extended this way (e.g. the diagonlizing proofs of the time hierarchy theorem) However, we know (Baker, Gill, Solovay) that there exists and oracle O1 where P^O1 subset NP^O1 as well as an oracle O2 such that P^O2 not subset NP^O2 Therefore, we know we a proof of P != NP must not relativize or else that would contradict the aforementioned result.
    - pwdisswordfish2 7y ago
      P^O is always a subset of NP^O, whatever the O.
      - joe_the_user 7y ago
        I think the gp left out the strict before the later subset statements.
        someguy12342 7y ago
        That's right! I completely flubbed that part while doing some other edits! Thanks. What I wanted to say is there are O1 and O2 such that: P^O1 strict subset NP^O1 and P^O2 equals NP^O2
lacker 7y ago
It isn’t that different - most complexity theory conjectures are this way. Basically, there are all these classes of algorithm. P can be solved in polynomial time, NP can be solved in polynomial time by a computer that gets really lucky with rng, PSPACE can be solved with polynomial space, L can be solved in logarithmic space. For many of these pairs, it kinda feels like they are not the same, but we can’t prove it. So in particular we don’t know that P != PSPACE, which is a much weaker statement, and a very similar one, compared to P != NP. Similarly, we can’t prove there are cryptographically secure hash functions, and we can’t prove it’s hard to factor numbers. Basically, we just have very few mathematical tools for proving that complexity classes are different. It’s hard to prove that algorithmic problems are hard. We have diagonalization, which shows that the halting problem is impossible and that P != EXPTIME, and that’s about it. Anyway, I would conclude not that P != NP is a uniquely hard problem, as much as that complexity theory is very young compared to most fields of mathematics, and there are still many statements we can’t prove.
jeromebaek 7y ago
P vs NP is also distinguished in that many people think it has profound philosophical implications. Nick Land seems to think this (http://www.uf-blog.net/crypto-current-021/ http://www.uf-blog.net/crypto-current-021/), and so does Scott Aaronson (“if P=NP, the word would be a profoundly different place than we usually assume it to be ... there would be no value in “creative gaps””). Though I think Land’s idea is a lot more interesting — he says P vs NP is a paraphrase of the analytic vs synthetic distinction.

AwesomeLemon 7y ago

Should 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.

enitihas 7y ago
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.
- jagraff 7y ago
  NP complete, not NP hard
einpoklum 7y ago
> 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
- ggggtez 7y ago
  Don't respond to a question with a vague quote, if you want to talk about putting away childish things. If anything, it implies you don't actually know the answer either.
  - jakear 7y ago
    The point of the quote is to say that they don't know the answer either. So, yes. Think of it as: we are all children when it comes to the ramifications of the proof of P vs NP. We do not know the impact; we cannot know the impact. We will know it when it arrives.

kibwen 7y ago

Is 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?

throwawaymath 7y ago
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.
- lidHanteyk 7y ago
  Surprisingly, this cannot be the case, not without discovering a completely new kind of independence proof. [0] p26 discusses the problem. > At the end of the day, a polynomial-time algorithm for 3-SAT either exists or it doesn't! [0] https://www.scottaaronson.com/papers/pnp.pdf https://www.scottaaronson.com/papers/pnp.pdf
marcosdumay 7y ago
Since an algorithm for running NP-complete problems in P-time would be enough to prove whether P=NP, wouldn't the impossibility to prove it just prove that P!=NP?
- H8crilA 7y ago
  Not really, we don't know if human reasoning is contained in P, BPP, BQP, PP or even PSPACE (is there a ghost in this shell?). It may not be. Though human reasoning probably is contained in P, just like probably P != NP.
  - lonelappde 7y ago
    Human reasoning is constant time. Generalized unbounded humanlike reasoning might not be.
- bloak 7y ago

einpoklum 7y ago

Next top story on HackerNews: "Predicting when a new article will be published about how P=NP is not solved yet." My prediction: Pretty soon :-(

jacobkg 7y ago

In my mind I always regard P/NP in the same category as the Riemann Hypothesis^. That has been open since 1859 (160 years) and shows no signs of cracking. So in other words we may be in for a long wait. ^Perhaps because one of the hypothesized examples of a hard problem is the factoring of multiples of large primes (though not proved NP Complete). Or perhaps because they are both extremely famous open problems.

hinkley 7y ago
One of the things that slows scientific progress is the lack of cross-discipline learning. Every so often you hear about someone taking an old concept from another field and applying it. Quite a few breakout companies have combined interdisciplinary knowledge into one product and made a mint. So many people are affected by NP complete problems that you'd think that someone would have a problem that appeared simpler on the surface and gave insights into a P solution, but either nobody has, or the right phrasing about it has caught nobody's attention. There's an XKCD lamenting something pretty similar. You solved some unsolved problem but nobody will ever know because it's buried in a bug fix for your obscure little product.
- empath75 7y ago
  It’d be amazing if we found some polynomial solution to an np complete problem buried in some kids Minecraft mod 10 years from now.
- fovc 7y ago
  https://m.xkcd.com/664/ https://m.xkcd.com/664/
  - raverbashing 7y ago
    I think Academia is more likely to criticize your technique because it doesn't generalize to any ring or you didn't prove a certain assumption you had. Of course the real bug is in some IEEE 754 quirk you forgot to consider.
  - 7y ago

skissane 7y ago

I have no idea what will be proven nor when. (My uneducated guess is not any time soon.) But I hope it isn't "here's a proof that P!=NP". That'd be just too boring... Much cooler possibilities would be "here's a non-constructive proof that P=NP" or "here's a proof that P=NP is independent of ZFC".

enriquto 7y ago
for me the most exciting would be "here's a constructive proof that P=NP. It uses polynomials of degree one million".
- chx 7y ago
  While Knuth has a different take on the P=?NP problem than most others, namely he believes P=NP, nonetheless, he is also saying that the degree won't ever be known and not even an upper bound will be known for it. http://www.informit.com/articles/article.aspx?p=2213858&WT.mc_id=Author_Knuth_20Questions http://www.informit.com/articles/article.aspx?p=2213858&WT.m... Certainly "if P=NP it'll be a pure non-constructive proof with no practical consequence whatsoever" feels right.

copperx 7y ago

What is the difference between solving and resolving an open problem?