P, NP, and Completeness Theory

A decision problem L is a set of strings over some alphabet Σ:

L ⊆ Σ*

An algorithm solves L if for any input x ∈ Σ*:

• If x ∈ L, the algorithm outputs "yes" or 1
• If x ∉ L, the algorithm outputs "no" or 0

The strings in L are called positive instances or yes-instances, while strings not in L are negative instances or no-instances.

An optimization problem P consists of:

• A set I of instances
• For each instance x ∈ I, a set S(x) of feasible solutions
• For each instance x and solution y ∈ S(x), a cost function f(x, y)
• A goal to either minimize or maximize f(x, y)

The objective is to find y* ∈ S(x) such that f(x, y*) is optimal (either minimum or maximum) among all y ∈ S(x).

Given an optimization problem P to minimize f(x, y), we can define a corresponding decision problem D:

D = {(x, k) | ∃y ∈ S(x) such that f(x, y) ≤ k}

Similarly, for a maximization problem, the decision version would be:

D = {(x, k) | ∃y ∈ S(x) such that f(x, y) ≥ k}

If we can solve the decision problem efficiently for any value k, we can use binary search to find the optimal value of the original optimization problem.

A certificate (or witness) for a decision problem instance is a string c that helps verify that the instance is a yes-instance.

Formally, for a decision problem L, a certificate scheme consists of:

• For each x ∈ L, a non-empty set C(x) of valid certificates
• A verification algorithm V that, given x and c, accepts if and only if c ∈ C(x)

For complexity theory, we're particularly interested in cases where certificates are of polynomial length and can be verified in polynomial time.

A decision problem L has efficient verification if there exists:

• A polynomial p(n)
• A polynomial-time algorithm V (the verifier)

Such that for all x:

x ∈ L ⟺ ∃c, |c| ≤ p(|x|) such that V(x, c) = 1

In other words, yes-instances have short, efficiently verifiable certificates.

The class P (polynomial time) is the set of all decision problemsL for which there exists a deterministic polynomial-time algorithm Asuch that:

• If x ∈ L, then A(x) = 1
• If x ∉ L, then A(x) = 0

Equivalently, P = ⋃k≥1 DTIME(nk).

The class P is robust under different reasonable computational models (multi-tape Turing machines, RAMs, etc.) and is widely accepted as capturing the notion of efficient computation.

The following problems are in P:

• PRIMES = {n | n is a prime number}
  Algorithm: AKS primality test, running in O(log6 n) time
• PATH = {(G,s,t) | graph G has a path from vertex s to vertex t}
  Algorithm: Breadth-first search, running in O(|V| + |E|) time
• 2-SAT = {φ | φ is a satisfiable 2-CNF formula}
  Algorithm: Construct and analyze implication graph, running in O(n+m) time
• LINEAR-PROGRAMMING = {(A,b,c,k) | ∃x: Ax ≤ b and c·x ≥ k}
  Algorithm: Ellipsoid method or interior-point methods, running in polynomial time

The class NP (nondeterministic polynomial time) is the set of all decision problems L for which there exists a nondeterministic polynomial-time Turing machine M such that:

• If x ∈ L, then M accepts x on some computation path
• If x ∉ L, then M rejects x on all computation paths

Equivalently, NP = ⋃k≥1 NTIME(nk).

A language L is in NP if and only if there exist:

• A polynomial p(n)
• A polynomial-time deterministic algorithm V (the verifier)

Such that for all strings x:

x ∈ L ⟺ ∃c, |c| ≤ p(|x|) such that V(x, c) = 1

This characterization defines NP in terms of efficiently verifiable certificates.

A binary relation R ⊆ Σ* × Σ* is polynomial-time decidable if there is a polynomial-time algorithm that decides, for any x, y, whether (x, y) ∈ R.

R is polynomially bounded if there exists a polynomialp such that for all (x, y) ∈ R, we have |y| ≤ p(|x|).

A language L is in NP if and only if there exists a polynomial-time decidable, polynomially bounded relation R such that:

L = {x | ∃y such that (x, y) ∈ R}

The following problems are in NP:

• SAT = {φ | φ is a satisfiable Boolean formula}
  Certificate: A satisfying assignment to the variables
