Why is there apparently a consensus on the P = NP question?

1.4k Views Asked by At

So through my years of education I have heard a lot about the famous $\mathrm{P}=\mathrm{NP}$ problem. I have seen that a significant number of mathematicians believe that this result is false (and that $\mathrm{P} \neq \mathrm{NP}$). Of course I respect their opinion and understand they don't express anything more than their beliefs. However, the fact that the majority is so overwhelming has always stricken me.

From what I have seen from websites, talks, etc., the main argument in favor of $\mathrm{P} \neq \mathrm{NP}$ is that given our actual knowledge of mathematics, if $\mathrm{P}$ was indeed equal to $\mathrm{NP}$, we would already have a proof. In my humble opinion, this is extremely weak since breakthroughs in the world of algorithms seem to happen regularly, and that century-old problem only get solutions today thanks to new ways of seeing things (Fermat and Poincaré's conjectures are nice examples of this).

I have seen people think that $\mathrm{P} = \mathrm{NP} \cap \mathrm{co}\text{-}\mathrm{NP}$ based on the fact that lots of problems that are in both $\mathrm{NP}$ and $\mathrm{co}\text{-}\mathrm{NP}$ are found to be in $\mathrm{P}$. Apparently the fact that $\mathrm{PRIMES}$ is in $\mathrm{P}$ wasn't that much of a surprise (even if the result is stunning) because $\mathrm{PRIMES}$ was known to be in $\mathrm{NP} \cap \mathrm{co}\text{-}\mathrm{NP}$. Same goes with linear programming.

But on the other hand, it has been shown that if $\mathrm{P} \neq \mathrm{NP}$ there are problems that belong to $\mathrm{NP}$ but are neither $\mathrm{P}$ nor $\mathrm{NP}$-complete, and we know very few problems (AFAIK) that are in this case. Furthermore, some problems in there might fall one day into one $\mathrm{P}$ (maybe Discrete Logarithm after the discovery of a $O(n^{log (n)})$ algorithm?).

So I'm surely missing arguments or extrapolating too much from the little I know. Hence the question : Why is there apparently a consensus on the $\mathrm{P} = \mathrm{NP}$ question?

I don't ask for everyone to state their opinion, I simply wonder about a thought process that seems to be quasi universal in the mind of numerous mathematicians. I honestly don't think this question is opinion-based.

2

There are 2 best solutions below

4
On BEST ANSWER

The post Reasons to believe from Scott Aaronson's blog states...

...ten arguments for believing P!=NP: arguments that are pretty much obvious to those who have thought seriously about the question, but that (with few exceptions) seem never to be laid out explicitly for those who haven’t. You’re welcome to believe P=NP if you choose. My job is to make you understand the conceptual price you have to pay for that belief.

Together with the post from the same blog The Scientific Case for P≠NP (already mentioned in a comment by user @Semiclassical), these pretty much cover the subject.

0
On

Through out the research in the latest years many people have introduced new classes of problems, in other words they tried to categorized problems considering many aspects of computation. Not only the running time as in $\mathrm{P}$ vs $\mathrm{NP}$. Or other models of calculation such as Randomized Turing Machines or even Quantum.

One particular class of interest is the polynomial hierarchy $\mathrm{PH}$ that contains many problems. Another one is $\mathrm{P/poly}$ that contains problems solved by circuits. It is proven, that if $\mathrm{P=NP}$ then many weird results are also true about these classes.

If $\mathrm{P=NP}$ many classes collapse and many problems, outside $\mathrm{NP}$ or $\mathrm{P}$ that are supposed difficult are much easier than considered now. Of course there are no results directly proving these things because it would mean $\mathrm{P=NP}$. These theorems are in the fashion of "If $\mathrm{P=NP}$ implies many counter-intuitive results that are not considered true".

That is also why most people researching this question believe them to be different. If they are equal our whole complexity world would collapse.

The wiki article is very informative. Also this.