Unit 14: More on Intractable Problems

I. Foundations of Computational Intractability

Computational complexity classifies problems by the resources required to solve them as input size grows. Intractability usually means that no polynomial-time algorithm is known and that strong complexity-theoretic evidence suggests none exists.

A. Governing Concepts and Conventions

The study of NP-hardness and NP-completeness depends on decision problems, efficient verification, and polynomial-time transformations.

• Problem instance: A particular input (x) to a computational problem; its size is denoted by (n=|x|), measured in symbols or bits.
• Decision problem: A problem whose answer is either “yes” or “no,” such as whether a graph contains a clique of size at least (k).
• Class (P): The set of decision problems solvable by a deterministic algorithm in polynomial time.

T(n) = O(n^c)

• (T(n)) is running time.
• (n) is input size.
• (c) is a fixed constant independent of (n).

• Class (NP): The set of decision problems whose “yes” instances have certificates verifiable in polynomial time by a deterministic algorithm.
  • For Hamiltonian Cycle, a certificate is an ordering of all vertices.
  • Verification checks each required edge and confirms that every vertex occurs once.
• Equivalent view of (NP): These are problems solvable in polynomial time by a nondeterministic Turing machine.
• Central unresolved question: Whether (P=NP). Since (P\subseteq NP), the issue is whether efficient verification always implies efficient solution.
• Intractability qualification: NP-completeness does not prove that a problem requires exponential time; it shows that a polynomial-time solution would imply polynomial-time solutions for every problem in (NP).
• Input encoding: Complexity depends on representation. An integer (N) requires (\Theta(\log N)) bits in binary, so a running time polynomial in (N) may be exponential in the actual input length.

II. NP-Hard Problems — At Least as Hard as Every Problem in NP

A. Definition and Classification

A problem (H) is NP-hard if every problem in (NP) can be transformed into (H) using a polynomial-time reduction.

• Formal condition: (H) is NP-hard when

For every L in NP, L <=p H

• (L) is any decision problem in (NP).
• (\leq_p) denotes polynomial-time many-one reducibility.
• (H) need not itself belong to (NP).

• Scope: NP-hard problems may be decision, search, or optimization problems; some can even be undecidable.
• Relationship to NP-completeness: Every NP-complete problem is NP-hard, but an NP-hard problem is NP-complete only if it is also a decision problem in (NP).
• Consequence: If any NP-hard problem has a polynomial-time algorithm, then every problem in (NP) can be solved in polynomial time and (P=NP).

B. Examples of NP-hard problems

NP-hard examples commonly occur as optimization versions of NP-complete decision problems.

• Travelling Salesperson optimization problem: Given weighted cities, find a minimum-cost tour visiting each city exactly once and returning to the start.
  • Its decision version asks whether a tour of cost at most (B) exists and is NP-complete.
  • An optimization solver would answer the decision version by comparing the optimal cost with (B), so optimization is NP-hard.
• Minimum graph coloring: Determine the chromatic number (\chi(G)), the smallest number of colors needed so adjacent vertices receive different colors.
  • The related decision problem asks whether (\chi(G)\leq k).
  • Computing (\chi(G)) exactly is NP-hard.
• Knapsack optimization: Select items to maximize total value without exceeding capacity (W).

maximize   sum(v_i x_i)
subject to sum(w_i x_i) <= W
           x_i in {0,1}

• (v_i) and (w_i) are the value and weight of item (i).
• (x_i=1) means item (i) is selected.
• Exact optimization is NP-hard, while the corresponding decision form is NP-complete.
  • Job-shop scheduling optimization: Minimize completion time while respecting machine and operation-order constraints; exact general formulations are NP-hard.
  • Halting problem: Determining whether an arbitrary program halts is undecidable and can be classified as NP-hard under suitable polynomial reductions.
• It is not NP-complete because it is not decidable and therefore is not in (NP).

C. Practical Significance and Limitations

NP-hardness directs algorithm design toward methods other than universally efficient exact computation.

• Restricted instances: A hard general problem may become polynomial-time solvable on trees, bounded-degree graphs, fixed dimensions, or other special structures.
• Approximation: An approximation algorithm sacrifices optimality for a provable quality bound; metric TSP, for example, admits constant-factor approximation.
• Parameterized algorithms: Running time such as (O(f(k)n^c)) isolates exponential growth in a parameter (k), rather than in the full input size.
• Heuristics: Greedy search, local search, and branch-and-bound can perform well in practice but may lack polynomial worst-case guarantees.
• Pseudo-polynomial behavior: The dynamic program for integer knapsack runs in (O(nW)), polynomial in capacity (W) but not in its binary length (\log W).

III. NP-Complete Problems — The Hardest Decision Problems in NP

A. Definition and Proof Requirements

A decision problem (C) is NP-complete precisely when it is both in (NP) and NP-hard.

• Membership requirement: Show (C\in NP) by specifying a polynomial-size certificate and a polynomial-time verifier.
• Hardness requirement: Show that a known NP-complete problem (A) satisfies (A\leq_p C).
• Direction rule: To prove a new problem hard, reduce the known hard problem to the new problem, not the reverse.
• Polynomial implication: If (C\in P) for any NP-complete (C), then (P=NP); if (P\neq NP), no NP-complete problem belongs to (P).