• HAMPATH = {(G,s,t) | graph G has a simple path from s to t visiting every vertex}
  Certificate: The sequence of vertices in the Hamiltonian path
• CLIQUE = {(G,k) | graph G has a clique of size at least k}
  Certificate: The set of vertices forming a k-clique
• SUBSET-SUM = {(S,t) | there exists a subset of S that sums to t}
  Certificate: The subset of elements that sum to t
• 3-COLORING = {G | graph G can be colored with 3 colors with no adjacent vertices sharing a color}
  Certificate: A valid 3-coloring of the vertices

The P vs. NP question asks whether P = NP or P ≠ NP.

Formally, the question is whether every language L with a polynomial-time verification algorithm also has a polynomial-time solution algorithm.

This question remains open despite decades of research. Most complexity theorists believe that P ≠ NP, but no proof or disproof has been found.

Key developments in the history of the P vs. NP question:

• 1956: Gödel writes a letter to von Neumann discussing the complexity of finding proofs, anticipating aspects of the P vs. NP question
• 1971: Stephen Cook's paper "The Complexity of Theorem-Proving Procedures" introduces the concept of NP-completeness and proves that SAT is NP-complete
• 1971-1972: Leonid Levin independently discovers NP-completeness in the Soviet Union
• 1972: Richard Karp's paper "Reducibility Among Combinatorial Problems" identifies 21 NP-complete problems, demonstrating the pervasiveness of NP-completeness
• 1979: The P vs. NP problem begins to gain recognition outside theoretical computer science
• 1990s: Development of various barriers to proving P ≠ NP (relativization, natural proofs, algebrization)
• 2000: The Clay Mathematics Institute designates P vs. NP as one of the seven Millennium Prize Problems, offering a $1 million prize for its solution
• 2000s-present: Continued research, including numerous claimed proofs (both for P=NP and P≠NP), all of which have been found to contain errors

If P=NP, the following would be true:

• Algorithmic Implications: Any problem with efficiently verifiable solutions would have an efficient solution algorithm
• Self-Optimization: For many optimization problems, we could efficiently find optimal solutions rather than approximations
• Cryptographic Impact: Most current cryptographic systems would be broken, as they rely on the presumed hardness of certain NP problems
• Mathematical Consequences: Automated theorem proving would be dramatically more powerful, potentially revolutionizing mathematical practice
• Learning and AI: Many learning problems would become tractable, potentially leading to dramatic advances in artificial intelligence
• Complexity Collapse: Many complexity classes would collapse: NP = co-NP = P = BPP, and the polynomial hierarchy would collapse

However, even if P=NP, the polynomial-time algorithm might have a prohibitively high exponent or constant factors, limiting practical impact.

If P≠NP, the following would be established:

• Formal Hardness: There would exist problems whose solutions can be verified efficiently but cannot be found efficiently
• Cryptographic Security: The theoretical foundation for modern cryptography would be strengthened, as it relies on the assumed hardness of certain problems
• Inherent Creativity: There would be mathematical confirmation that finding solutions can be inherently more difficult than verifying them
• Approximation Necessity: For many optimization problems, we would know that we must settle for approximate solutions rather than optimal ones
• Algorithmic Barriers: Certain algorithmic tasks would be proven to require exponential time in the worst case
• Proof Techniques: New mathematical techniques developed for proving P≠NP might lead to progress on other complexity separations

Three major barriers to resolving the P vs. NP question have been identified:

• Relativization (Baker, Gill, Solovay, 1975): Techniques that relativize (remain valid when both classes have access to the same oracle) cannot resolve P vs. NP, because there exist oracles A and B such that P^A = NP^A and P^B ≠ NP^B
• Natural Proofs (Razborov, Rudich, 1994): Any "natural" proof technique (with certain constructivity and largeness properties) for showing circuit lower bounds would break widely believed cryptographic assumptions
• Algebrization (Aaronson, Wigderson, 2008): Even techniques that avoid relativization cannot resolve P vs. NP if they algebrize (remain valid under certain algebraic extensions)

These barriers suggest that resolving P vs. NP will require fundamentally new mathematical techniques.

While no proof exists, the following constitute evidence suggesting P≠NP:

