I am not aware of any practical use of P=NP outside of pure complexity theory, and the P!=NP case is already ubiquitous assumption anyways. P=NP would be a notable result, but probably not important.
That said, there is definitely potential practical implications for this. Even if it means we can know np problems do not have efficient solutions - that is something with practical implications.
- if the solution is constructive,
- if the asymptotic solution has good constants (lower bound on input size, highest degree term), and
- having no other mitigating factors (requiring absurd amounts of space, for example)
The idea that P=efficient is a complete misnomer. For simple algorithms, asymptotic analysis is a fine enough coarse-grained view of program performance. However for extreme cases (like may be the case for P=NP) asymptotic analysis tells you almost nothing at all.
Yes it does. That is literally exactly what it means. The class P is the class of problems which are considered theoretically "tractable"/"efficiently solvable"/"feasibly solvable" (Cobham-Edmonds thesis). Hence, if NP=P, then that same definition extends to all problems in NP.
In practical terms, the class of efficient algorithms is probably O(n^3) at best, and even then assuming no huge constant factors.
Where was that question asked?
> That said, there is definitely potential practical implications for this. Even if it means we can know np problems do not have efficient solutions [emphasis mine]
So, this was about efficiency in the practical sense, not some largely useless definition of efficiency by which galactic algorithms are "efficient".
> An explanation is due on the use of the words "efficient algorithm." First, what I present is a conceptual description of an algorithm and not a particular formalized algorithm or "code." For practical purposes computational details are vital. However, my purpose is only to show as attractively as I can that there is an efficient algorithm. According to the dictionary, "efficient" means "adequate in operation or performance." This is roughly the meaning I want—in the sense that it is conceivable for maximum matching to have no efficient algorithm. Perhaps a better word is "good."
> It is by no means obvious whether or not there exists an algorithm whose difficulty increases only algebraically with the size of the graph. The mathematical significance of this paper rests largely on the assumption that the two preceding sentences have mathematical meaning.
> ...
> When the measure of problem-size is reasonable and when the sizes assume values arbitrarily large, an asymptotic estimate of FA(N) (let us call it the order of difficulty of algorithm A) is theoretically important. It cannot be rigged by making the algorithm artificially difficult for smaller sizes. It is one criterion showing how good the algorithm is—not merely in comparison with other given algorithms for the same class of problems, but also on the whole how good in comparison with itself. There are, of course, other equally valuable criteria. And in practice this one is rough, one reason being that the size of a problem which would ever be considered is bounded.
You should read the rest of section 2, it's short very clear. Calling P the class of "efficiently solvable" problems is a completely reasonable framing for this paper, considering that this was written at a time when we had fewer tools to formally compare algorithms. Edmonds correctly does not claim that all P algorithms are feasible, and my opinion that P=NP is not important is based on the 60 years of feasible non-P computations we've had since.
I am not a complexity theorist, but ive always doubted the n^1000 solution to p=np being likely. Think about it - that essentially means you have to loop through the data 1000 times, but no more than that, no matter how much data. It just doesn't seem natural that looping 999 wouldn't be enough, but 1000 would be precisely enough. Its a sort of middle ground that seems like it would be extremely odd to me. Much more so than p=np with a low exponent or p!=np.
I still think it would be bizarre to have to nest a loop n layers deep, where n-1 is not enough, but n layers is sufficient for really large n. Like what extra info would you get on the 1000th nested loop that you didn't on the first 999.
Of course there is nothing formal about this, it just feels like it would be wrong to me (and hence personally i would consider it the most interesting result). Of course gut feelings dont really count for much and i have nothing more than that.
I suppose my intuition is that increasing the exponent gives diminishing returns to how much more power you really get , so it doesn't make sense for problems to be in the n^1000 range. My gut feeling is they should either be easier or harder. I certainly can't think of very many non-exponential algorithms in the > n^50 range.
I think you can't require absurd amounts of space, because you only have P steps to access that space, therefore the space is bounded to P anyway. (Memory you can't access can't help you.)
For one thing, the proof of P!=NP (which is what most people assume) will almost certainly provide us a lot of new math and insight. So yes, there won't necessarily be something new practically just from the result P!=NP, because this is what everyone assumes, but it's likely to yield lots of new math.
As for the case where P=NP - that's almost certainly a gamechanger, especially if this is proved by way of a counterexample, e.g. a problem in NP that is actually computable in P. While this may not be immediately computable on current hardware, at that point we'll almost certainly focus a lot of time and effort into making it more feasible.
What CS problem do you think is more important?
As for more important problems-- I think it's more important to improve the specializations of NP problems, heuristically, for problem instances which arise in practice. A concrete example in my line of work could be improving the performance of SMT solvers on encodings of real programs. There's a lot of exciting work happening in this area and it's opening doors in program verification previously thought to be unrealistic. IIUC the formal methods team at AWS is putting a lot of work into memoized, distributed SMT solving, and are making meaningful gains over the current state of the art.
I don't really care if we can solve the most general NP hard problems in O(bad*N^bad) only for N>bad. A) Even a getting result that weak seems to be too challenging to prove and probably not true, and B) trying to solve the most general problem is complete overkill for any problems that come up outside a complexity textbook.