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.
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.
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?
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.
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.
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.
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
If anything, it implies you don't actually know the answer either.
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.