Skip to content

Poly-time Reductions

Poly-time algorithms can scale to huge problems.

Poly-time algorithm can solve: shortest path, min cut, 2-SAT, matching, primality testing, linear programming...

Probably can't solve: longest path, max cut, 3SAT, integer linear programming...

Cook Reduction

Problem \(X\) polynomial-time (Cook) reduces to problem \(Y\) if arbitrary instances of problem \(X\) can be solved using

  • Polynomial number of standard computational steps, and
  • Polynomial number of calls to oracle that solves problem \(Y\).

Written \(X\leq_p Y\).

  • If \(X\) is not solvable in poly time, \(Y\) is not either.
  • If \(Y\) is solvable in poly time, \(X\) is too.
  • If \(Y\) is not solvable in poly time, we don't know about \(X\).

Transitivity: \(X\leq_p Y\and Y\leq_p Z\Rightarrow X\leq_p Z\).

Equivalence: \(X\leq_p Y\and Y\leq_p X\Rightarrow X\equiv_p Y\).

Packing and Covering Problems

Independent set: Given a graph \(G\) and an integer \(k\), is there a subset of \(k\) vertices s.t. no two are adjacent?

Vertex cover: Given a graph \(G\) and an integer \(k\), is there a subset of \(k\) vertices such that each edge is incident to at least one vertex in the subset?

Theorem: Independent set \(\equiv_p\) Vertex cover.

Set cover: Given a universe set \(U\), a collection \(S\) of subsets of \(U\), and an integer \(k\), are there \(\leq k\) of these subsets whose union is equal to \(U\)?

Theorem: Vertex cover \(\leq_p\) Set cover

Satisfiability

Literal, clause, CNF

3SAT \(\leq_p\) Independent set

Decision, Search, and Optimization Problems

Decision: Does there exist a vertex cover of size \(\leq k\)?

Search: Find a vertex cover of size \(\leq k\).

Optimization problem: Find a vertex cover of minimum size.

These 3 problems poly-time reduce to one another! equivalent

P vs. NP

P

Decision problem

  • Problem \(X\) is a set of strings.
  • Instance \(s\) is one string
  • Algorithm \(A\) solves problem \(X\): \(A(s)=yes\) if \(s\in X\), \(no\) otherwise.

Definition: Algorithm \(A\) runs in polynomial time if for every string \(s\), \(A(s)\) terminates in \(\leq p(|s|)\) steps.

\(P\) is the set of decision problems for which there exists a poly-time algorithm.

NP

Definition: Algorithm \(C(s,t)\) is a certifier for problem \(X\) if for every string \(s\): \(s\in X\) iff there exists a string \(t\) s.t. \(C(s,t)=yes\).

\(NP\) is the set of decision problems for which there exists a poly-time certifier.

  • \(C(s,t)\) is a poly-time algorithm
  • Certificate \(t\) is of polynomial size w.r.t. \(|s|\).

For 3SAT, a certificate is an assignment of truth values to the Boolean variables.

Certifier is to check that each clause has at least one true literal.

So \(SAT\in NP, 3SAT\in NP\).