1.
Relationship Between NP-Hard, NP-Complete, and P Problems
In computational complexity theory, decision problems (yes/no problems) are grouped
into classes based on their difficulty and the resources needed to solve or verify them.
The key classes are P, NP, NP-Complete, and NP-Hard.
a. Class P:
Problems that can be solved in polynomial time by a deterministic Turing machine.
Examples: Sorting a list (e.g., Merge Sort runs in O(n log n)), Shortest path in a graph
(Dijkstra’s algorithm).
b. Class NP:
Problems for which a solution can be verified in polynomial time by a deterministic
Turing machine.
"NP" stands for Nondeterministic Polynomial time.
Example: Subset Sum Problem – Given a set of numbers, is there a subset that adds up to
a target value? Given a proposed subset, you can check if it adds to the target in
polynomial time.
c. NP-Complete:
These are the hardest problems in NP.
A problem is NP-Complete if:
1. It is in NP.
2. Every other problem in NP can be reduced to it in polynomial time.
Example: SAT (Boolean Satisfiability Problem) – Given a Boolean formula, is there an
assignment of variables that makes the formula true?
d. NP-Hard:
These are problems at least as hard as NP-complete problems, but not necessarily in NP.
They include optimization problems and problems not even decision-based.
Example: Traveling Salesman Problem (TSP) – Find the shortest route visiting all cities.
Visual Summary:
All P problems ⊆ NP
NP-Complete ⊆ NP
NP-Hard ⊇ NP-Complete
Some NP-Hard problems ∉ NP
2. Does P = NP or P ≠ NP?
As of now (2025), it is not known whether P = NP or P ≠ NP. It is one of the seven
Millennium Prize Problems, and solving it yields a $1 million reward.
However, most computer scientists believe that P ≠ NP.
Example: 3-SAT Problem
Input: A Boolean formula in 3-CNF (each clause has 3 literals).
Goal: Is there a way to assign TRUE/FALSE to variables to satisfy the formula?
Verification is easy:
If someone gives you a truth assignment, you can plug it into the formula and verify in
polynomial time whether the formula is true.
No polynomial-time algorithm is known to solve 3-SAT for all cases.
If P = NP, there would be an efficient algorithm that solves 3-SAT quickly.
But after decades of research, no such algorithm has been found.
Why this matters:
If P = NP, encryption algorithms (like RSA) would break, because problems like integer
factorization would be easy.
Yet, encryption still works in practice, which supports the belief that P ≠ NP.
Summary Table:
| Class | Contains Problems That… | Example |
|-------------|------------------------------------------------|--------------------------|
|P | Can be solved in polynomial time | Sorting, Shortest Path |
| NP | Can be verified in polynomial time | Subset Sum |
| NP-Complete | Are in NP and as hard as any NP problem | SAT, 3-SAT |
| NP-Hard | As hard as NP-Complete but not necessarily in NP | TSP (optimization),
Halting Problem |
Most experts believe P ≠ NP, but it is not yet proven.
If any NP-Complete problem is found to be solvable in polynomial time, then P = NP.
Otherwise, P ≠ NP.
