What is the evidence that P could equal NP?
I guess this is the same as asking:
If it's known that $P \subseteq NP$ (depending on standard), then why is this not enough? Why assume that P could equal NP?
1
$\begingroup$
$\endgroup$
-
$\begingroup$ @Kittsil Yes. And I don't understand the down voting, since haven't seen this one assessed clearly anywhere. $\endgroup$ – mavavilj Sep 18 '15 at 10:45
-
3$\begingroup$ It isn't known that $P\subset NP$, only that $P\subseteq NP$. $\endgroup$ – Tom van der Zanden Sep 18 '15 at 11:58
-
$\begingroup$ there is little to no "evidence"... quite to the contrary most evidence seems to be the opposite... $\endgroup$ – vzn Sep 18 '15 at 16:02
-
1$\begingroup$ Don Knuth believes that P=NP (q17). $\endgroup$ – Raphael♦ Sep 19 '15 at 10:12
5
$\begingroup$
$\endgroup$
This is a rather strange question to ask, given that a large majority of complexity theorists believe that P is different from NP. All the evidence we have points at P being different from NP, which is why most people believe that P doesn't equal NP.
It's like asking a climate scientist for the evidence that there is no connection between global warming and greenhouse gasses. The main difference is the standard of proof involved. The climate scientist is content with trying to convince you that there is strong evidence for anthropogenic global warming. The complexity theorist's goal is a proof, and she would not settle for less.
That said, much of complexity theory tacitly relies upon P being different from NP: if P were to equal NP, many of the results would be meaningless. Officially, such results are stated as "if P$\neq$NP then X" (such results are known as conditional results). However, the perceived semantics is simply "X holds".
Sometimes the results need a strong assumption, "if A then X", for various different As. The weaker the A, the stronger the result. Some of the assumptions A don't enjoy widespread acceptance, for example the Unique Games Conjecture. Others are considered pretty likely, such as the (Strong) Exponential Time Hypothesis. All of these are stronger assumption than P$\neq$NP (that is, they imply that P$\neq$NP).
answered Sep 18 '15 at 15:23
-
$\begingroup$ Wonder if one can say then that the $P=NP$ as a problem tilted towards the solution of $P=NP$ as an equality is hype? That is, that just because it e.g. has "so many cool practical consequences", some people believe that it's more reasonable to believe $P=NP$, rather than $P≠NP$. The question I'm asking is really about this, which one, equality or inequality is more true from the perspective of the theory? $\endgroup$ – mavavilj Sep 18 '15 at 15:28
-
-
1$\begingroup$ Perhaps you'd be interested in this: cs.umd.edu/~gasarch/papers/poll.pdf. $\endgroup$ – Yuval Filmus Sep 18 '15 at 15:31
-
$\begingroup$ Wonder why the $P=NP$ has gained "so much" traction then? If it's readable form the theory that $P≠NP$ seems more reasonable, then why even pose the problem of "is $P=NP$"? $\endgroup$ – mavavilj Sep 18 '15 at 16:05
-
2$\begingroup$ It's exactly the same as posing the problem "is P$\neq$NP". $\endgroup$ – Yuval Filmus Sep 18 '15 at 17:05
3
$\begingroup$
$\endgroup$
What evidence suggests that P could be equal to NP?
This is simple: it seems counterintuitive, especially to a layperson, that a problem might be significantly harder to solve than to check.
Currently, most theoreticians believe that P$\not=$NP; that is, whatever evidence that they could be equal is not currently very strong.
Is it important whether P=NP?
Yes. This is incredibly important for many reasons.
On the one hand, if P=NP, this means that many tasks that we currently consider computationally infeasible will be feasible; an algorithm that solves an NP-complete problem in polynomial time would revolutionize the world.
On the other hand, many cryptographic techniques rely on certain problems being "hard." That is, they rely on the fact that solving the problem will take more resources (time and computation) than a cracker would reasonably possess. Obviously, the problems on which security is based need to be in NP (we must be able to guarantee that the provided solution is correct), but they should not be in P, since that would mean the solution is easy to reverse engineer. As it stands, most theoreticians believe that P$\not=$NP. However, until it is established one way or the other, we cannot actually guarantee our cryptographic security systems.
See: https://en.wikipedia.org/wiki/P_versus_NP_problem#Consequences_of_solution
-
1$\begingroup$ What I'm saying is is that I'm not convinced your proposed proof is sound; it seems to assume that we can derive and prove the time complexity of every algorithm that runs in PTIME, which is undecidable. $\endgroup$ – G. Bach Sep 18 '15 at 11:41
-
2$\begingroup$ "it seems counterintuitive [...] that a problem might be significantly harder to solve than to check." That doesn't sound counterintuitive at all. Consider sudoku: common experience says that it's near-trivial to check that a claimed solution is correct but that finding such a solution can take a significant amount of time. $\endgroup$ – David Richerby Sep 18 '15 at 12:22
-
$\begingroup$ Re: "it seems counterintuitive, especially to a layperson, that a problem might be significantly harder to solve than to check": I really don't think this is true. Laypeople have no difficulty recognizing that long division is much harder than multiplication, even though the latter can be (and is) used to check the former. I think the speculation that P = NP actually probably originated from the realization that DFAs and NFAs are equivalent. $\endgroup$ – ruakh Sep 18 '15 at 17:05
-
$\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Raphael♦ Sep 19 '15 at 9:58
-
2$\begingroup$ P vs NP may have less to do with effective cryptography than you think. Also, there is no reason to think that a discovered P-algorithm for an NP-hard problem would change much; if it had runtime in $\Theta(n^100)$, we'd stick to the efficient, weaker algorithms we already have. $\endgroup$ – Raphael♦ Sep 19 '15 at 10:03
