Senior LevelData Structures & Algorithms
What are P, NP, NP-Complete, and NP-Hard complexity classes?
❓ Interview Prompt: Explain P vs NP, NP-Completeness, polynomial-time reductions, and famous NP-Complete problems.
Complexity Classes:
•
P: Problems solvable in polynomial time $O(N^k)$ — e.g., Sorting, Shortest Path.
•
NP: Problems whose solutions can be verified in polynomial time — e.g., TSP, Subset Sum, SAT.
•
NP-Complete: NP problems that are as hard as all other NP problems (every NP problem reduces to them in polynomial time).
•
NP-Hard: At least as hard as NP-Complete; may not even be in NP (e.g., Halting Problem).
P vs NP (Millennium Prize Problem):
Is $P = NP$? If so, every verifiable problem is efficiently solvable. Most believe $P \neq NP$.
Famous NP-Complete Problems:
SAT, 3-SAT, TSP (decision), Knapsack (decision), Graph Colouring, Clique, Hamiltonian Path.
Code Implementation Example
markdown
Complexity Class Hierarchy:
┌──────────────────────────────────────────┐
│ NP-Hard │
│ ┌────────────────────────────────────┐ │
│ │ NP-Complete │ │
│ │ ┌───────────────────────────────┐ │ │
│ │ │ NP │ │ │
│ │ │ ┌─────────────────────────┐ │ │ │
│ │ │ │ P │ │ │ │
│ │ │ │ Sorting, Dijkstra, │ │ │ │
│ │ │ │ BFS, Matrix Multiply │ │ │ │
│ │ │ └─────────────────────────┘ │ │ │
│ │ │ TSP (verify), 3-SAT, Knapsack│ │ │
│ │ └───────────────────────────────┘ │ │
│ │ TSP (decision), SAT, Hamiltonian │ │
│ └────────────────────────────────────┘ │
│ Halting Problem, Chess, Go (unbounded) │
└──────────────────────────────────────────┘💡P ⊆ NP ⊆ NP-Complete ⊆ NP-Hard complexity class hierarchy.
🎯 Interview Key Takeaway
For NP-Complete problems, use approximation algorithms, heuristics, or bitmask DP for small N. Proving P=NP would revolutionise cryptography and AI.
#DSA#NP-Complete#Complexity Theory#P vs NP#Senior
Back to all Data Structures & Algorithms Questions→