How to prove P=NP ? (Theoretically)

There is nothing like an unsolved problem and sure isn’t there something beautiful about P?=NP? I will admit right away, that I am on the side of the underdog, I would think it to be magically ironic if proof came into existence of P=NP. One of those major events to tell your grandchildren about.

Introducing P vs NP

To introduce this topic we will follow the definitions in Combinatorial Optimization by Jens Vygen, and Bernhard Korte [1]. A decision problem is any problem that can be answered with a single yes/no. One such example is: given a number of cities on a map, can you find a tour that visits each city only once follows established roads, and returns to the starting town? In many cases, it is hard to answer such a question but if you are given the answer it is almost trivial to verify that it is true. Formally, the complexity class NP is defined such that a solution to a decision problem can be verified in polynomial time.

If the problem is also solvable deterministically in polynomial time, by known algorithms, it belongs to the class P. A big research question in computer science is whether all problems in NP also are solvable in polynomial time, that is P?=NP.

As of now there are many problems that it is unknown whether they can be solved in polynomial time specifically there is a class of NP-complete problems that have a few important properties in complexity theory. A problem that belongs to the class of NP-complete problems has the property that all problems in NP are polynomially reducible to the NP-complete problem. In other words, for all problems in NP, there is a polynomial-time algorithm that transforms any instance into an instance of the NP-complete problem.

Any algorithm which solves one of the NP-complete problems in polynomial time can therefore solve the entire class of NP problems. This is huge! It is also provable that P ⊆ NP which means that there is a possibility that these complexity classes are the same. There is, however, great doubt in computer science that this would be the case and in practice, approximation schemes are common for problems without known polynomial algorithms.

Proving P=NP

The consequences of P=NP, are predicted to be great, especially in the field of cryptography where many security protocols are built on the fact that some problems are not solvable quickly. But if it was the case, if P=NP, how could one prove it?

1. Giving the magical algorithm which solves one NP-complete problem i.e. a constructive proof
2. Proving the existence of such an algorithm

If we only know of the existence of an algorithm, this is monumental, but in practice it changes very little because we are not much closer to finding an efficient algorithm. It would, however, induce great motivation for finding it.

The arguments against P=NP

In practice, few actually believe that P=NP. Scott Aaronson [2], professor in complexity at the University of Austin Texas, brings up a few important points as to why the consensus within computer science is that P and NP are two different complexity classes. The first is that the running times for problems in NP that are not in P are different. Even with loads of research, the best algorithms have exponential running times with no proof of existence for polynomial ones. There is also a hypothesis that a famous NP-complete problem the 3-SAT problem has at least an exponential running time.

The second argument against P=NP is more obscure. The question of whether P=NP, is posed such that: is there a single algorithm that for all n, can solve the problem in polynomial time [2]. For some problems, it may be the case that an algorithm can solve it in polynomial time for a specific size n. What if there is a slightly different algorithm for every input size, together composing the fastest algorithm of a problem?

How to prove P≠NP

Proving P≠NP does not seem to be an easy feat regardless of this [2]. Aaronson means that we cannot argue for the hardness of the problems not in P because most arguments would also apply to some problems in P. Furthermore, we cannot assume that some problems are not solvable faster than they seem to be. Here, matrix multiplication is an example that was long believed to need cubic complexity but new results have given much faster algorithms. A key here is to explain the border between polynomial and non-polynomial algorithms.

In conclusion, there are still more questions than there are answers on this topic and I look forward to new research on this topic. I am particularly interested in the progress to be made in approximating hard problems with deep learning.

References

[1] Jens Vygen, Bernhard Korte. Combinatorial Optimization. Theory and Algorithms. 2nd. Algorithms and Combinatorics. Springer, 2002.

[2] Scott Aaronsson. P?=NP. https://www.scottaaronson.com/papers/pnp.pdf, accessed 2023–03–01.