12
$\begingroup$

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.

$\endgroup$
  • 8
    $\begingroup$ Goldbach's conjecture isn't the correct analogy. Why do number theorists work under the assumption that the Riemann hypothesis is true? $\endgroup$ – Peter Shor Jan 2 '17 at 17:27
  • 2
    $\begingroup$ These aren't random opinions based solely on the fact that nobody has disproved stuff; they're informed opinions. Nobody has disproved the existence of a projective plane of order 12, but nearly everybody thinks it doesn't exist. $\endgroup$ – Peter Shor Jan 2 '17 at 17:30
  • 6
    $\begingroup$ @AJ "if you argue otherwise you will be called crazy" ... if you had an interesting argument, then it would be far from crazy, in my mind. It would be extremely important. In several cases where researchers have assumed something similar to P=NP, we have been able to derive a contradiction. E.g. the time-space tradeoffs for SAT. (Note: the current question under discussion is not in the ballpark of an interesting argument. It asserts that P=NP is the more conservative assumption, with no reasons given.) $\endgroup$ – Ryan Williams Jan 2 '17 at 20:18
  • 3
    $\begingroup$ In a way, if we assume that P=NP, then a large part of the field would be just closed. No more hardness of approximation, explicit constructions, some crypto primitives. If this was true, what other interesting questions could we ask? $\endgroup$ – Igor Shinkar Jan 2 '17 at 20:22
  • 11
    $\begingroup$ I don't think OP has seriously done his homework on this question. This is discussed in many placed. See for example rjlipton.wordpress.com/2009/09/18/…, scottaaronson.com/blog/?p=1720, the links Domotor has given, any book on complexity theory.. $\endgroup$ – Sasho Nikolov Jan 2 '17 at 23:46
13
$\begingroup$

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

$\endgroup$
  • $\begingroup$ As much as I like this answer (and I like it a lot), I'm a bit concerned: you can phrase the statement $P = NP$ in several ways. Some examples: $\forall$ languages $L$ we have $L \in P \iff L \in NP$; OR $\exists$ algorithm $A$ s.t. $A$ runs in poly-time and $A$ accepts $w$ iff $w \in SAT$; OR $\forall$ NP-complete languages $L$ we have $L \in P$; OR $\exists$ NP-complete language $L \in P$. Some of these statements start with existential and some with universal quantifiers, so clearly we can't apply your rule (universal quantifier implies probably true) to all of the statements. $\endgroup$ – Mikhail Rudoy Jan 2 '17 at 21:17
  • $\begingroup$ @Mikhail: Indeed! I'm not sure how one could formalize which option to pick. $\endgroup$ – domotorp Jan 2 '17 at 22:35
  • 1
    $\begingroup$ @MikhailRudoy: You have to be careful to specify first-order versus second-order quantifiers. When you say "$\forall$ languages $L$" that's a second-order quantifier, but when you say "$\exists$ algorithm $A$" it's a first-order quantifier. So the "$\exists$ algorithm $A$" formulation has zero second-order quantifiers, and is thus closer to the true "logical complexity" of the statement "P=NP." As a first-order sentence, this version of "P=NP" indeed begins with an existential quantifier. (Though this doesn't completely resolve your objection, it does resolve your specific examples.) $\endgroup$ – Joshua Grochow Jan 2 '17 at 23:31
  • 3
    $\begingroup$ There are many exceptions. Before the monster group was proved to exist, it was a conjecture that started with an existential quantifier. And for one of the Clay problems (the Yang-Mills one), the conjectured outcome starts with an existential quantifier. $\endgroup$ – Peter Shor Jan 2 '17 at 23:51
  • 1
    $\begingroup$ @MikhailRudoy: en.wikipedia.org/wiki/Second-order_logic $\endgroup$ – Joshua Grochow Jan 3 '17 at 16:16
0
$\begingroup$

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).

$\endgroup$
-1
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ One of the justifications for big-oh notation in many uniform machine models is that the constants are not robust to the model. For example, see the Linear Speed-up Theorem. (And then I think we still use big-oh in non-uniform models because we're actually using them to try to understand uniform models...) $\endgroup$ – Joshua Grochow May 7 '17 at 2:18
  • $\begingroup$ @JoshuaGrochow Even so big-oh notation can invite misuse, I don't think it needs much justification. It often succinctly expresses exactly what we want to say. I just tried to find similarly succinct notations for situations were we could be more explicit. (When we find ourself referring to the proof instead of the theorem, then this is a typical situation where we probably should be more explicit. This comes up in explanations how constructive/intuitionistic logic can be helpful.) $\endgroup$ – Thomas Klimpel May 7 '17 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.