-
What is the reason that anyone believes that P may equal NP in the first place? It seems extremely counter to what we know of the universe and how it works - and, as I understand it, it’s overwhelmingly believed and assumed that P does not equal NP - but presumably there must be some legit reason to believe P may equal NP, otherwise the problem wouldn’t persist as an issue to this day.
-
Is the analogy of “NP is like trying to manually type in millions of passwords to see what the correct password is, but P is like being able to find the correct password in as little time as it take to verify the correct password were it given to you” correct?
-
If there actually were a constructive proof of P = NP, what would it look like? (sorry for vagueness, but you probably get what I mean - a formula for “here’s what the universe’s shortcut formula for solving problems in polynomial time is?”)
-
If P actually did equal NP, and were proven with a constructive proof, how long could such a thing be kept secret? And, like in the movie Traveling Salesman (2012,) would it be considered too dangerous to be published?
I’m no expert on this, but until one of the experts get here, I’ll pontificate a bit.
-
Pretty darn sure to the point that “I’ll bet my first born’s life on it” is not good enough for mathematicians. Either its proved or it isn’t. I don’t think any mathematician believed that there was an exception to Fermat’s last “theorem”, or now believes that pi is not a normal number, but until it is proved its still officially an open question.
-
Note that P time doesn’t necessarily mean fast. Polynomials can be really big. If the time it takes to check a password with N characters is N milliseconds, and the time it takes to find a password is (10*N)^10,000 milliseconds, then that will still be polynomial time, even though it would mean that finding that password wouldn’t be done in the lifetime of the universe.
-
Out side of my area of expertise, but it would probably go something like: Problem A is the equivalent of applying this complicated algorithm to the solutions of problem B, which is equivalent to this complicated algorithm applied to the solutions of problem C, which involves checking this subset of the solutions to problem D, where all of the complicated algorithms run in polynomial time and the subset to be checked at the end is a polynomial of the complexity of the input.
-
It would depend on who found it. If it was discovered by an NSA researcher then it would probably be kept under wraps. If it was discovered by a patriotic professor who wanted to get a job at the NSA, then he might contact them first, and then it would be kept under wraps. If it was found by an ordinary college professor, then he would publish the result receive huge numbers of accolades while other people took the time to see if his solution was actually practical and if so what its significance was. Of course most likely this professor would only be putting the final piece in a large puzzle that had led to this point and maybe not even the hardest piece. So it may be that if we reached this point someone was going to put it together soon anyway.
[Moderating]
I’ve edited the title to make it clearer what the thread is about.
[Not moderating]
The reason that people think that P may equal NP is that nobody’s ever proven that it isn’t. Everyone very strongly suspects that they’re not equal, because a proof that they are equal would be very conceptually simple if it were true, but nobody’s ever done it.
As to how you would prove P = NP? Well, there are some problems (quite a few of them, actually) that are called “NP-complete”. What that means is that you can convert any problem in NP into an instance of that problem, in polynomial time. Which means that a solution to that problem can be converted into a solution to any NP problem, and a polynomial solution to that problem could be converted into a polynomial solution for any NP problem. To prove that P = NP, then, all you would have to do would be to come up with a polynomial solution for any one of those NP-complete problems.
How, then, would you prove the reverse, that P ≠ NP (assuming that’s true)? Well, we don’t know exactly, of course. But it would probably come down to some sort of counting argument: Say, showing that there is some maximum possible number of P problems, and that there is larger than that number of possible NP problems.
If, of course, it’s provable at all. Even if, as everyone suspects, P ≠ NP, that doesn’t necessarily mean that it’s possible to prove it: It was nearly a century ago that Gödel proved that there exist some true statements that cannot be proven. Maybe P ≠ NP is one of those.
It’s been more than a few years since I took Theory of Computation, but I’ll throw my thoughts into the ring.
This is a pretty good analogy, but even if P == NP, it might take a lot longer to find a solution to an NP-complete problem than it would to verify the solution. It’s just that the time to do so would grow in a polynomial fashion as the password length increased, rather than in an exponential fashion.
Depends greatly on whether there’s a computationally feasible algorithm. An N^100000 algorithm might be really interesting mathematically, but it wouldn’t likely make any difference in the real world. An N^2 algorithm would be worth a lot of money and would likely be very hard to keep under wraps.
On the other hand, if a N^100000 algorithm were found, that shows that it’s possible, and mathematicians would kick into overdrive in trying to find more efficient variations of it. Which may well, in time, lead to something more realistic like N^4 or N^2 or whatever.
And conversely, superpolynomial time algorithms can be quite efficient. The time bound being superpolynomial just means that there is some specific instance of the problem in the problem space for which the algorithm is slow, not that the algorithm is slow for every, or even most instances.
The simplex algorithm for linear programming is an exponential time algorithm, but in practice most “real world” cases complete quickly and in order to find once of the cases where it actually takes exponential time you have to go out of your way to construct it. There are interior point algorithms for LP that are proven to take polynomial time, but they are often not worth it to use.
Similarly full-program type inference is IIRC equivalent to SAT, but for almost all programs any normal human would actually write, some special case applies so the solution remains practical.
Back when I was in grad school I worked on some NP complete problems, and we could always find heuristics that gave optimal or close to optimal results in almost all cases. There were obviously counterexamples that showed the heuristics were not always optimal. For these, finding a polynomial solution would have little or no impact in the real world unless it was much more efficient than the heuristics, which seems unlikely.
Or maybe just N^{99999.873} 
. I’m reminded of matrix multiplication algorithms, where it was considered a notable development to reduce the complexity from N^{2.3728639} to N^{2.3728596}.