[AwesomeLemon]

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.

[elfexec]

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

[joe_the_user]

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]

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]

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]

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]

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.

[Laakeri]

SAT competition 2018 http://sat2018.forsyte.tuwien.ac.at/index.php had a track with random instances. The article "Generating the Uniform Random Benchmarks" in https://helda.helsinki.fi/bitstream/handle/10138/237063/sc20... contains the descriptions of the random instances used.

[tgflynn]

Thanks for the link, but it seems difficult to answer the question "find a SAT instance with no more than 100 variables which all competing solvers failed to solve in the allowed time" from the information presented here.

I'm going to download the benchmarks and try to correlate them with the results CSV table (which doesn't show number of variables for each instance), but since the full random benchmarks are 2.9 GB compressed this might take a fair amount of work.

If you can provide any further guidance on finding the relevant instances I'd appreciate it.

[tgflynn]

Also note that just specifying the number of variables may not be terribly informative if you don't also specify the maximum clause size and the number of clauses.

For example I see some instances here with 120 variables but they are 7-SAT with around 10k clauses. Unless I'm mistaken reducing those to <=3-SAT will require adding about 20k more variables and tripling the number of clauses.

[enitihas]

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]

NP complete, not NP hard

[salty_biscuits]

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]

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

[danharaj]

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.

[ggggtez]

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.

[marcosdumay]

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

[lacker]

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.

[einpoklum]

> 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]

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]

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.