Why do computer scientists on the whole work under the assumption that P ≠ NP?

Question

Coming from a math background, it seems interesting to me that on the whole computer scientists tend to work under the assumption that $P \neq NP$. While there is no proof either way, generally, unless something can be specifically unproven in both math and science it is taken with a fair amount of strength. I feel that in the years and years people have spent trying to disprove $P = NP$, the fact that no proof has been discovered yet would at least lead some computer scientists to work within the parameters of viewing $P = NP$ as possibly true. However, I often see people working within the framework of it not being true and I was wondering why? It seems more conservative to assume that $P = NP$ in many fields. I've read countless articles about how many computer science and CS-adjacent fields would have to change a lot of their current methodology if $P = NP$ was proven to be true, so why is this not assumed? While it is unlikely to be proven either way any time soon, it just seems somewhat odd to rely so heavily on the a conjecture like that. It almost seems paramount to assuming that Goldbach's conjecture is invalid as there is no proof for it either.

Answer 1

As a rule of thumb, for any unsolved problem people tend to conjecture the statement that starts with a universal quantifier - since if it started with an existential one, then one would expect to have a solution found. Other than this, this topic has been discussed at several other places, see https://en.wikipedia.org/wiki/P_versus_NP_problem#Reasons_to_believe_P_.E2.89.A0_NP or https://rjlipton.wordpress.com/conventional-wisdom-and-pnp/.

Update: Or the very recent Chapter 3 here: http://www.scottaaronson.com/papers/pnp.pdf

Answer 2

Researchers work under the assumptions they think are more plausible. In the case of complexity theory almost every experts thinks $P \neq NP$, so they work under that assumption, therefore we have more conditional results with $P \neq NP$ assumption than $P = NP$.

It also helps that in the case of $P = NP$ problems have simpler answers (e.g. it implies that $P = BPP$, etc.) where as there are more possibilities in the case of $P \neq NP$. But that doesn't means we don't have conditional results with $P = NP$. If you want to have a look at how things would look like in that case check what Russell Impagliazzo calls the Algorithmika in his five worlds.

Also check out Status of Impagliazzo's Worlds?

Russel gave a talk at IAS workshop on his worlds in 2009 (video).

Answer 3

As a rule of thumb, for any unsolved problem people tend to conjecture the statement that starts with a universal quantifier - since if it started with an existential one, then one would expect to have a solution found.

There is a hidden difference between conjectures equivalent to a $\Pi_1^0$ sentence like Riemann hypothesis and conjectures equivalent to a $\Pi_2^0$ sentence like $P \neq NP$. We sort of already know some algorithms (i.e. universal search algorithms like Levin search or Hutter search) which would be polynomial time in case $P = NP$ (well, Levin search only works for syntactic subclasses of $F(NP\cap coNP)$=TFNP like PPA or integer factorization, and Hutter search ...), but that still doesn't settle the $P \neq NP$ conjecture.

I've read countless articles about how many computer science and CS-adjacent fields would have to change a lot of their current methodology if P=NP was proven to be true, so why is this not assumed?

You probably mean that we should assume a non-zero probability that $P=NP$, for example by assuming that $P=NP$ with probability 0.01% and $P \neq NP$ with probability 99.99%. Many computer scientists will claim that this is more or less what they do, but they don't see how this assumption should alter what they write in their papers in any substantial way.

What they could do different would be to state the relation between runtimes achieved by reductions between problems more explicitly. But how much more explicit? Should they try to work less with $f(n)=O(g(n))$ and more with $f(n)\sim g(n)$ ($\lim_{n\to\infty}\frac{f(n)}{g(n)}=1$) and $f(n)\lesssim g(n)$ ($\limsup_{n\to\infty}\frac{f(n)}{g(n)}\leq 1$) for stating resource estimates in theorems? The question is just whether this is realistically possible, since even basic tools like the master theorem are formulated in terms of $f(n)=O(g(n))$, and it is unclear how complicated they would become in terms of $f(n)\lesssim g(n)$ (or whether such a formulation would be useful at all).