P, NP, NP-hard, NP-complete - Complete explanation

✅ P problems

In computational complexity theory, the class of problems that have polynomial-time algorithms using a deterministic Turing machine is called P problems.

✅ NP problems

An NP problem refers to a problem for which, given a solution, one can verify whether it is correct in polynomial time.
All P problems are also included in the set of NP problems.

✅ Reduction

Before we get into NP-hard problems, let’s study what reduction is.
When we compare the difficulty of two problems, we use the concept of reduction.
Let’s say there are two problems: A and B.
Suppose inputs to problem B can be reduced(transformed) into equivalent inputs to problem A and transformation time is negligible.
If we use the fastest solution to solve problem A, we can say that fastest solution of problem B is faster than problem A.
Therefore, we can define:

If problem B can be reduced to problem A, problem A is harder than problem B.

Coming back to our story… The SAT problem is the task of finding a combination of truth values for N Boolean variables that makes a given logical formula true. Any NP problems can be reduced to SAT problem meaning that SAT problem is at least as hard as any problem in NP.

✅ NP-Hard problems

A problem is NP-hard if every problem in NP can be reduced to it in polynomial time.’ NP-Hard problems are at least as hard as the hardest problems in NP.
Noone has ever yet solved NP-Hard problems in polynomial time, so they are strongly believed to be unsolvable in polynomial time.(They are literally hard.)
However, NP-Hard problems are not required to be in NP themselves, so their solution might not be verified in polynomial time.

✅ NP-Complete problems

NP-complete problems are the hardest problems in the class NP (nondeterministic polynomial time). A problem is NP-complete if it satisfies two conditions:

1. It’s in NP: This means if someone gives you a solution, you can verify it in polynomial time.
2. It’s NP-hard: This means every other problem in NP can be reduced to it in polynomial time.

🎓 Interesting Facts

In the year 2000, the Clay Mathematics Institute announced 7 of the most important and difficult open problems in mathematics. These are called the Millennium Prize Problems. For each problem, there’s a $1 million prize for a correct solution. One of the 7 problems include P vs NP problems.

The key question is:

If a problem can be verified quickly (in polynomial time), can it also be solved quickly (in polynomial time)?

No one has ever found a polynomial-time algorithm for an NP-complete problem (like SAT or 3-SAT). Over decades, people have tried and failed to find such algorithms. Some problems feel inherently hard, even though checking a solution is easy. So most computer scientists and mathematicians believe:

P ≠ NP, but no proof yet exists.

Reference

[1] Cook-Levin’s Theorem