Skip to content

Computational Complexity

Overview

Computational complexity theory studies not "whether we can compute" but "how many resources computation requires." Even if a problem is decidable, the time or space resources it demands may make it practically unsolvable.

1. Complexity Class Basics

1.1 Time Complexity

Definition: The time complexity \(t(n)\) of a Turing machine \(M\) is the maximum number of steps \(M\) takes on any input of length \(n\).

\[ \text{TIME}(t(n)) = \{L \mid \text{there exists a deterministic TM deciding } L \text{ in } O(t(n)) \text{ time}\} \]

1.2 Basic Complexity Classes

\[ \textbf{P} = \bigcup_{k \geq 0} \text{TIME}(n^k) \]

P: Languages decidable in polynomial time. Represents "efficiently solvable" problems.

\[ \textbf{NP} = \bigcup_{k \geq 0} \text{NTIME}(n^k) \]

NP: Languages decidable in nondeterministic polynomial time.

Equivalent definition: \(L \in \textbf{NP}\) if and only if there exists a polynomial-time verifier \(V\) and a polynomial \(p\) such that:

\[ w \in L \iff \exists c \; (|c| \leq p(|w|) \wedge V(w, c) = \text{accept}) \]

where \(c\) is called the certificate (or witness).

NP Problem Example

COMPOSITES problem: Given an integer \(n\), is \(n\) composite?

  • Certificate: A nontrivial factor \(d\) of \(n\)
  • Verification: Check that \(1 < d < n\) and \(d \mid n\); this runs in polynomial time

Note: COMPOSITES (and PRIMES) are actually in P as well (AKS primality test, 2002).

1.3 co-NP

\[ \textbf{co-NP} = \{L \mid \overline{L} \in \textbf{NP}\} \]
  • \(\textbf{P} \subseteq \textbf{NP} \cap \textbf{co-NP}\)
  • It is generally believed that \(\textbf{NP} \neq \textbf{co-NP}\)
graph TB
    subgraph "Complexity Class Hierarchy (assuming P != NP)"
        P["P"]
        NPI["NP-intermediate"]
        NPC["NP-complete"]
        NP["NP"]
    end
    P --> NPI --> NPC
    P --> NP
    NPC --> NP

2. P vs NP Problem

2.1 Problem Statement

\[ \textbf{P} \stackrel{?}{=} \textbf{NP} \]

This is one of the most important open problems in computer science (and mathematics), and one of the seven Millennium Prize Problems of the Clay Mathematics Institute.

2.2 Intuitive Understanding

  • P: Problems that can be solved quickly
  • NP: Problems that can be verified quickly
  • P vs NP: Does fast verification imply fast solving?

Most computer scientists believe \(\textbf{P} \neq \textbf{NP}\).

2.3 If P = NP

If \(\textbf{P} = \textbf{NP}\), then:

  • All NP problems could be solved in polynomial time
  • Modern cryptography (based on hardness assumptions like factoring and discrete logarithms) would collapse
  • Optimization problems (scheduling, routing, etc.) would become "easy"
  • Discovering mathematical proofs would become easy (verification \(\to\) search)

3. NP-Completeness

3.1 Polynomial-Time Reductions

Definition: \(A \leq_p B\) (\(A\) polynomial-time reduces to \(B\)) if there exists a polynomial-time computable function \(f\) such that:

\[ w \in A \iff f(w) \in B \]

Properties:

  • If \(A \leq_p B\) and \(B \in \textbf{P}\), then \(A \in \textbf{P}\)
  • Transitivity: \(A \leq_p B\) and \(B \leq_p C \implies A \leq_p C\)

3.2 Definition of NP-Completeness

A language \(L\) is NP-complete if:

  1. \(L \in \textbf{NP}\)
  2. \(\forall A \in \textbf{NP}, A \leq_p L\) (NP-hard)

NP-complete problems are the "hardest" problems in NP. If any NP-complete problem has a polynomial algorithm, then \(\textbf{P} = \textbf{NP}\).

