Project 15: Computational Complexity Explorer

Build a small lab for NP-completeness, reductions, and approximations.

Quick Reference

Attribute Value
Difficulty Level 5: Master
Time Estimate 1 month
Language Python (Alternatives: Any)
Prerequisites All previous projects, mathematical maturity
Key Topics NP-completeness, reductions, approximation

1. Learning Objectives

By completing this project, you will:

  1. Explain P, NP, NP-hard, and NP-complete with examples.
  2. Implement small brute-force solvers for SAT, Vertex Cover, and TSP.
  3. Build and demonstrate polynomial-time reductions.
  4. Implement and evaluate approximation algorithms.

2. Theoretical Foundation

2.1 Core Concepts

  • Decision problems: Yes/No versions of optimization problems.
  • Polynomial-time reductions: Transform problem A to B in poly time.
  • NP-completeness: Problems that are in NP and NP-hard.
  • Approximation algorithms: Guarantee near-optimal solutions.

2.2 Why This Matters

Complexity theory explains why some problems resist efficient solutions and guides us toward heuristics and approximations in practice.

2.3 Historical Context / Background

Cook-Levin (1971) proved SAT is NP-complete, forming the basis of modern complexity theory.

2.4 Common Misconceptions

  • Misconception: NP means “not polynomial”. Reality: NP means verifiable in polynomial time.
  • Misconception: Approximation is always good enough. Reality: Some problems are hard to approximate.

3. Project Specification

3.1 What You Will Build

A CLI toolkit that demonstrates NP-complete problems, reductions, and approximation algorithms on small instances.

3.2 Functional Requirements

  1. SAT solver: Brute force for small instances.
  2. Vertex cover: Exact and 2-approximation.
  3. TSP: Brute force for small n, MST-based 2-approx for metric TSP.
  4. Reductions: Show SAT to 3-SAT or SAT to Vertex Cover mapping.
  5. Reports: Output solution sizes and approximation ratios.

3.3 Non-Functional Requirements

  • Performance: Only small instances for brute force.
  • Reliability: Correctness of reductions and checks.
  • Usability: CLI with clear descriptions of limitations.

3.4 Example Usage / Output

$ ./complexity --sat formula.txt
SAT: yes
Assignment: 1 0 1 0

$ ./complexity --tsp cities.txt --approx
Approx tour length: 120 (ratio <= 2)

3.5 Real World Outcome

You will see how quickly brute force explodes and how approximation algorithms give practical solutions with guarantees.

4. Solution Architecture

4.1 High-Level Design

┌───────────┐     ┌──────────────┐     ┌─────────────┐
│ CLI Input │────▶│ Problem Core │────▶│ Reporter    │
└───────────┘     └──────┬───────┘     └─────────────┘
                            │
                      ┌─────▼─────┐
                      │ Reductions│
                      └───────────┘

4.2 Key Components

Component Responsibility Key Decisions
sat.py SAT brute force Small CNF format
vc.py Vertex cover Exact + approx
tsp.py TSP solvers brute + MST approx
reductions.py SAT -> VC mapping Clear graph encoding

4.3 Data Structures

# CNF representation
clauses = [[1, -3, 4], [-1, 2], [3, -4]]

4.4 Algorithm Overview

Key Algorithm: Vertex Cover 2-Approx

  1. Pick any edge (u, v).
  2. Add both u and v to cover.
  3. Remove all incident edges and repeat.

Complexity Analysis:

  • Time: O(V + E)
  • Space: O(V)

5. Implementation Guide

5.1 Development Environment Setup

python3 -m venv .venv
. .venv/bin/activate

5.2 Project Structure

complexity-explorer/
├── src/
│   ├── sat.py
│   ├── vc.py
│   ├── tsp.py
│   ├── reductions.py
│   └── cli.py
├── data/
└── tests/

5.3 The Core Question You’re Answering

“What makes a problem hard, and what can we do about it?”

5.4 Concepts You Must Understand First

Stop and research these before coding:

  1. P vs NP definitions
  2. Polynomial-time reductions
  3. Approximation ratios

5.5 Questions to Guide Your Design

  1. How will you keep instances small enough for brute force?
  2. How will you explain reductions in output?
  3. How will you measure approximation quality?

5.6 Thinking Exercise

Take a 3-SAT formula and convert it to a graph for Vertex Cover. Verify that a satisfying assignment corresponds to a small cover.

