P vs. NP is a millenium-prize problem in Computer Science that has not been proven yet. Are all P in NP? Or are all NP in P? What is NP-Complete?

P vs. NP

When we talk about P or NP, we generally talk about decision problems, which means the algorithms always output a "yes" or a "no". Abstract versions of these problems can include things like a solution to a chess game, or figuring out if a number is a prime.

P and NP represent complexity classes, which is a set of problems of related resource-based complexity.

What is P?

P stands for polynomial time. Thus, the problems in the P set are solvable in the worst-case in polynomial time. A function such as \(f(x) = n^2 + 3n - 4\) is polynomial. A function such as \(f(x) = 2^n\) is not.

We can say that problems in P are solved quickly with computers. This is a general assumption and it may not be so "quick" in practice, but P solutions are the most desirable because we know that they are the most optimal of their kind!

What is NP?

NP stands for non-deterministic polynomial time. NP problems are also restricted to decision problems.

The "non-deterministic" part in the name is based on an unrealistic non-deterministic model (Turing machine) that gives us a good guess out of many, many options in constant time, that leads to a "yes". In other words, NP is the set of all problems for which the instances where the answer is "yes" have efficiently verifiable proofs.

This means that if solving a Chess board is an NP problem (which it is, because Chess is currently unsolvable), and a solution to a chess board is given, then at the very least, we can check that the solution is correct in an efficient amount of time.

Note that NP is a superset of P. This means that all P problems are automatically in the NP set, because P problems can also check their solutions efficiently (on top of being able to search for a solution efficiently).

NP (the gray circle) is a big set. Unlike problems in P (the green circle), some NP problems can have a big \(?\) in the worst-case time of problems. These problems cannot be solved optimally or an efficient solution cannot be found.

The complex problems in NP include things like circuit design, \(n \times n\) Sudoku/Rubix Cube, and vehicle routing.

What is NP-Hard?

NP-Hard problems are "at least as hard as the hardest problems in NP". This means some NP-Hard problems are in NP, while there are others that are not in NP, i.e. they are so hard that their solution can't be proven efficiently, or they are outside the realm of decision problems.

This means finding a polynomial algorithm to solve any NP-Hard problem would give polynomial algorithms for all the problems in NP.

If you have a NP-Hard problem and you cracked an optimal solution for it, congrats! You unlocked the key to solving all of the problems in NP.

Realistically speaking, there is no polynomial time solution for any NP-Hard problem. However, this has not been proven.

What is NP-Complete?

NP-Complete problems are both in NP and NP-Hard. They are as difficult as the hardest problems of NP.

NP-Complete is a complexity class which represents the set of all problems \(X\) in NP for which it is possible to reduce any other NP problem \(Y\) to \(X\) in polynomial time. This means that if \(X\) is solved in polynomial time, then \(Y\) is also solved in polynomial time.

That property alone makes NP-Complete very important. If a deterministic polynomial time algorithm can be found to solve one NP-Complete problem, then every NP problem is solvable in polynomial time (by reducing them).

Similar to NP-Hard, in reality there is no polynomial time solution for any NP-Complete problem (unproven).

Summary

P vs. NP is the big debate on whether or not P = NP or P != NP.

Neither has been proven to this day, but if you succeed to prove that P = NP, then you might cause the world to shift a little bit.

The reality that we live in promotes the belief that P != NP, because many complex problems are believed to have no optimal solution. Yet, if P = NP, then we will be able to engineer "luck" magically and solve complex algorithms in deterministic time. We will be able to solve NP-Complete problems in polynomial time! This means we'll be able to cure cancer. This would also mean that all forms of public-key cryptography and security would be crackable.

P vs. NP is still a big mystery, but if it is solved, then the world will definitely change very fast.