Unit V - Computational Complexity Theory

1. Introduction to Computational Complexity

Computational Complexity Theory studies how efficiently problems can be solved. It classifies problems based on the resources (time, space) needed to solve them.

Why Study Complexity?

• Decidability vs Efficiency:
  • Computability theory: Can we solve it at all?
  • Complexity theory: Can we solve it efficiently?
• Practical Importance:
  • Some decidable problems take millions of years!
  • Need to distinguish "feasible" from "infeasible"
• Algorithm Design:
  • Know when to look for better algorithms
  • Know when to give up on exact solutions

Time Complexity:

Measured as a function of input size n:

• O(1): Constant time
• O(log n): Logarithmic (binary search)
• O(n): Linear (scanning array)
• O(n log n): Linearithmic (merge sort)
• O(n²): Quadratic (bubble sort)
• O(n³): Cubic (matrix multiplication)
• O(2ⁿ): Exponential (subset enumeration)
• O(n!): Factorial (traveling salesman brute force)

Polynomial vs Exponential:

Deterministic vs Nondeterministic:

• Deterministic TM: One transition per configuration (usual TM)
• Nondeterministic TM: Multiple transitions possible, can "guess" correctly

2. The Class P (Polynomial Time)

Characteristics of P:

• Efficient: Problems in P are considered "tractable"
• Closed under: Union, concatenation, star, complement
• Robust: Same class for different computational models (multi-tape TM, RAM)
• Practical: Can be solved on real computers

Properties of P:

1. Closed under complement: If L ∈ P, then L̄ ∈ P
2. Closed under union: If L₁, L₂ ∈ P, then L₁ ∪ L₂ ∈ P
3. Closed under intersection: L₁ ∩ L₂ ∈ P
4. Closed under concatenation: L₁ · L₂ ∈ P
5. Closed under Kleene star: L* ∈ P

3. The Class NP (Nondeterministic Polynomial Time)

Intuitive Understanding:

NP = "Easy to verify, but may be hard to solve"

• Solving: Finding the answer (may be hard)
• Verifying: Checking if given answer is correct (must be easy)

Relationship: P ⊆ NP

If we can solve in polynomial time, we can certainly verify in polynomial time!

• Just solve the problem and compare with certificate
• Therefore: P ⊆ NP

Properties of NP:

• ✓ Closed under union
• ✓ Closed under intersection
• ✓ Closed under concatenation
• ✓ Closed under Kleene star
• ? Closed under complement (unknown! Related to NP = co-NP?)

4. NP-Complete Problems

NP-Complete problems are the "hardest" problems in NP. They are the bottleneck of computational complexity theory.

Polynomial-Time Reduction:

Problem A reduces to problem B (written A ≤ₚ B) if:

• There's a polynomial-time computable function f such that:
• x ∈ A if and only if f(x) ∈ B
• Meaning: If we can solve B, we can solve A

Significance of NP-Completeness:

• If ANY NP-Complete problem is in P, then P = NP
• If ANY NP-Complete problem is NOT in P, then P ≠ NP
• All NP-Complete problems are "equally hard"
• Solving one efficiently means solving ALL efficiently

How to Prove NP-Completeness:

To prove problem L is NP-Complete:

1. Show L ∈ NP: Describe polynomial-time verifier
2. Show L is NP-Hard: Reduce known NP-Complete problem K to L
   • Choose known NP-Complete problem K
   • Show K ≤ₚ L (polynomial-time reduction)
   • Since K is NP-Hard and K ≤ₚ L, then L is NP-Hard

Common Reduction Chain:

SAT → 3-SAT → Clique → Vertex Cover → Hamiltonian Cycle → TSP
            

5. NP-Hard Problems

NP-Complete vs NP-Hard:

Complexity Hierarchy:

            All Problems
                  |
              NP-Hard (at least as hard as NP)
                  |
          +-------+-------+
          |               |
    NP-Complete      Harder than NP
    (NP ∩ NP-Hard)   (e.g., Halting Problem)
          |
          |
         NP (verifiable in polynomial time)
          |
          |
          P (solvable in polynomial time)
            

Approaches for NP-Hard Problems:

6. Hamiltonian Path Problem

The Hamiltonian Path Problem is a classic NP-Complete problem named after Irish mathematician William Rowan Hamilton.

Graph:
    A --- B
    |     |
    |     |
    D --- C

Hamiltonian Cycle: A → B → C → D → A
✓ Visits each vertex exactly once
                

Graph:
    A --- B --- C
    |           |
    D --- E --- F

Try all paths:
- Can't visit all vertices without repeating
- Vertices D and F have degree 1, need to be endpoints
- But can't connect them without revisiting
✗ No Hamiltonian path exists
                

Complexity:

• Hamiltonian Path: NP-Complete
• Hamiltonian Cycle: NP-Complete
• Brute Force: O(n!) - try all permutations
• Best Known: O(2ⁿ · n²) - dynamic programming
• No polynomial algorithm known!

Why NP-Complete?

1. In NP:
   • Certificate: The Hamiltonian path itself (sequence of vertices)
   • Verification: Check each vertex appears once - O(n), check edges exist - O(n)
   • Total: O(n) - polynomial!
2. NP-Hard:
   • Can reduce from 3-SAT or Vertex Cover
   • Standard reduction techniques exist

