P=NP, or rather P$\ne$NP, is one of the most famous examples of a currently unresolved problem in Computer Science, but that does not mean that there have not been attempts. Here we will explain the problem and look at some of the many ways it has been attempted to be solved.

The Question of P$\ne$NP

This problem has to do with the computational complexity of algorithms. We can talk about complexity on an increasing scale; the least complex are ones which can be solved in less than or equal to a polynomial time. We refer to these types of problems as P. There are also problems which can be solved in less than or equal to exponential time, referred to as EXP problems. As the complexity increases, the levels also encapsulate those below them; this means that P problems are a subset of EXP problems.

Now, what are NP problems? These are a type of decision problem, normally solved by exponential methods, that can be solved by lucky guesses. At any stage when an algorithm has to make a decision, it makes a guess, and this series of guesses is guaranteed to lead to a successful answer if this is possible.

The question of P=NP is to determine whether polynomial problems can be solved in the same amount of time as NP (non-deterministic polynomial) problems. Some may say that NP problems can be considered as polynomial because following one distinct route at each stage, rather than trying every possible route, only requires a number of guesses which is polynomial. A problem is NP-complete if it is within the set of NP problems, and also NP-hard, which means that it is at least as hard as all other NP problems.

One would be lead to believe that these are not, in fact, equal, as solving problems in an NP way clearly seems unrealistic and not reliable. Yet, the problem has still not been proven. However, if it can be shown that one NP-complete problem can be solved in polynomial time, since some NP-complete problems can be reduced to each other, all decisions in this subset can be solved in polynomial time, which would be a large breakthrough for problems previously only considered to be solvable in exponential time.

The problem is considered so important that it is one of the seven Millennium Prize Problems, a set of problems organised by the Clay Mathematics Institute, with a prize of $1 million for solving the problem. Only one of these problems, the Poincaré Conjecture, has so far been proved.

Attempts to Solve

There have been many attempts to prove, disprove and prove this problem unsolvable. Late mathematician Gerhard J. Woeginger compiled a list of attempts to solve this problem up until 2016, which consisted of 116 entries, however the actual number has undoubtedly increased since then. Most of these attempts differ in manner wildly from another, yet all of these attempts have so far been refuted. We will have a brief look at some of these proofs which are particularly interesting.

In a 2016 paper, Frank Vega showed that assuming that P=NP was true implied that P=EXP was true using Boolean algebra. Since it is provably true that P$\ne$EXP, it could therefore be shown that P$\ne$NP. Another attempt to prove that they are not equal was by Hubie Chen, presenting a rather simple proof by contradiction based on the fact that it had not yet been solved.

Many of the attempts to prove that they are equal focus on proving that one NP problem can be solved in polynomial time, as other problems can be reduced to it and thus P would be equal to NP; this way of solving the problem is obviously something more difficult when proving the other way around. Many solutions focus on solving the SAT problem, which was also the first problem proven to be NP-complete. For this problem, it needs to be found out whether there is some arrangement of true or false values that can be assigned to the variables of a given Boolean expression to make it true. You can quite easily tell by looking that it that it could be solved by an exponential method, but in order to prove that P=NP an algorithm must be found which can do this in polynomial time. Matt Groff used linear algebra in a 2011 paper to show that it could be solved in O($n^7$), and around the same time Sergey Kardash presented an algorithm which could solve it in O($n^{12}$) time.

However, attempts have still been made to prove that P is not equal to NP using a single problem. In a 2011 paper, Roman V. Yampolskiy showed a type of problem known as the Hashed-Path Travelling Salesman Problem, showed it to be in the class NP and showed that it had no polynomial time solutions, showing that P cannot be equal to NP.

As you can see, even after so many attempts to resolve this problem using varied techniques, this problem is still very much unsolved. Unless you are convinced you have an answer, do not fall into the trap of spending years finding a solution!