• Algorithmic Experience: Decades of research have yielded no polynomial-time algorithms for NP-complete problems, despite strong incentives to find them
• Lower Bounds: Proven exponential lower bounds for restricted models of computation (e.g., constant-depth circuits)
• Oracle Results: For random oracles A, P^A ≠ NP^A with probability 1
• Time-Space Tradeoffs: Proven time-space tradeoffs for SAT algorithms in restricted models
• Logical Implications: P=NP would have consequences that seem implausible, such as the effective automatability of mathematical creativity

A polynomial-time reduction (or Karp reduction) from a languageA to a language B, denoted A ≤p B, is a polynomial-time computable function f : Σ* → Σ* such that for all x:

x ∈ A ⟺ f(x) ∈ B

Intuitively, A ≤p B means that problem A is "no harder than" problem B, because any instance of A can be efficiently transformed into an equivalent instance of B.

A language L is NP-complete if:

1. L ∈ NP (L is in NP)
2. For all A ∈ NP, A ≤p L (L is NP-hard)

A problem is NP-hard if it satisfies condition 2, even if it is not in NP.

The Boolean satisfiability problem (SAT) is defined as:

SAT = {φ | φ is a satisfiable Boolean formula}

A Boolean formula φ is in conjunctive normal form (CNF) if:

• It is a conjunction (AND) of clauses: C₁ ∧ C₂ ∧ ... ∧ Cm
• Each clause Ci is a disjunction (OR) of literals: l₁ ∨ l₂ ∨ ... ∨ lk
• Each literal lj is either a variable xj or its negation ¬xj

The formula is satisfiable if there exists an assignment of true/false values to the variables that makes the entire formula evaluate to true.

To prove that a problem L is NP-complete:

1. Show L ∈ NP: Describe a polynomial-time verification algorithm for L
2. Show L is NP-hard: Choose a known NP-complete problem L' and construct a polynomial-time reduction from L' to L

By transitivity of reductions, if L' is NP-complete and L' ≤_p L, then L is NP-hard. Combined with L ∈ NP, this proves that L is NP-complete.

Several techniques are commonly used in NP-completeness reductions:

• Variable Gadgets: Create components that represent variables and their truth values
• Clause Gadgets: Create components that represent clauses and ensure they are satisfied
• Consistency Gadgets: Ensure that variable representations remain consistent throughout the construction
• Local Replacement: Replace each element of the source problem with a gadget in the target problem
• Forced Structure: Force the solution to have a particular structure, within which the original problem is embedded
• Restriction: Show that a special case of your problem is already NP-complete

When proving a problem L is NP-complete, the choice of source problem L' for the reduction (L' ≤_p L) can significantly affect the complexity of the proof. Consider:

• Structural Similarity: Choose L' with a structure similar to L
• Constraint Type: Match boolean constraints with boolean problems, numeric constraints with numeric problems, etc.
• Common Source Problems:
  • 3-SAT: Good for problems involving choice or constraint satisfaction
  • CLIQUE or INDEPENDENT SET: Good for selection problems
  • 3-COLORING: Good for assignment or labeling problems
  • SUBSET-SUM or PARTITION: Good for numeric or partitioning problems
  • HAMILTONIAN-PATH: Good for sequencing or path problems

The 3-SAT problem is a restricted version of SAT where:

3-SAT = {φ | φ is a satisfiable Boolean formula in CNF with exactly 3 literals per clause}

Despite the restriction to exactly 3 literals per clause, 3-SAT remains NP-complete. This makes it a particularly useful problem for reductions.

Several important variants of SAT have been studied:

• k-SAT: Each clause has exactly k literals
  • NP-complete for k ≥ 3
  • In P for k = 2 (2-SAT is solvable in linear time)
  • Trivial for k = 1 (1-SAT is solvable in linear time)
• MAX-SAT: Find an assignment that satisfies the maximum number of clauses
  • NP-hard optimization problem
  • Even MAX-2-SAT is NP-hard
• NAE-SAT (Not-All-Equal SAT): Each clause must have at least one true and one false literal
  • NP-complete even for 3-NAE-SAT
• XOR-SAT: Each clause is an XOR of literals (exactly one must be true)
  • In P (solvable using Gaussian elimination)
• HORN-SAT: Each clause has at most one positive literal
  • In P (solvable in linear time)

A clique in an undirected graph G = (V, E) is a subset of vertices C ⊆ V such that every two vertices in C are connected by an edge in E. The CLIQUE problem is:

