6 ms·

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 polyn

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.
ggggtez 7y ago
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.
danharaj 7y ago
P=NP? is such a difficult problem that it is more likely than not that a proof either way will necessitate extremely powerful new tools in complexity theory. It's hard to say what the impact on algorithm design and analysis would be.
marcosdumay 7y ago
> will this help up us to invent such algorithms? It depends on the details, but it's very likely that the proof carries hints about how to create such algorithm. But even if it doesn't, it being possible means that there is more value in searching for it than people expect today, so more people will look.
joe_the_user 7y ago
Working programmers and even people concerned with producing useful algorithm probably shouldn't care about P=NP?. It seems very likely to be true and if it isn't true, it seems like a polynomial algorithm would be unwieldy indeed. Further, P!=NP is a theory entirely about worst case scenarios. Many NP complete problems are actually quite solvable in the average case and the worst case can have little relation to the average case (SAT solvers that are quite fast on average exist now, for example). For logicians and mathematicians, a proof of N=NP? would be an incredible accomplishment simply because it's a problem that at this point no one know where to start on and so by definition, the proof would be a piece of remarkable and surprising mathematics giving people much to think on.
- AnimalMuppet 7y ago
  P=NP is very likely to be true? I would say it's very likely to be false. Why do I say that? Because it's possible to construct, say, SAT3 problems such that it seems impossible to solve them in polynomial time. If some problems can't be solved in polynomial time, then P!=NP. Why do you think that it's "very likely" that P=NP?
  - norrius 7y ago
    Given the next sentence (...if it isn't true, it seems like a polynomial algorithm would be unwieldy indeed), I think the GP actually meant P!=NP to be true.
- Laakeri 7y ago
  SAT solvers are not fast on average. Even some very simple random distributions produce small (<100 variables) SAT instances that are very hard for the solvers.
  - tgflynn 7y ago
    Do you have a link ? I've been on the lookout for small hard SAT instances for some time and haven't really found any.
salty_biscuits 7y ago
Depends, if it was a constructive proof by example for a useful problem (e.g. somebody finds a provable polynomial algorithm for the traveling salesman problem). Even without the polynomial reduction to other problems that would be pretty great...
- lonelappde 7y ago
  Only if the constant factor and polynomial exponent are small enough to be faster than exponential on real problem sizes.
lacker 7y ago
It would be pretty handy for cryptography to have a better understanding of which problems were hard. P != NP we are already assuming, but if we could use the mechanism on other problems (like knowledge of exponent, discrete log, etc) it would help.
elfexec 7y ago
> Should we even care for a mathematical proof that P=NP? Should we care about the most important computational problem in the world today? I'd say yes. > 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. Why does the method of proof matter? If it is proved that P=NP, then it means most of the pressing computational problems today are solvable in polynomial time. So we can double our efforts in trying to find these solutions. If it is proven that P!=NP, then we can stop wasting our time or just work on solving subsets of these problems. The problem is that we don't know whether the problems can be solved in polynomial time. Put it this way. Which scenario would you prefer. Scenario 1: There MAY be a billion dollars hidden somewhere in Mount Denali. Scenario 2: There IS a billion dollars hidden somewhere in Mount Denali. Scenario 3: There ISN'T a billion dollars hidden somewhere in Mount Denali. Currently, we are at scenario 1. We don't know whether our efforts are for naught. We don't know if we haven't found the billion dollars because it's in a place we haven't looked or if the billion dollars isn't even in the mountain. Proving P=NP, would get us to scenario 2. We know there is a billion dollars there, but we just have to find it. Proving N!=NP would get us to scenario 3. We know the billion dollars isn't there so we don't have to bother wasting our time. I'd say we'd be in a much better position if we were in scenario 2 or 3 than the current scenario 1 we are at right now.

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.

ggggtez 7y ago

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.

danharaj 7y ago

P=NP? is such a difficult problem that it is more likely than not that a proof either way will necessitate extremely powerful new tools in complexity theory. It's hard to say what the impact on algorithm design and analysis would be.

marcosdumay 7y ago

> will this help up us to invent such algorithms? It depends on the details, but it's very likely that the proof carries hints about how to create such algorithm. But even if it doesn't, it being possible means that there is more value in searching for it than people expect today, so more people will look.

joe_the_user 7y ago

Working programmers and even people concerned with producing useful algorithm probably shouldn't care about P=NP?. It seems very likely to be true and if it isn't true, it seems like a polynomial algorithm would be unwieldy indeed. Further, P!=NP is a theory entirely about worst case scenarios. Many NP complete problems are actually quite solvable in the average case and the worst case can have little relation to the average case (SAT solvers that are quite fast on average exist now, for example). For logicians and mathematicians, a proof of N=NP? would be an incredible accomplishment simply because it's a problem that at this point no one know where to start on and so by definition, the proof would be a piece of remarkable and surprising mathematics giving people much to think on.

AnimalMuppet 7y ago
P=NP is very likely to be true? I would say it's very likely to be false. Why do I say that? Because it's possible to construct, say, SAT3 problems such that it seems impossible to solve them in polynomial time. If some problems can't be solved in polynomial time, then P!=NP. Why do you think that it's "very likely" that P=NP?
- norrius 7y ago
  Given the next sentence (...if it isn't true, it seems like a polynomial algorithm would be unwieldy indeed), I think the GP actually meant P!=NP to be true.
Laakeri 7y ago
SAT solvers are not fast on average. Even some very simple random distributions produce small (<100 variables) SAT instances that are very hard for the solvers.
- tgflynn 7y ago
  Do you have a link ? I've been on the lookout for small hard SAT instances for some time and haven't really found any.

salty_biscuits 7y ago

Depends, if it was a constructive proof by example for a useful problem (e.g. somebody finds a provable polynomial algorithm for the traveling salesman problem). Even without the polynomial reduction to other problems that would be pretty great...

lonelappde 7y ago
Only if the constant factor and polynomial exponent are small enough to be faster than exponential on real problem sizes.

lacker 7y ago

It would be pretty handy for cryptography to have a better understanding of which problems were hard. P != NP we are already assuming, but if we could use the mechanism on other problems (like knowledge of exponent, discrete log, etc) it would help.

elfexec 7y ago

> Should we even care for a mathematical proof that P=NP? Should we care about the most important computational problem in the world today? I'd say yes. > 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. Why does the method of proof matter? If it is proved that P=NP, then it means most of the pressing computational problems today are solvable in polynomial time. So we can double our efforts in trying to find these solutions. If it is proven that P!=NP, then we can stop wasting our time or just work on solving subsets of these problems. The problem is that we don't know whether the problems can be solved in polynomial time. Put it this way. Which scenario would you prefer. Scenario 1: There MAY be a billion dollars hidden somewhere in Mount Denali. Scenario 2: There IS a billion dollars hidden somewhere in Mount Denali. Scenario 3: There ISN'T a billion dollars hidden somewhere in Mount Denali. Currently, we are at scenario 1. We don't know whether our efforts are for naught. We don't know if we haven't found the billion dollars because it's in a place we haven't looked or if the billion dollars isn't even in the mountain. Proving P=NP, would get us to scenario 2. We know there is a billion dollars there, but we just have to find it. Proving N!=NP would get us to scenario 3. We know the billion dollars isn't there so we don't have to bother wasting our time. I'd say we'd be in a much better position if we were in scenario 2 or 3 than the current scenario 1 we are at right now.