📘 Complexity Classes: P, NP, NP-Hard, NP-Complete
1️⃣ Introduction
In computational complexity theory, problems are classified based on how efficiently they can be solved.
The most important classes are:
- P (Polynomial time)
- NP (Non-deterministic Polynomial time)
- NP-Hard
- NP-Complete
These classes help us understand:
- Which problems are easy
- Which are hard
- Which are unsolvable efficiently
📗 2️⃣ Class P (Polynomial Time)
🔹 Definition
Class P consists of all problems that can be solved in polynomial time by a deterministic algorithm.
[
O(n),; O(n^2),; O(n^3),; O(n \log n)
]
🔹 Characteristics
✔ Efficient and tractable
✔ Solvable in reasonable time
✔ Deterministic algorithms used
🔹 Examples
- Linear Search
- Binary Search
- Merge Sort
- Shortest Path (Dijkstra)
📘 3️⃣ Class NP (Non-deterministic Polynomial Time)
🔹 Definition
Class NP consists of problems for which a given solution can be verified in polynomial time.
It may be difficult to find the solution, but easy to verify it.
🔹 Characteristics
✔ Solution verification is fast
✔ Solution finding may be slow
✔ Uses non-deterministic model
🔹 Examples
- Traveling Salesperson (decision version)
- Subset Sum
- Hamiltonian Cycle
📙 4️⃣ NP-Hard Problems
🔹 Definition
A problem is NP-Hard if:
It is at least as hard as the hardest problems in NP.
- Not necessarily in NP
- May not be decision problems
- May not have polynomial-time verification
🔹 Characteristics
✔ Very difficult problems
✔ No known efficient solution
✔ May be optimization problems
🔹 Examples
- Traveling Salesperson (optimization version)
- Halting Problem
- Scheduling problems
📕 5️⃣ NP-Complete Problems
🔹 Definition
A problem is NP-Complete if:
- It belongs to NP
- It is NP-Hard
🔹 Meaning
- Hardest problems in NP
- If one NP-Complete problem is solved in polynomial time → all NP problems can be solved in polynomial time
🔹 Examples
- SAT (Boolean Satisfiability Problem)
- Subset Sum
- Clique Problem
- Vertex Cover
- Hamiltonian Cycle
📊 6️⃣ Relationship Between Classes
P ⊆ NP
NP-Complete ⊆ NP
NP-Hard ⊇ NP-Complete
👉 Key idea:
- All P problems are in NP
- NP-Complete problems are hardest in NP
- NP-Hard includes even harder problems
📌 7️⃣ P vs NP Problem
- Biggest open problem in computer science
- Question:
Is P = NP?
✔ If YES:
- All NP problems become easy
✔ If NO:
- Some problems are inherently hard
📊 8️⃣ Summary Table
| Class | Meaning | Solvable? | Verifiable? |
|---|---|---|---|
| P | Easy problems | ✔ Yes | ✔ Yes |
| NP | Verifiable problems | ❓ Unknown | ✔ Yes |
| NP-Hard | Very hard problems | ❓ Unknown | ❌ Not always |
| NP-Complete | Hardest in NP | ❓ Unknown | ✔ Yes |
🔟 Key Differences
| Feature | P | NP | NP-Hard | NP-Complete |
|---|---|---|---|---|
| Solution time | Polynomial | Unknown | Unknown | Unknown |
| Verification | Easy | Easy | Not always | Easy |
| Type | Easy | Medium | Hard | Very Hard |
🔚 Conclusion
The classification of problems into P, NP, NP-Hard, and NP-Complete helps us understand the limits of computation.
NP-Complete problems are the most critical, as solving one efficiently would solve all NP problems efficiently.
📌 Exam Tip
👉 Always include:
- Definitions
- Examples
- Relationship diagram
- P vs NP statement