CLIQUE = {(G, k) | graph G has a clique of size at least k}

An independent set in a graph G = (V, E) is a subset S ⊆ V such that no two vertices in S are adjacent. The INDEPENDENT-SET problem is:

INDEPENDENT-SET = {(G, k) | graph G has an independent set of size at least k}

A vertex cover in a graph G = (V, E) is a subset C ⊆ V such that every edge in E has at least one endpoint in C. The VERTEX-COVER problem is:

VERTEX-COVER = {(G, k) | graph G has a vertex cover of size at most k}

These problems are closely related: S is an independent set in G if and only if V-S is a vertex cover in G.

A Hamiltonian path in a graph G = (V, E) is a simple path that visits every vertex exactly once. The HAMILTONIAN-PATH problem is:

HAMILTONIAN-PATH = {G | graph G has a Hamiltonian path}

A Hamiltonian cycle is a simple cycle that visits every vertex exactly once (except the start/end vertex). The HAMILTONIAN-CYCLE problem is:

HAMILTONIAN-CYCLE = {G | graph G has a Hamiltonian cycle}

Both problems are NP-complete, even for special classes of graphs like planar graphs.

A k-coloring of a graph G = (V, E) is an assignment of k colors to vertices such that no adjacent vertices have the same color. The GRAPH-COLORING problem is:

GRAPH-COLORING = {(G, k) | graph G can be colored with at most k colors}

For any fixed k ≥ 3, the k-COLORING problem is NP-complete:

k-COLORING = {G | graph G can be colored with at most k colors}

2-COLORING is in P (a graph is 2-colorable if and only if it is bipartite), but 3-COLORING is already NP-complete.

The SUBSET-SUM problem is:

SUBSET-SUM = {(S, t) | there exists a subset S' ⊆ S such that Σ(S') = t}

