Computational Complexity: Classes, Intractability & Turing Machines

TAKEAWAYS:

• Understand time and space complexity of Turing machines and how they measure computational effort.
• Master Big-O, Big-Ω, and Big-Θ notations to classify algorithmic efficiency.
• Differentiate P, NP, and NP-Complete classes and why some problems are "hard."
• Learn why SAT is NP-Complete and how it models real-world decision problems.
• Apply intractability concepts to explain why some problems cannot be solved efficiently.
• Connect theory to practice via real-world examples (e.g., eSewa’s order processing, Ncell’s routing).

1. Computational Complexity: Definitions and Basics

Computational complexity studies how resources (time, space) grow as input size increases. For Turing machines (TMs), we measure:

• Time complexity: Number of steps a TM takes to solve a problem.
• Space complexity: Maximum memory (tape cells) used during computation.

Big-O, Big-Ω, and Big-Θ Notations

These notations describe algorithmic growth rates:

• Big-O (O): Upper bound (worst-case). Example: $O(n^2)$ for nested loops.
• Big-Ω (Ω): Lower bound (best-case). Example: $\Omega (n)$ for linear scans.
• Big-Θ (Θ): Tight bound (exact). Example: $\Theta (n\log n)$ for efficient sorts.

graph LR
    A["Big-O (Upper Bound)"] -->|"O(n²)"| B["Worst-case"]
    C["Big-Ω (Lower Bound)"] -->|"Ω(n)"| D["Best-case"]
    E["Big-Θ (Tight Bound)"] -->|"Θ(n log n)"| F["Exact"]

Example: For a TM that checks if a string is a palindrome:

• Time: $O(n)$ (read each character once).
• Space: $O(1)$ (constant extra memory).

2. Complexity Classes: P, NP, and NP-Complete

P (Polynomial Time)

• Problems solvable in polynomial time (e.g., $O(n^2)$).
• Example: Sorting a list (quicksort is $O(n\log n)$).

NP (Nondeterministic Polynomial Time)

• Problems where solutions can be verified quickly (but may not be found quickly).
• Example: SAT (Boolean satisfiability): Given a formula, can we assign truth values to make it true?
  • Verification: Check if a given assignment works in $O(n)$.
  • Finding a solution: May take exponential time.

NP-Complete

• Hardest problems in NP: If one NP-complete problem is solved in polynomial time, all NP problems are solvable efficiently (P = NP).
• Example: Traveling Salesman Problem (TSP): Find the shortest route visiting all cities once.
  • Real-world tie: NTC’s route optimization for buses could use TSP approximations.

classDiagram
    class P {
        +Solvable in polynomial time
    }
    class NP {
        +Solutions verifiable in polynomial time
    }
    class NPComplete {
        +Hardest in NP
        +P = NP if one is solved in poly time
    }
    P --> NP : Subset of
    NPComplete --> NP : Special case

3. Intractability: Why Some Problems Are Hard

Intractable problems cannot be solved efficiently (e.g., NP-complete problems).

• SAT is NP-Complete: Proving this reduces any NP problem to SAT.
• Implications:
  • No known polynomial-time algorithm exists.
  • Approximations (e.g., heuristics) are used in practice.

Example: eSewa’s order processing uses NP-hard scheduling to assign agents to customer requests. Exact solutions are impractical, so they use approximations.

4. Turing Machine Complexity: Time and Space

Time Complexity

• Count the number of steps a TM takes for input size $n$.
• Example: A TM that counts the number of 1s in a binary string:
  • Time: $O(n)$ (read each bit once).

Space Complexity

• Measure the tape cells used.
• Example: A TM that checks if a string is in a regular language may use $O(1)$ space (finite automaton).

Tape: 0 1 1 0 1 | Head
States: q0 (start), q1 (count 1s), q_accept, q_reject
Steps:
1. Start at q0, move right.
2. On '1', move to q1, increment counter.
3. On '0', stay in q0.
4. End at q_accept if all 1s are counted.

5. Real-World Applications

1. eSewa’s Order Processing

• Problem: Assigning agents to customer requests (NP-hard scheduling).
• Solution: Uses heuristics (approximations) to balance load efficiently.

2. Ncell’s Network Routing

• Problem: Finding optimal paths for data packets (similar to TSP).
• Solution: Uses shortest-path algorithms (Dijkstra’s, $O(n^2)$).

3. Daraz’s Inventory Management

• Problem: Stock allocation (NP-complete knapsack problem).
• Solution: Uses linear programming for near-optimal solutions.

6. Worked Example: SAT Problem

Problem: Given a Boolean formula, is there an assignment to variables that makes it true? Reduction to NP-Complete:

1. Any NP problem can be converted to SAT.
2. Example: Convert a graph coloring problem to SAT:
   • Variables: $x_i^c$ = "Node $i$ is colored $c$."
   • Clauses: Ensure no two adjacent nodes share a color.

graph TD
    A["Graph Coloring"] -->|"Convert"| B["SAT Instance"]
    B --> C["Solve SAT"]
    C --> D["Solution to Graph Coloring"]

Exam Tip

• Define clearly: Time/space complexity, Big-O/Θ, P/NP/NP-Complete.
• Prove reductions: For NP-complete problems, show how they reduce to SAT.
• Real-world links: Connect TSP to NTC routes, SAT to eSewa’s logic checks.
• Trace TMs: Show step-by-step tape movements for complexity analysis.
• Avoid memorization: Focus on why problems are hard (e.g., exponential growth).

Key Formulae to Remember:

• $O(n^2)$ vs $O(2^n)$: The latter is intractable for large $n$.
• NP-Complete problems: SAT, TSP, Vertex Cover, Knapsack.