3.3 Cook-Levin Theorem

Theorem (Cook 1971, Levin 1973): SAT is NP-complete.

SAT (Boolean Satisfiability Problem):

  • Input: A Boolean formula \(\phi(x_1, x_2, \ldots, x_n)\)
  • Question: Is there a variable assignment that makes \(\phi\) true?

Proof sketch:

  1. SAT \(\in\) NP: Given an assignment, it can be verified in polynomial time
  2. NP-hard: For any NP language \(A\), encode the computation of its nondeterministic Turing machine as a Boolean formula
    • Use variables to represent TM configurations (state, tape contents, head position)
    • Encode transition function as clauses
    • Encode acceptance condition as clauses

4. Classic NP-Complete Problems

4.1 3-SAT

\[ \phi = (x_1 \vee \bar{x}_2 \vee x_3) \wedge (\bar{x}_1 \vee x_2 \vee x_4) \wedge \cdots \]

Satisfiability of a CNF formula where each clause has exactly 3 literals.

Reduction: SAT \(\leq_p\) 3-SAT (split long clauses, introduce auxiliary variables)

4.2 CLIQUE

  • Input: Graph \(G = (V, E)\), positive integer \(k\)
  • Question: Does \(G\) contain a clique (complete subgraph) of size \(k\)?

Reduction: 3-SAT \(\leq_p\) CLIQUE

For a 3-SAT instance with \(m\) clauses, construct graph \(G\): - Each literal in each clause becomes a vertex - Edge condition: Not in the same clause and not complementary - Set \(k = m\)

4.3 VERTEX COVER

  • Input: Graph \(G = (V, E)\), positive integer \(k\)
  • Question: Does there exist \(S \subseteq V\), \(|S| \leq k\), such that every edge has at least one endpoint in \(S\)?

Reduction: CLIQUE \(\leq_p\) VERTEX COVER

Graph \(G\) has a clique of size \(k\) \(\iff\) the complement graph \(\overline{G}\) has a vertex cover of size \(|V| - k\).

4.4 HAMILTONIAN CYCLE

  • Input: Graph \(G\)
  • Question: Does \(G\) contain a cycle that visits every vertex exactly once?

4.5 Traveling Salesman Problem (TSP)

  • Input: Distance matrix for \(n\) cities, budget \(B\)
  • Question: Is there a tour visiting all cities with total distance \(\leq B\)?

Reduction: HAMILTONIAN CYCLE \(\leq_p\) TSP

4.6 Reduction Relationship Diagram

graph TD
    SAT[SAT] --> 3SAT[3-SAT]
    3SAT --> CLIQUE[CLIQUE]
    3SAT --> IS[Independent Set]
    CLIQUE --> VC[Vertex Cover]
    IS --> VC
    3SAT --> 3COLOR[3-Coloring]
    3SAT --> SUBSET[Subset Sum]
    SUBSET --> KNAPSACK[Knapsack]
    SUBSET --> PARTITION[Partition]
    VC --> HC[Hamiltonian Cycle]
    HC --> TSP[Traveling Salesman]
    3SAT --> DS[Dominating Set]

5. NP-Complete Problem List

Problem Category Description
SAT Logic Boolean satisfiability
3-SAT Logic 3-CNF satisfiability
CLIQUE Graph theory Maximum clique
VERTEX COVER Graph theory Minimum vertex cover
INDEPENDENT SET Graph theory Maximum independent set
3-COLORING Graph theory 3-color graph coloring
HAMILTONIAN CYCLE Graph theory Hamiltonian cycle
TSP Optimization Traveling salesman problem
SUBSET SUM Number theory Subset sum problem
KNAPSACK Optimization 0-1 knapsack problem
SET COVER Set theory Minimum set cover
PARTITION Number theory Equal-sum partition

Karp's classic 1972 paper listed 21 NP-complete problems, laying the foundation for NP-completeness theory.