where S is a set of integers and Σ(S') denotes the sum of elements in S'.

SUBSET-SUM is a well-known NP-complete problem, but it is pseudopolynomial: it can be solved in time O(n·t) where n is the number of elements and t is the target sum. This is polynomial in the numeric value of t, but exponential in the input length log t.

The PARTITION problem is:

PARTITION = {S | there exists a partition of S into S₁ and S₂ such that Σ(S₁) = Σ(S₂)}

where S is a set of positive integers, and the partition (S₁, S₂) satisfies S₁ ∪ S₂ = S and S₁ ∩ S₂ = ∅.

PARTITION is a special case of SUBSET-SUM where the target t = Σ(S)/2. It is NP-complete but also has a pseudopolynomial-time algorithm.

The BIN-PACKING decision problem is:

BIN-PACKING = {(S, c, k) | the items in S can be packed into k or fewer bins of capacity c}

where S is a set of items with sizes s₁, s₂, ..., s_n, c is the bin capacity, and k is the target number of bins.

The optimization version asks for the minimum number of bins needed. BIN-PACKING is NP-complete, and the optimization version is NP-hard.

The SET-COVER problem is:

SET-COVER = {(U, S, k) | there exists a subset S' ⊆ S such that |S'| ≤ k and ⋃(S') = U}

where U is a universe of elements, S is a collection of subsets of U, and k is the target size of the cover.

The optimization version asks for the smallest subset S' that covers all elements in U. SET-COVER is NP-complete, and the optimization version is NP-hard.

In the JOB-SCHEDULING problem, we have:

• A set of n jobs, each with processing time t_i
• m identical machines
• A deadline D

The decision problem asks if there exists a schedule assigning each job to one machine such that all jobs complete by time D.

JOB-SCHEDULING = {(J, m, D) | jobs J can be scheduled on m machines to complete by deadline D}

This problem is NP-complete for m ≥ 2, but polynomial-time solvable for m = 1.

The TRAVELING-SALESMAN decision problem (TSP) is:

TSP = {(G, c, k) | graph G has a Hamiltonian cycle of total cost at most k}

where G is a complete graph, c assigns a cost to each edge, and k is the budget.

The optimization version asks for the minimum-cost Hamiltonian cycle. TSP is NP-complete, and the optimization version is NP-hard. It remains NP-complete even when the costs satisfy the triangle inequality.

The KNAPSACK decision problem is:

KNAPSACK = {(S, v, w, W, V) | there exists S' ⊆ S such that Σ(w(S')) ≤ W and Σ(v(S')) ≥ V}

where S is a set of items, v(i) is the value of item i, w(i) is the weight of item i, W is the weight capacity, and V is the target value.

The optimization version asks for the maximum achievable value within the weight constraint. KNAPSACK is NP-complete, but like SUBSET-SUM, it has a pseudopolynomial-time algorithm running in O(n·W) time.

The class co-NP is defined as:

co-NP = {L | L̄ ∈ NP}

where L̄ = Σ* - L is the complement of language L.

Equivalently, L ∈ co-NP if there exists a polynomial-time verifier V such that:
x ∈ L if and only if for all certificates c of polynomial length, V(x, c) = 0.

The class NP ∩ co-NP contains languages that are in both NP and co-NP.

For a language L ∈ NP ∩ co-NP:

• There exists a polynomial-time verifier Vyes that verifies "yes" instances
• There exists a polynomial-time verifier Vno that verifies "no" instances

It is believed that NP ∩ co-NP contains problems that are unlikely to be NP-complete. Example problems in NP ∩ co-NP include integer factorization and parity games.

A language L is co-NP-complete if:

1. L ∈ co-NP
2. For all L' ∈ co-NP, L' ≤p L

Examples of co-NP-complete problems:

• TAUTOLOGY = {φ | φ is a Boolean formula that evaluates to true for all assignments}
• UNSAT = {φ | φ is an unsatisfiable Boolean formula}
• VALID = {φ | φ is a valid first-order formula (true in all models)}

If any co-NP-complete problem is in NP, then NP = co-NP.

The polynomial hierarchy is a sequence of complexity classes defined inductively:

• Σ0P = Π0P = P
• Σi+1P = NPΣiP (problems solvable by an NP machine with oracle access to Σ_iP)
• Πi+1P = co-NPΣiP (complements of problems in Σ_i+1P)

In particular:

• Σ1P = NP
• Π1P = co-NP
• Σ2P = NPNP
• Π2P = co-NPNP

The entire hierarchy is denoted PH = ⋃_i≥0 Σ_iP.

Examples of complete problems for higher levels of the polynomial hierarchy:

• Σ₂P-complete: QSAT2 = {φ | ∃x₁...∃xₙ∀y₁...∀yₘ φ(x₁,...,xₙ,y₁,...,yₘ) = 1}
  (Quantified Boolean formulas with one quantifier alternation, starting with ∃)
• Π₂P-complete: QSAT2' = {φ | ∀x₁...∀xₙ∃y₁...∃yₘ φ(x₁,...,xₙ,y₁,...,yₘ) = 1}
  (Quantified Boolean formulas with one quantifier alternation, starting with ∀)
• PSPACE-complete: QSAT = {φ | φ is a true quantified Boolean formula with any number of alternations}

A function problem is specified by a relation R(x, y) and asks: given input x, find a y such that R(x, y) holds (if such a y exists).

The class FP (Function Polynomial-time) consists of all function problems solvable in polynomial time:

FP = {f : Σ* → Σ* | f is computable in polynomial time}

For decision problems in P, the corresponding search problems are in FP.

An NP optimization problem (NPO) consists of:

• A set of problem instances I, recognizable in polynomial time
• For each instance x ∈ I, a set of feasible solutions S(x)
• A polynomial-time computable cost function f(x, y) for x ∈ I and y ∈ S(x)
• A goal to either maximize or minimize f(x, y)

An NPO problem is in PO (Polynomial-time Optimizable) if it can be solved optimally in polynomial time.

The relationship P = NP would imply PO = NPO, meaning all optimization problems with efficiently verifiable solutions could be solved optimally in polynomial time.

For NP-hard optimization problems, we often study approximation algorithms with guaranteed performance ratios:

• APX: Problems that can be approximated within some constant factor c
• PTAS (Polynomial-Time Approximation Scheme): Problems that can be approximated within a factor (1+ε) for any ε > 0, with running time polynomial in the input size (but possibly exponential in 1/ε)
• FPTAS (Fully Polynomial-Time Approximation Scheme): Like PTAS, but with running time polynomial in both the input size and 1/ε

There exist approximation-preserving reductions and APX-complete problems, analogous to NP-completeness for decision problems.