Special Cases (Polynomial Time):

Sufficient Conditions (Guarantee Hamiltonian Cycle):

• Dirac's Theorem (1952): If G has n ≥ 3 vertices and every vertex has degree ≥ n/2, then G has Hamiltonian cycle
• Ore's Theorem (1960): If for every pair of non-adjacent vertices u, v: deg(u) + deg(v) ≥ n, then G has Hamiltonian cycle

Applications:

• Route Planning: Visit all locations exactly once
• DNA Sequencing: Reconstruct sequence from fragments
• Circuit Board Design: Drill holes in optimal order
• Puzzle Solving: Knight's tour on chessboard

7. Traveling Salesman Problem (TSP)

The Traveling Salesman Problem is one of the most famous and well-studied optimization problems in computer science.

Cities and Distances:
    A -10- B
    |\    /|
   5| \  / |15
    |  \/  |
    | /  \ |
   20|/    \|12
    D -8-- C

Possible Tours:
1. A → B → C → D → A: 10 + 12 + 8 + 20 = 50
2. A → B → D → C → A: 10 + 15 + 8 + 18 = 51
3. A → C → B → D → A: 18 + 12 + 15 + 20 = 65
4. A → C → D → B → A: 18 + 8 + 15 + 10 = 51
5. A → D → B → C → A: 20 + 15 + 12 + 18 = 65
6. A → D → C → B → A: 20 + 8 + 12 + 10 = 50

Optimal Tours: #1 and #6 with cost 50
                

Complexity:

Algorithms and Approaches:

function BruteForceTSP(G):
    best_tour = null
    best_cost = ∞
    
    for each permutation P of vertices:
        cost = calculate_tour_cost(P)
        if cost < best_cost:
            best_cost = cost
            best_tour = P
    
    return best_tour, best_cost

Time: O(n!) - Infeasible for n > 20
                

function NearestNeighbor(G, start):
    current = start
    unvisited = V - {start}
    tour = [start]
    cost = 0
    
    while unvisited not empty:
        nearest = vertex in unvisited closest to current
        tour.append(nearest)
        cost += distance(current, nearest)
        current = nearest
        unvisited.remove(nearest)
    
    cost += distance(current, start)  // Return to start
    return tour, cost

Time: O(n²)
Approximation: No guarantee (can be arbitrarily bad)
                

Algorithm:
1. Find Minimum Spanning Tree (MST)
2. Do DFS traversal of MST (pre-order)
3. Take shortcut tour following DFS order

Guarantee: Tour ≤ 2 × OPT
Time: O(n²)
                

Approximation Algorithms:

Variants of TSP:

• Symmetric TSP: d(i,j) = d(j,i) (undirected)
• Asymmetric TSP: d(i,j) ≠ d(j,i) (directed)
• Metric TSP: Satisfies triangle inequality
• Euclidean TSP: Points in 2D plane, Euclidean distance
• Multiple TSP: Multiple salesmen, multiple tours
• TSP with Time Windows: Visit cities in time constraints

Real-World Applications:

• Logistics: Package delivery routes
• Manufacturing: PCB drilling, robot arm movement
• DNA Sequencing: Fragment assembly
• Astronomy: Telescope observation scheduling
• Transportation: Bus routes, airline scheduling
• Genome Mapping: Ordering DNA fragments

8. More Examples of NP-Complete and NP-Hard Problems

1. Vertex Cover Problem

Example Graph:
    A --- B --- C
    |     |     |
    D --- E --- F

Vertex Cover of size 3: {B, E, D}
✓ All edges covered
                

2. Clique Problem

Example Graph:
    A --- B
    |\ /| 
    | X |
    |/ \|
    D ---C

Clique of size 4: {A, B, C, D}
✓ All pairs connected
                

3. Graph Coloring

Example - 3-Coloring:
    A(R) --- B(G)
     |   X   |
     |  / \  |
    D(B) --- C(R)

✓ Valid 3-coloring: Red, Green, Blue
No adjacent vertices share color
                

4. Subset Sum Problem

Example:
S = {3, 34, 4, 12, 5, 2}
T = 9

Solution: {4, 5} or {3, 4, 2}
Both sum to 9 ✓
                

5. Knapsack Problem

Example:
Items: [(weight, value)]
  Item 1: (2, 3)
  Item 2: (3, 4)
  Item 3: (4, 5)
  Item 4: (5, 6)
Capacity: W = 8

Optimal: Items 1, 2, 4
Weight: 2 + 3 + 5 = 10 > 8 ✗

Try: Items 2, 3
Weight: 3 + 4 = 7 ≤ 8 ✓
Value: 4 + 5 = 9
                

6. Boolean Satisfiability (SAT)

Example - 3-SAT:
F = (x₁ ∨ ¬x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ x₄) ∧ (¬x₃ ∨ ¬x₄ ∨ x₁)

Solution: x₁=T, x₂=T, x₃=T, x₄=F
Check:
  (T ∨ F ∨ T) = T ✓
  (F ∨ T ∨ F) = T ✓
  (F ∨ T ∨ T) = T ✓
Result: T ∧ T ∧ T = T ✓ Satisfiable!
                

Summary Table:

⚡ Quick Revision (Unit V Cheat Sheet)