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?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityWhat 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?
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).
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...
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?
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
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.
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.