i) P Problems
Class P is the set of decision problems that can be solved in polynomial time by a deterministic algorithm.
That means the algorithm’s time complexity is in O(p(n)), where p(n) is a polynomial of the input size n.
These problems are considered tractable, meaning they are efficiently solvable.
Examples:
- Sorting a list of numbers (e.g., using Merge Sort – O(n log n))
- Finding the greatest common divisor of two integers
- Finding the shortest path in a graph (e.g., Dijkstra’s algorithm)
- Searching a key in a list (e.g., Binary Search – O(log n))
ii) NP Problems
Class NP (Nondeterministic Polynomial time) is the class of decision problems for which a given solution can be verified in polynomial time by a deterministic algorithm.
These problems may not be solvable in polynomial time, but if someone gives a solution (called a certificate), we can verify it quickly.
A problem is in NP if it can be solved by a nondeterministic polynomial-time algorithm, which works in two stages:
- Guessing Stage: Randomly guesses a candidate solution.
- Verification Stage: Deterministically checks if the guess is a valid solution in polynomial time.
Relationship:
All problems in P are also in NP, since solving a problem also allows verifying it.
So, P ⊆ NP
Examples:
- Hamiltonian Circuit Problem – Does a graph have a cycle that visits every vertex exactly once?
- Subset Sum Problem – Can a subset of given integers sum to a target value?
- Traveling Salesman Problem (Decision version) – Is there a tour of all cities with cost ≤ k?
- Graph Coloring (m-coloring) – Can a graph be colored with at most m colors such that no two adjacent vertices have the same color?
iii) NP-Complete Problems
A decision problem D is NP-Complete if:
- D ∈ NP
- Every problem in NP can be polynomially reduced to D
That means:
An NP-complete problem is the hardest among all problems in NP.
If we can find a polynomial-time algorithm for any one NP-complete problem, all problems in NP can also be solved in polynomial time — i.e., P = NP.
Polynomial Reduction:
Problem D₁ is reducible to D₂ if we can convert any instance of D₁ into an instance of D₂ in polynomial time.
First Known NP-Complete Problem:
- CNF-Satisfiability (SAT) problem – Given a Boolean expression in CNF, can we assign true/false values to variables to make the expression true?
Proven by Stephen Cook in 1971 (Cook-Levin Theorem).
Examples of NP-Complete Problems:
- SAT (Boolean Satisfiability Problem)
- 3-SAT
- Traveling Salesman Problem (Decision Version)
- Hamiltonian Circuit Problem
- Knapsack Problem (Decision Version)
- Graph Coloring (m-coloring problem)
- Partition Problem
- Bin Packing Problem
iv) NP-Hard Problems
A problem H is NP-Hard if every problem in NP is polynomially reducible to H, but H may or may not be in NP.
- NP-Hard problems are at least as hard as NP-complete problems.
- They are not required to be decision problems.
- Verifying a solution may not be possible in polynomial time.
If a polynomial-time algorithm is found for any NP-Hard problem, all NP problems can be solved in polynomial time.
Examples of NP-Hard Problems:
- Halting Problem – Given a program and input, will it halt or run forever? (This is undecidable)
- Optimization version of Traveling Salesman Problem – Find the shortest tour, not just whether one exists under a cost.
- Integer Programming (Optimization version)
- Scheduling Problems – Assign tasks to machines with resource constraints.