not on exam

Poly-Time Reductions

General definition of Reduction $y \leq pX : Y$ reduces to $x$ poly-time.

• say we have a blackbox to solve $x$. We give it an instance of $y$.

If $x$ is solvable in polynomial time, then $y$ is solvable in polynomial time. The contrapositive is that: if $y$ is not solvable in polynomial time, then $x$ is not solvable in polynomial time.

• i.e., $x$ is no easier than $y$.

Desiderata: suppose we could solve problem $Y$ in polynomial time. What else could we solve in polynomial time?

Reduction: probelm $X$ polynomial-time (cook) reduces to problem $Y$ if arbitrary instances of porblem $X$ can be solved using:

• polynomial number of standard computational steps, plus
• polynomial number of calls to oracle (a computational model supplemented by special piece of hardware that solves instaces of $Y$ in a single step) that solves problem $Y$.

Notation: $X \leq _P Y$

Note: we pay for time to write down instance of $Y$ sent to oracle $\implies$ instances of $Y$ must be of polynomial size.

Novice mistake: confusing $X \leq _P Y$ with $Y \leq_P X$

Design algorithms: If $X \leq _P Y$ and $Y$ can be solved in polynomial time, then $X$ can be solved in polynomial time

Establish intractability: If $X \leq _P Y$ and $X$ cannot be solved in polynomial time, then $Y$ cannot be solved in polynomial time.

Establish equivalence: If both $X \leq _P Y$ and $Y \leq _P X$, we use notation $X \equiv _P Y$. In this case, $X$ can be solved in polynomial time iff $Y$ can be.

packing and covering problems

Are these questions the same in terms of complexity? (i.e., can O reduce to D or can D reduce to O)

• Optimization question: what is the size of the largest possible independent set?
• Decision question: is there an independent set of size at least $k$

Answer: if you have the solution to the optimization problem, you have the solution to the decision question. Therefore, $D\leq_P O$, i.e., D can reduce to O. You can make calls of D again and again to find the answer for O. Therefore, $O \leq_P D$ and $O \equiv_P D$.

More formally,

Independent-Set: given a graph $G=(V,E)$ and an integer $k$, is there a subset of $k$ (or more ) verticies such that no two are adjacent?

Vertex-Cover: given a graph $G=(V,E)$ and an integer $k$, is there a subset of $k$ (or fewer) verticies such that each edge is incident to at least one vertex in the subset?

Do vertex cover and independent set reduce to one another? Theorem: Independent-Set $\equiv_P$ Vertex-Cover. Proof: we show $S$ is an independent set of size $k$ iff $V-S$ is a vertex cover of size $n-k$.

$\Rightarrow$

• Let $S$ be any independent set of size $k$.
• $V-S$ is of size $n-k$
• Consider an arbitrary edge $(u,v) \in E$
• $S$ independent
  • $\implies$ either $u \notin S$, or $v \notin S$ or both.
  • $\implies$ either $u \in V-S$, or $v \in V-S$, or both
• Thus, $V-S$ covers $(u,v)$.

$\Leftarrow$

• Let $V-S$ be any vertex cover of size $n-k$
• $S$ is of size $k$.
• Consider an arbitrary edge $(u,v) \in E$.
• $V-S$ is a vertex cover
  • $\implies$ either $u\in V-S$, or $v \in V-S$ or both
  • $\implies$ either $u \notin S$ or $v \notin S$ or both
• Thus, $S$ is an independent set

Set Cover

Given a set $U$ of elements, a collection $S$ of subsets of $U$, and an integer $k$, are there $\leq k$ of these subsets whose union is equal to $U$?

Sample application:

• $m$ available pieces of software
• $U$ of $n$ capabilities that we would like our system t have
• The $i^{th}$ piece of software provides the set $S_i \subseteq U$ of capabilities
• Goal: achieve all $n$ capabilities using fewest peices of software.

Theorem: vertex-cover $\leq_P$ set-cover. Proof:

• given a vertex-cover instance $G=(V,E)$ and $k$, we construct a Set-Cover instance $(U,S,k)$ that has a set cover of size $K$ iff $G$ has a vertex cover of size $k$.

Construction:

• universe $U=E$
• include one subset for each node $v\in V$: $S_v = \{e\in E: e \text{ incident to } v\}$

Vertex cover reduces to set cover. Lemma: $G= (V,E)$ contains a vertex cover of size $k$ iff $(U,S,k)$ contains a set cover of size $k$. Proof: $\Rightarrow$

• Let $X \subseteq V$ be a vertex cover of size $k$ in $G$. Then $Y = \{S_v : v \in \}$ is a set cover of size $k$.
• "yes" instances of vertex-cover are solved correctly.

$\Leftarrow$

• Let $Y \subseteq S$ be a set cover of size $k$ in $(U,S,k)$. Then $X = \{ v: S_v \in Y \}$ is a vertex cover of size $k$ in $G$.
• "no" instances of Vertex-Cover are solved correctly.

Constraint satisfaction problems

Satisfiability terms:

• literal: a boolean variable or its negation. $x_i$ or $\bar{x_i}$
• clause: a disjunction of literals $C_j = x_1 \lor \bar{x_2} \lor x_3$
• conjunctive normal form (CNF): a propositional formula $\Phi$ that is a conjunction of clauses. $\Phi = C_1 \land C_2$
• sat: given a CNF formula $\Phi$, does it have a satisfying truth assignment?
• 3-sat: sat where each clause contains exactly 3 literals (and each literal corresponds to a different variable)

$\Phi = (\bar x_1 \lor x_2 \lor x_3) \land (x_1 \lor \bar x_2 \lor x_3) \land (\bar x_1 \lor x_2 \lor x_4)$

• yes instance occurs when $x_1 = x_2 =$ true and $x_3 = x_4 =$ false.

key application: elecetronic design automation (EDA)

There does not exist a poly-time algorithm for $3-sat$.

$P$ vs $NP$ this hypothesis is equivalen to $P \neq NP$ conjecture.

3-satisfiability reduces to independent set

Theorem: $3-sat \leq_P Independent-set$ Proof: given an instance $\Phi$ of $3-SAT$, we construct an instance $(G,k)$ of Independent-set that has an independent set of size $k=|\Phi|$ iff $\Phi$ is satisfiable

Construction:

• $G$ contains 3 nodes for each clause, one for each literal
• connect 3 literals in a clause in a triangle
• connect litearl to each of its negations.

Lemma: $\Phi$ is satisfiable iff $G$ contains an independent set of size $k=\Phi$.

Proof $\Rightarrow$ consider any satisfying assignment for $\Phi$

• select one true litearl from each clause/triangle
• this is an independent set of size $k=\Phi$.
• "yes" instances of 3-sat are solved correctly.

$\Leftarrow$ let $S$ be indepnedent set of size $k$

• $S$ must contain exactly one node in each triangle
• set these literals to true (and remaining literals consistently)
• all clauses in $\Phi$ are satisfied
• "no" instances of 3-sat are solved correctly.

Review

Basic reduction strategies:

• simple equivalence
• special case to general case
• encoding with gadgets ($3-Sat \leq_P Independent-set)

transitivity: if $X \leq_P y$ and $Y \leq_P Z$, then $X \leq_P Z$ proof idea: compose the two algorithms. e.g., $\text{3-SAT} \leq_P \text{Independent-Set} \leq_P \text{Vertex-Cover} \leq_P \text{Set-Cover}$.