Why I believe P != NP

Discussions concerned with knowledge of measurement, properties, and relations quantities, theoretical or applied.

Why I believe P != NP

Postby hyksos on April 19th, 2020, 6:19 pm 

The mainstream consensus in computer science is that the class of Polynomial-time solvable algorithms is a different class than Non-deterministic polynomial-time algorithms. That is to say, a vast majority of computer scientists believe that P does not equal NP.

Of course, they don't know this, because a proof of P =!= NP is outstanding. If you found a proof next weekend or whenever, you could mail it to the Clay Mathematics Institute, and Clay will award you a million U.S. dollars. In coming years, you would probably also be awarded a Fields Medal.

http://www.claymath.org/millennium-problems/p-vs-np-problem

The theorem is $1million dollars important. But why? There may exist problems that are solvable only in exponential time (roughly "check every combination by rote"). No matter how much cleverness and ingenuity ever comes in the future, nobody will ever find a "fast" way of solving them. Mathematicians want a proof that such problems exist.

If CS's lack a formal proof of this theorem, why is it that they universally believe it? I won't pretend to speak for others , but I can detail the way I visualize the theorem and why this supports the assertion that P =!= NP , at least heuristically.

In an article of this size, it is hard to communicate a broad swath of algorithms to a reader. I will be referring to something I call "naturally-occurring" algorithms. This is a mushy poetic idea that refers to those algorithms likely found in textbooks and that are useful to people who want to solve problems using a computer. In other words, I am cognizant that someone could stay up late tonight contriving an example that violates some of the assertions I am going to make here. I am aware that contrived edge-cases exist.

In any case, the heuristic for class P being a different class than NP is the following observation : There are no naturally-occurring algorithms that go to polynomial times of high degree.

Faced with a new problem to solve, computer scientists will take it through stages. They will first formulate the problem as exponential, and this is roughly equal to having to "check every combination by rote". Then they find clever methods to reduce the set of candidate solutions that need to be checked. When a breakthrough is made , the CS may find an algorithm that runs in some embarrassing time such as O(n8 + n log n + n) . While embarrassing, they have at least shown that the problem can be solved in polynomial runtime, and so the problem is firmly established to be in the class P.

History has shown that the problem never ends there. In the coming weeks or months another CS takes on the problem and reduces it to O((n3)*(n log n)) A year later, someone finds O(n2). Each reduction is celebrated as ingenious along the way. This is the common, indeed the universal pattern through history. As soon as someone finds that a problem can be solved in polynomial runtime, it is only a matter of time before someone else reduces it to O(n2).

In my academic career , the only algorithm that I know of that goes to O(n3) is Floyd-Warshall. What about algorithms that are O(n4) and O(n5) ? There aren't any. Seriously.

Among graduate students (and even the occasional undergrad), there is a universally unspoken consensus. Algorithms that go to high-powered polys, say O(n25) . It is "understood" that they simply don't exist.

What about on the exponential side of things? (Very tentatively) I will assert that we just never see algorithms that go a tiny base. That would be an algorithm with a runtime complexity of O( 1.09n ). We just don't see them. Well, this author is unaware of any .

Image
The above diagram is what I see in my own mind with visualizing P =?= NP . There is no technical meaning to the graph, per se. What would happen on the left is that it would spread right with higher-degree polynomials. On the right, "lower" exponential would seep slowly leftwards towards the middle.

This is not observed in practice. Instead there is a yawning gulf where no algorithms exist, what is called the No Man's Land in the graph above. When a polytime algorithm is discovered, it is like the problem "leaps over the gap" into the land of O(n3). The persistent nagging existence of this weird gap between these two worlds is what leads me to personally believe that P =!= NP. Indeed a more formal description of No Man's Land mental "idea", but in technical terms, may be the inroads to a formal proof.

If it were the case that P=NP, then we would expect to see high-degree polynomial runtimes that go and meet low-base exponentials in the middle of this graph. Instead of a yawning gap, there would be a smooth transitional zone between them. That heuristic would suggest that P=NP. Almost everything we know about this topic strongly implies there is no such smooth transition.
User avatar
hyksos
Active Member
 
Posts: 1787
Joined: 28 Nov 2014


Return to Mathematics

Who is online

Users browsing this forum: No registered users and 20 guests