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?
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Don Knuth believes that P=NP (q17). $\endgroup$ – Raphael♦ Sep 19 '15 at 10:12
Add a comment
|
$\begingroup$
$\endgroup$
8
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
-
2$\begingroup$ It's exactly the same as posing the problem "is P$\neq$NP". $\endgroup$ – Yuval Filmus Sep 18 '15 at 17:05
-
2$\begingroup$ @vzn you're taking my analogy too far... $\endgroup$ – Yuval Filmus Sep 21 '15 at 4:02
$\begingroup$
$\endgroup$
5
Without taking any stance, here are 7 arguments I made to help you believe that P = NP is possible:
1. Primes is in P
AKS primality test has $O(\log(n)^6)$ complexity. Here, the complexity of solving does not increase exponentially with the size of the input. However, multiplication is (either naïvely or correctly?) assumed to be a one-way function.
2. Problems that are easy to solve can seem very hard to solve
XOR-SAT, and more generally systems of linear equations, are very easy to solve using Gaussian Elimination. But if you express the exact same problems in SAT, now they seem to be hard because you have no algorithm that wants to deal with SAT.
Why should it be impossible to find an algorithm that would solve at least all the "easy" SAT formulas (2SAT, linear problems, etc...) in polynomial time? In other words, we can't even automatically recognize and solve the problems, that we know are easy. And if you can find such a general algorithm for all "easy" problems, why couldn't it be tweaked to deal with the "random" problems? Where does the difficulty actually begin and how to measure it?
3. (2SAT + XOR-SAT) is NP-complete
Both 2SAT and XOR-SAT are in P. They can only express "simple" problems. But the combination (a formula that allows both 2SAT and XOR-SAT clauses) is NP-complete. It shows that simple information can express any problem in NP without using 3SAT or k-SAT.
4. The arguments commonly used to argue that SAT is hard, could be used to argue that 2SAT or XOR-SAT are hard
This is a classic way to shoot down a failed P != NP proof. Use the arguments of the author to show that an easy problem would be very hard, should their arguments be fair...
- A number of different assignments that is exponential in the number of variables? Also in XOR-SAT.
- The inefficiency of checking the assignments one by one? Also in XOR-SAT.
- The high dependency between all variables? Also in XOR-SAT.
- The inefficiency of testing the variables separately? Also in XOR-SAT.
- The clauses can be combined together in a combinatorial amount of ways, and the combinations can be combined as well, in a completely chaotic way if that's what you want to do? Also in XOR-SAT.
- There seems to be no algorithm that can solve it in polynomial time? Well if you haven't been taught about Gaussian Elimination, surely you are in trouble when trying to find a satisfying assignment for XOR-SAT. You can try to run a SAT solver that tries to build random assignments on the system of linear equations, and it will fail in a spectacular way. The exponential complexity only proves that you are obviously using the wrong method, not that there is no correct method.
5. No one is able to prove P != NP so far
If random hard problems in NP are so obviously irreducibly combinatorial, why should the difficulty of proving it be so hard, that no one has done it yet? (I know the argument is often used the other way around). After all, there is also a big reward (1 million dollars) for the first person who can speak elegantly about this problem. If it the difficulty of NP is so obviously real, why is no one speaking elegantly about it?
It was very easy to demonstrate that EXPTIME and P are different. The reason why P != NP is so hard to prove, could be that it's false.
6. Finding algorithms takes effort and motivation
Human beings are limited by time, energy, money... If the best algorithm for a NP-complete problem is difficult to construct (thousands of lines of code, involving various advanced original concepts), then the effort required to unravel the truth in this direction could be high. If on top of that, no one actually believes that P = NP is possible, then no one is going to invest the required effort to even think about it.
7. The consequences are mind-blowing, but not impossible to imagine
Obviously if P=NP, then a lot of assumptions will go away. Cryptography doesn't work. The value of cryptocurrency will be zero. You can't protect any secret or communication using only mathematics, in plain sight of everyone. You can "design" all sort of amazing things just by describing their characteristics through satisfiability. You can quickly train AI to be better than humans at everything.
The consequences are mind blowing, but still easy to imagine. You would be able to solve quickly anything you can verify quickly, but... nothing more. You would not get any unbelievable extra-physical ability. Your computer would not break the laws of physics. There would be still be plenty of unsolvable problems in EXPTIME because the solution cannot be verified quickly.
P = NP would be said to be magic. But P != NP is also magic. You can protect your secrets and your bitcoins, in plain sight of everyone (providing the verification function publicly), with no possible counterforce. Why isn't that hard to believe?
-
$\begingroup$ "Obviously if P=NP, then a lot of assumptions will go away. Cryptography doesn't work." I would be a bit more nuanced here. If P=NP ("Algorithmica" with the vocabulary of Russell Impagliazzo's five worlds), some cryptography is still possible. There is a significant community working on information-theoretic (and unconditionally secure) cryptography. Additionally there are some works on basing security/privacy on non-mathematical assumptions, and instead leveraging noisy channels or anonymity (e.g. eprint.iacr.org/2006/084.pdf). $\endgroup$ – integrator Oct 16 '20 at 9:36
-
$\begingroup$ Some of your points (2,3,4) seem to imply that we know very little about the difference between 2SAT and 3SAT, or why 3SAT is hard. One particular line of research of 3SAT may be relevant: the "phase transition" phenomenon between easy and hard random instances. The phase transition phenomenon is well understood for the simple 2SAT, but not so much for 3SAT, see these slides, for example. In general, it seems many of your points are attacking arguments in favor of P!=NP, rather than giving an argument for P=NP. $\endgroup$ – Discrete lizard♦ Oct 16 '20 at 12:42
-
1$\begingroup$ Absurdly large order (googolplex?) polynomials would still be "hard" enough to allow practical cryptography. $\endgroup$ – Paul A. Clayton Oct 16 '20 at 13:41
-
$\begingroup$ IMO, if P was equal to NP, the complexity of solving SAT would likely be on the order of N^4 (based on the complexity of primality testing). It does not make sense to think about large polynomials because if a problem takes N^1000 to solve why wouldn't another take N^1001 ? If the order climbs to the sky, there no reason for the complexity to stop there and not reach exponentiality. N^3 on the other hand seems too little because that's already the complexity of basic linear problems. $\endgroup$ – d3m4nz3 Oct 16 '20 at 23:25
-
$\begingroup$ @PaulA.Clayton you don't need that large exponents. Exponent of 10 is enough in order for it to not have any practical use. $\endgroup$ – Tomer Wolberg Oct 18 '20 at 16:05
$\begingroup$
$\endgroup$
7
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
-
3$\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
-
1$\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
-
3$\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
$\begingroup$
$\endgroup$
I think that Time Hierarchy Theorem can be an argument in favor of $P = NP$: there exist problems which can't be solved in time $O(n^{100})$, but can be solved in time $O(n^{101})$. I didn't see arguments why SAT can't be one of such problems.
The common argument is that there are tons of NP-complete problems, and for none of them we have a polynomial-time algorithm, but when was the last time you've seen the algorithm with complexity greater than, say, $n^{20}$? Since we've only learned how to design efficient algorithms, it makes sense that we haven't learned how to design inefficient ones.
$\begingroup$
$\endgroup$
Regardless of whether or not P=NP unlike what the other answers seems to claim this problem is way too much over hyped.
Why it doesn't matter if P = NP (at least in the practical sense)
People think the P,NP problem is an important question because they think that if someone would solve an NP complete problem in polynomial time it would change the world or something like that when in reality it would probably only change the life of the person who solved it because of the 1 million dollars prize. The reason people think it matters is because they don't understand how fast exponential growth actually grows, because in every reduction the exponent grows (multiplied by a constant) so even if in the end the exponent would be constant it would still be exponential in this constant and even if this constant would be small (like 10) it won't have any practical use what so ever, and for each other problem the constant would get bigger. If the constant would be extremely small (like 1) for specific NP-complete problem it might be practical to solve this exact problem but not other NP problems (since the exponent is multiplied in each reduction).
When it might be useful
If someone would solve a very fundamental NP-complete problem (like SAT) with extremely small exponent and not too big constant multiplier. In that particular case it really can revolutionize the world, however most people mistakenly thinks that it's enough if someone would solve any NP-complete problem in a polynomial time. But even in this case it's not that it's useful because it solves the P,NP problem but because it gives a fast solution for a very useful problem.
