Complexity

Maheshwari & Smid · Ch. 8 · Introduction to Theory of Computation

P is the class of problems solvable in polynomial time. NP is the class whose solutions can be verified in polynomial time. Whether P = NP is the central open question. The Cook-Levin theorem proves that SAT is NP-complete: every NP problem reduces to it in polynomial time.

P: efficiently solvable

P contains problems where an algorithm runs in O(n^k) time for some constant k. Sorting, shortest path, matching, primality testing: all in P.

NP: efficiently verifiable

NP contains problems where a proposed solution (certificate) can be checked in polynomial time. Finding a solution may be hard, but verifying one is fast. Every problem in P is also in NP (just solve it and check).

Scheme

; SAT: given a boolean formula, is there an assignment
; that makes it true?
; Checking a given assignment is easy (polynomial).
; Finding one may require exponential search.

; Formula: (x1 OR x2) AND (NOT x1 OR x3) AND (NOT x2 OR NOT x3)
; This is in conjunctive normal form (CNF).

(define (eval-clause clause assignment)
  ; clause is list of (var . positive?)
  (define (eval-lit lit)
    (let ((val (list-ref assignment (car lit))))
      (if (cdr lit) val (not val))))
  (not (null? (filter eval-lit clause))))

(define (eval-cnf clauses assignment)
  (null? (filter (lambda (c) (not (eval-clause c assignment)))
                 clauses)))

; (x1 OR x2) AND (NOT x1 OR x3) AND (NOT x2 OR NOT x3)
(define formula
  (list
    (list (cons 0 #t) (cons 1 #t))        ; x1 OR x2
    (list (cons 0 #f) (cons 2 #t))        ; NOT x1 OR x3
    (list (cons 1 #f) (cons 2 #f))))      ; NOT x2 OR NOT x3

; Try all 8 assignments for 3 variables
(define (try-all n)
  (if (= n 8) (display "No satisfying assignment found.")
      (let ((a (list (> (modulo n 4) 1)
                     (> (modulo (modulo n 4) 2) 0)
                     (odd? n))))
        (if (eval-cnf formula a)
            (begin (display "SAT! Assignment: ") (display a))
            (try-all (+ n 1))))))

(display "Formula: (x1|x2) & (!x1|x3) & (!x2|!x3)") (newline)
(try-all 0)

; SAT: given a boolean formula, is there an assignment
; that makes it true?
; Checking a given assignment is easy (polynomial).
; Finding one may require exponential search.

; Formula: (x1 OR x2) AND (NOT x1 OR x3) AND (NOT x2 OR NOT x3)
; This is in conjunctive normal form (CNF).

(define (eval-clause clause assignment)
  ; clause is list of (var . positive?)
  (define (eval-lit lit)
    (let ((val (list-ref assignment (car lit))))
      (if (cdr lit) val (not val))))
  (not (null? (filter eval-lit clause))))

(define (eval-cnf clauses assignment)
  (null? (filter (lambda (c) (not (eval-clause c assignment)))
                 clauses)))

; (x1 OR x2) AND (NOT x1 OR x3) AND (NOT x2 OR NOT x3)
(define formula
  (list
    (list (cons 0 #t) (cons 1 #t))        ; x1 OR x2
    (list (cons 0 #f) (cons 2 #t))        ; NOT x1 OR x3
    (list (cons 1 #f) (cons 2 #f))))      ; NOT x2 OR NOT x3

; Try all 8 assignments for 3 variables
(define (try-all n)
  (if (= n 8) (display "No satisfying assignment found.")
      (let ((a (list (> (modulo n 4) 1)
                     (> (modulo (modulo n 4) 2) 0)
                     (odd? n))))
        (if (eval-cnf formula a)
            (begin (display "SAT! Assignment: ") (display a))
            (try-all (+ n 1))))))

(display "Formula: (x1|x2) & (!x1|x3) & (!x2|!x3)") (newline)
(try-all 0)

Polynomial-time reductions

Problem A reduces to problem B (A ≤_P B) if instances of A can be transformed to instances of B in polynomial time. If B is in P and A reduces to B, then A is in P too. Reductions let us compare hardness.

NP-completeness

A problem is NP-complete if it is in NP and every NP problem reduces to it. NP-complete problems are the hardest in NP. If any one of them is in P, then P = NP and all of them are in P.

Cook-Levin theorem

The Cook-Levin theorem (1971) proves that SAT (boolean satisfiability) is NP-complete. The proof encodes the computation of any NP Turing machine as a boolean formula. Every step, state, and tape cell becomes a variable. The formula is satisfiable if and only if the machine accepts. Since any NP problem can be encoded this way, SAT is the universal NP-complete problem.

Scheme

; The zoo of NP-complete problems: all are equivalent
; under polynomial-time reductions.
;
; SAT (Cook-Levin, 1971)
;   |-- 3-SAT (restrict to 3 literals per clause)
;   |     |-- 3-COLORING (color graph with 3 colors)
;   |     |-- CLIQUE (find complete subgraph of size k)
;   |     |-- VERTEX-COVER
;   |     |-- SUBSET-SUM
;   |           |-- KNAPSACK
;   |
;   |-- CIRCUIT-SAT
;         |-- HAMILTONIAN-PATH
;               |-- TSP (Traveling Salesman)

(display "If you solve one in polynomial time,") (newline)
(display "you solve them ALL in polynomial time.") (newline)
(display "That is what NP-completeness means.") (newline)
(newline)
(display "Known NP-complete problems: ~10,000+") (newline)
(display "Known to be in P: 0 of them (so far).")

Neighbors

⚙ Algorithms Ch.10 — NP-completeness in the algorithms context
🔢 Discrete Math Ch.3 — propositional logic and SAT
⚙ Algorithms Ch.1 — complexity classes in practice: O(n log n) sorting, O(n²) dynamic programming
🔢 Discrete Math Ch.4 — graph theory: Hamilton path is the canonical NP-complete problem
🔐 Cryptography Ch.1 — cryptographic security assumes P ≠ NP: factoring is believed hard

← Decidability by june.kim