NP-Completeness

Nievergelt & Hinrichs · Ch. 10 · Algorithms and Data Structures

P = problems solvable in polynomial time. NP = problems whose solutions are verifiable in polynomial time. NP-complete problems are the hardest in NP: if you solve one in polynomial time, you solve them all. Nobody has proved P = NP or P ≠ NP. The question is the central open problem in computer science.

What is a reduction?

Problem A reduces to problem B (written A ≤p B) if you can transform any instance of A into an instance of B in polynomial time. If B is easy, A is easy. Contrapositive: if A is hard, B is hard. This is how hardness spreads.

Scheme

; SAT: is there an assignment that makes a Boolean formula true?
; A formula in CNF: (x1 OR NOT x2) AND (NOT x1 OR x3) AND (x2 OR x3)

; Brute-force SAT solver: try all 2^n assignments
(define (sat-solve clauses n-vars)
  (define (check assignment)
    (define (var-val v)
      (if (> v 0)
          (list-ref assignment (- v 1))
          (not (list-ref assignment (- (- v) 1)))))
    (define (clause-sat clause)
      (ormap var-val clause))
    (andmap clause-sat clauses))
  ; Generate all assignments
  (define (gen n)
    (if (= n 0) (list (list))
        (let ((rest (gen (- n 1))))
          (append (map (lambda (a) (cons #t a)) rest)
                  (map (lambda (a) (cons #f a)) rest)))))
  (let loop ((assignments (gen n-vars)))
    (cond ((null? assignments) "UNSAT")
          ((check (car assignments))
           (cons "SAT" (car assignments)))
          (else (loop (cdr assignments))))))

; (x1 OR -x2) AND (-x1 OR x3) AND (x2 OR x3)
(define formula (list (list 1 -2) (list -1 3) (list 2 3)))

(display (sat-solve formula 3))
; Exponential: 2^n assignments to try

; SAT: is there an assignment that makes a Boolean formula true?
; A formula in CNF: (x1 OR NOT x2) AND (NOT x1 OR x3) AND (x2 OR x3)

; Brute-force SAT solver: try all 2^n assignments
(define (sat-solve clauses n-vars)
  (define (check assignment)
    (define (var-val v)
      (if (> v 0)
          (list-ref assignment (- v 1))
          (not (list-ref assignment (- (- v) 1)))))
    (define (clause-sat clause)
      (ormap var-val clause))
    (andmap clause-sat clauses))
  ; Generate all assignments
  (define (gen n)
    (if (= n 0) (list (list))
        (let ((rest (gen (- n 1))))
          (append (map (lambda (a) (cons #t a)) rest)
                  (map (lambda (a) (cons #f a)) rest)))))
  (let loop ((assignments (gen n-vars)))
    (cond ((null? assignments) "UNSAT")
          ((check (car assignments))
           (cons "SAT" (car assignments)))
          (else (loop (cdr assignments))))))

; (x1 OR -x2) AND (-x1 OR x3) AND (x2 OR x3)
(define formula (list (list 1 -2) (list -1 3) (list 2 3)))

(display (sat-solve formula 3))
; Exponential: 2^n assignments to try

The NP-complete zoo

SAT (satisfiability), 3-SAT, CLIQUE (is there a complete subgraph of size k?), VERTEX COVER (can you cover all edges with k vertices?), HAMILTONIAN CYCLE, SUBSET SUM, KNAPSACK. All are NP-complete. All reduce to each other in polynomial time. None have known polynomial-time algorithms.

Scheme

; Clique: brute-force check for a complete subgraph of size k
; Graph as adjacency matrix

(define (has-edge? adj u v)
  (vector-ref (vector-ref adj u) v))

(define (is-clique? adj vertices)
  (let loop ((vs vertices))
    (if (null? vs) #t
        (let inner ((rest (cdr vs)))
          (if (null? rest)
              (loop (cdr vs))
              (if (has-edge? adj (car vs) (car rest))
                  (inner (cdr rest))
                  #f))))))

; Graph: 0-1, 0-2, 1-2, 1-3, 2-3 (5 edges, 4 vertices)
(define adj (vector
  (vector #f #t #t #f)
  (vector #t #f #t #t)
  (vector #t #t #f #t)
  (vector #f #t #t #f)))

(display "Is (0,1,2) a clique? ")
(display (is-clique? adj (list 0 1 2))) (newline)
(display "Is (0,1,3) a clique? ")
(display (is-clique? adj (list 0 1 3))) (newline)
(display "Is (1,2,3) a clique? ")
(display (is-clique? adj (list 1 2 3)))

Approximation

When exact solutions are intractable, approximation algorithms guarantee solutions within a factor of optimal. Vertex cover has a 2-approximation. Traveling salesman with triangle inequality has a 1.5-approximation (Christofides). General TSP has no constant-factor approximation unless P = NP.

Neighbors

Cross-references

🔢 Discrete Math Ch.3 — logic: SAT is satisfiability of propositional formulas
🔀 Theory of Computation Ch.8 — P vs NP is the complexity-theoretic framing of the same question
🔐 Cryptography — every hard crypto problem relies on an NP-hard assumption
✎ Proofs Ch.3 — NP-completeness proofs use contradiction and reduction

← Dynamic Programming by june.kim