What is the evidence that P could equal NP?

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?

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.

1. 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?

1. (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.

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

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

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

1. 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?

StackExchange Computer Science Q#47300, answer score: 7