5.7 The Interview Questions They’ll Ask

  1. What does NP-complete mean?
  2. Explain a reduction from SAT to 3-SAT.
  3. Why do approximation algorithms matter?

5.8 Hints in Layers

Hint 1: Start with SAT brute force Limit to <= 12 variables.

Hint 2: Build exact VC for small graphs Use bitmask enumeration to compare with approx.

Hint 3: Use MST for TSP approximation Build MST, double edges, then shortcut.

5.9 Books That Will Help

Topic Book Chapter
NP-completeness “Introduction to Algorithms” Ch. 34
Reductions “Algorithm Design” Ch. 8
Approximation “Introduction to Algorithms” Ch. 35

5.10 Implementation Phases

Phase 1: Foundation (8-10 days)

Goals:

  • Implement SAT brute force
  • Build CNF parser

Tasks:

  1. Parse CNF from simple text format.
  2. Implement assignment enumeration.

Checkpoint: SAT solver handles small inputs.

Phase 2: Vertex Cover and Reductions (8-10 days)

Goals:

  • Implement exact and approximate VC
  • Add SAT to VC reduction

Tasks:

  1. Build VC exact solver for small graphs.
  2. Implement reduction mapping.

Checkpoint: Reduction output passes verification.

Phase 3: TSP and Reporting (6-8 days)

Goals:

  • Implement TSP brute force and approx
  • Add report of ratios

Tasks:

  1. Add MST-based approx.
  2. Print approximation ratios.

Checkpoint: Approx ratios appear in output.

5.11 Key Implementation Decisions

Decision Options Recommendation Rationale
SAT format DIMACS, custom custom Simpler for learning
VC exact bitmask, ILP bitmask Simple and transparent
TSP approx MST, Christofides MST 2-approx Easier to implement

6. Testing Strategy

6.1 Test Categories

Category Purpose Examples
Unit Tests Small solvers SAT with 3 vars
Integration Tests Reductions SAT -> VC check
Edge Case Tests Unsat formulas No solution

6.2 Critical Test Cases

  1. SAT instance with known assignment.
  2. VC graph with known optimal cover.
  3. TSP with 4 cities.

6.3 Test Data

SAT: (x1 OR x2) AND (NOT x1 OR x3)
Graph: triangle
Cities: square

7. Common Pitfalls and Debugging

7.1 Frequent Mistakes

Pitfall Symptom Solution
Wrong reduction mapping VC doesn’t correspond Validate mapping step by step
Exponential blow-up Program hangs Cap input sizes
Miscomputed ratios Incorrect reports Use exact solution for small cases

7.2 Debugging Strategies

  • Validate each reduction with a small hand-crafted example.
  • Compare approximate vs exact for tiny instances.

7.3 Performance Traps

Brute force grows exponentially. Always enforce max variable or node limits.

8. Extensions and Challenges

8.1 Beginner Extensions

  • Add 3-SAT solver for small cases.
  • Add set cover approximation.

8.2 Intermediate Extensions

  • Add ILP solver integration (optional).
  • Add reductions from 3-SAT to Clique.

8.3 Advanced Extensions

  • Implement Christofides for TSP.
  • Add visualization of reduction graphs.

9. Real-World Connections

9.1 Industry Applications

  • Scheduling and resource allocation
  • Network design and optimization
  • OR-Tools: Optimization and constraints.
  • MiniSat: SAT solver.

9.3 Interview Relevance

Complexity topics appear in advanced interviews and research discussions.

10. Resources

10.1 Essential Reading

  • “Introduction to Algorithms” - Ch. 34-35
  • “Algorithm Design” by Kleinberg & Tardos - Ch. 8

10.2 Video Resources

  • NP-completeness lectures and reductions

10.3 Tools and Documentation

  • DIMACS SAT format (if extending)

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain P vs NP.
  • I can perform a basic reduction.
  • I can compute approximation ratios.

11.2 Implementation

  • Solvers work on small instances.
  • Reductions produce correct mappings.

11.3 Growth

  • I can identify NP-hard problems and choose heuristics.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • SAT brute force solver
  • Vertex cover approximation

Full Completion:

  • SAT to VC reduction
  • TSP brute force and 2-approx

Excellence (Going Above and Beyond):

  • Christofides algorithm
  • Visualization of reductions

This guide was generated from LEARN_ALGORITHMS_DEEP_DIVE.md. For the complete learning path, see the parent directory.