B. Examples of NP-complete problems

Canonical NP-complete problems represent logic, graphs, sets, numbers, routes, and schedules.

• Boolean Satisfiability (SAT): Decide whether a Boolean formula has an assignment making it true.
  • A certificate lists truth values for all variables.
  • The verifier evaluates the formula in time polynomial in its length.
• 3-SAT: Decide satisfiability when the formula is a conjunction of clauses containing exactly three literals, such as

(x OR not y OR z) AND (not x OR y OR w)

• (x,y,z,w) are Boolean variables.
• A literal is a variable or its negation.
  • CLIQUE: Given (G=(V,E)) and integer (k), decide whether (G) contains (k) vertices that are pairwise adjacent.
  • VERTEX COVER: Given (G) and (k), decide whether at most (k) vertices touch every edge.
• A set (S\subseteq V) is a vertex cover if every ((u,v)\in E) has (u\in S) or (v\in S).
  • Hamiltonian Cycle: Decide whether a graph contains a cycle visiting every vertex exactly once.
  • SUBSET SUM: Given integers (a_1,\ldots,a_n) and target (t), decide whether some subset sums exactly to (t).
  • TSP decision problem: Given a weighted graph and bound (B), decide whether a tour of total weight at most (B) exists.
  • Distinguishing feature: Each listed decision problem has efficiently verifiable “yes” certificates, unlike an unrestricted optimization output or an undecidable problem.

C. Complementary Complexity

NP-completeness concerns efficiently verifiable “yes” answers, while complementary classes clarify the status of “no” answers.

• Class (coNP): A language belongs to (coNP) when its complement belongs to (NP).
• Example: TAUTOLOGY asks whether a Boolean formula is true under every assignment and is (coNP)-complete.
• Open relationship: Whether (NP=coNP) is unknown; (P=NP) would imply (NP=coNP).
• Logical caution: Failure to find a certificate for “yes” does not itself provide a polynomially verifiable certificate for “no.”

IV. Cook’s Theorem — The Foundation of NP-Completeness

A. Formal Statement and Conditions

Cook’s theorem, independently established in closely related form by Stephen Cook and Leonid Levin, states that Boolean satisfiability is NP-complete.

• Membership: SAT belongs to (NP) because a truth assignment is a certificate that can be checked by evaluating the formula.
• Hardness: For every language (L\in NP), there is a polynomial-time transformation (f) such that

x in L  if and only if  f(x) is satisfiable

• (x) is an input instance.
• (f(x)) is a Boolean formula.
• The formula’s size is polynomial in (|x|).

B. Cook's theorem

The theorem encodes a polynomial-time nondeterministic computation as a satisfiable Boolean formula.

• Computation tableau: Arrange the machine’s configurations by time step, recording state, tape symbols, and head position.
• Boolean variables: Variables state which symbol, state, or head location occupies each tableau cell at each time.
• Constraint groups:
  • Initial constraints: Encode the input and starting configuration.
  • Uniqueness constraints: Ensure each cell has one symbol and the machine has one state and head position.
  • Transition constraints: Enforce the Turing machine’s legal local transition rules.
  • Acceptance constraint: Require an accepting state within the polynomial time bound.
• Correctness: The formula is satisfiable exactly when an accepting computation exists.
• Polynomial size: A polynomial-time machine has only polynomially many time steps and relevant tape cells, so the tableau and formula remain polynomial in input length.
• Historical significance: Cook’s theorem supplied the first NP-complete problem, enabling later hardness proofs through chains of reductions rather than fresh machine encodings.

V. Polynomial-Time Reduction — Transferring Computational Difficulty

A. Purpose and Principle

A reduction converts instances of one problem into instances of another while preserving answers and using only polynomial time.

• Definition: (A\leq_p B) if a polynomial-time computable function (f) satisfies

x in A  if and only if  f(x) in B

• (A) is the source problem.
• (B) is the target problem.
• (f) maps each instance while preserving “yes” and “no.”

B. Problem reduction

Problem reduction establishes hardness by showing that solving the target would also solve an already hard source problem.

• Reduction algorithm:

SolveA(x):
    y = f(x)
    return SolveB(y)

• (x) is an instance of (A).
• (y=f(x)) is the corresponding instance of (B).
• If both steps are polynomial, then a polynomial algorithm for (B) gives one for (A).

• Transitivity: If (A\leq_p B) and (B\leq_p C), then (A\leq_p C).
• Hardness proof pattern:
  1. Choose a known NP-complete problem (A).
  2. Construct a polynomial transformation from (A) to candidate (B).
  3. Prove both directions of answer preservation.
  4. Prove that construction time and output size are polynomial.
  5. Separately prove (B\in NP) if NP-completeness, rather than only NP-hardness, is required.
• Concrete reduction: CLIQUE reduces to VERTEX COVER using graph complementation. A graph (G) has a clique of size (k) exactly when its complement (\overline{G}) has a vertex cover of size (|V|-k).
• Common error: Showing (B\leq_p A) demonstrates that (B) is no harder than (A); it does not establish that (B) inherits (A)’s hardness.