6. PSPACE

6.1 Definition

\[ \textbf{PSPACE} = \bigcup_{k \geq 0} \text{SPACE}(n^k) \]

6.2 Hierarchy Relationships

\[ \textbf{P} \subseteq \textbf{NP} \subseteq \textbf{PSPACE} \subseteq \textbf{EXPTIME} \]

By the time hierarchy theorem: \(\textbf{P} \neq \textbf{EXPTIME}\), but we do not know whether the intermediate inclusions are strict.

Savitch's theorem:

\[ \text{NSPACE}(s(n)) \subseteq \text{SPACE}(s(n)^2) \]

Corollary: \(\textbf{NPSPACE} = \textbf{PSPACE}\)

6.3 PSPACE-Complete Problems

TQBF (Totally Quantified Boolean Formula):

\[ \exists x_1 \forall x_2 \exists x_3 \cdots \phi(x_1, x_2, x_3, \ldots) \]

TQBF is PSPACE-complete (analogous to SAT's role for NP).

Other PSPACE-complete problems:

  • Generalized Geography
  • Optimal strategy for Go
  • Regular expression equivalence

7. Approximation Algorithms

7.1 Motivation

Since NP-complete problems (very likely) have no polynomial exact algorithms, can we find approximately optimal solutions in polynomial time?

7.2 Approximation Ratio

For a minimization problem, the approximation ratio \(\rho\) of algorithm \(A\) satisfies:

\[ \frac{A(I)}{OPT(I)} \leq \rho \quad \text{for all instances } I \]

7.3 Classic Approximation Results

Problem Approximation Ratio Algorithm
Vertex Cover 2 Greedy matching
Set Cover \(\ln n\) Greedy
TSP (triangle inequality) 1.5 Christofides
MAX-SAT 0.75 Randomized rounding
Knapsack \(1 + \varepsilon\) FPTAS

7.4 Inapproximability

PCP Theorem (Probabilistically Checkable Proofs):

\[ \textbf{NP} = \textbf{PCP}[\log n, 1] \]

This implies that certain NP-complete problems cannot be approximated to arbitrary ratios under the \(\textbf{P} \neq \textbf{NP}\) assumption:

  • MAX-3SAT: Cannot be approximated better than \(7/8\)
  • CLIQUE: Cannot be approximated to within \(n^{1-\varepsilon}\)
  • SET COVER: Cannot be approximated better than \(\ln n\) (unless \(\textbf{P} = \textbf{NP}\))

8. Complexity Class Landscape

graph TB
    subgraph "Space Complexity"
        L["L (Log Space)"]
        NL["NL"]
        PSPACE["PSPACE"]
    end
    subgraph "Time Complexity"
        P["P"]
        NP["NP"]
        coNP["co-NP"]
        EXP["EXPTIME"]
    end
    L --> NL --> P --> NP --> PSPACE --> EXP
    P --> coNP --> PSPACE

Known strict inclusions:

  • \(\textbf{L} \subsetneq \textbf{PSPACE}\) (space hierarchy theorem)
  • \(\textbf{P} \subsetneq \textbf{EXPTIME}\) (time hierarchy theorem)
  • \(\textbf{NL} \subsetneq \textbf{PSPACE}\)

Major open problems:

  • \(\textbf{P} \stackrel{?}{=} \textbf{NP}\)
  • \(\textbf{NP} \stackrel{?}{=} \textbf{co-NP}\)
  • \(\textbf{P} \stackrel{?}{=} \textbf{PSPACE}\)
  • \(\textbf{NP} \stackrel{?}{=} \textbf{PSPACE}\)
  • \(\textbf{L} \stackrel{?}{=} \textbf{P}\)

References

  • Sipser, Introduction to the Theory of Computation, Chapters 7-10
  • Arora & Barak, Computational Complexity: A Modern Approach
  • Garey & Johnson, Computers and Intractability (the bible of NP-completeness)

Related sections:

评论 #