np-hardness [np-hardness]

— title: NP-Hardness —

Definition 1. NP-hardness [np-hard]

A Language $L$ is NP-hard if it is at least as hard as every problem in $NP$ , i.e., $\forall A \in NP,A\underset{P}{\leq}L$ .

There is nothing in this definition that’s really specific to $NP$ . We could switch it out for other complexity classes if we’d like.

Note that we don’t require our language to be in $NP$ ! $A_{TM}$ is NP-hard.

Definition 2. NP-Completeness [NP-complete]

A language $L$ is NP-complete if $L$ is NP-hard and $L \in \text{NP}$ .

Theorem. Cook-Levin Theorem

SAT is NP-complete.

Corollary.

3SAT is also NP-complete.

Theorem.

If B is NP-complete, $C \in \text{NP}$ , and $B\underset{P}{\leq}C$ , then $C$ is NP-complete.

Proof.

Need to show: $A\underset{P}{\leq}C,\forall A \in \text{NP}$
We know $A\underset{P}{\leq}B$ , i.e. you can solve $A$ in terms of $B$ .
- So $\exists$ a polytime computable $f:x \in A\Leftrightarrow f(x) \in B$ .
We know $B\underset{P}{\leq}C$ : $\exists$ a polytime computable $g:y \in B\Leftrightarrow g(y) \in C$
Let $h:\Sigma \ast \rightarrow\Sigma \ast$ be $h(x) = g\left( {f(x)} \right)$ . This is polytime computable.
- Has the properties: $x \in A\Leftrightarrow f(x) \in B\Leftrightarrow g(f(x) \in C$ .

Problem. CLIQUE [CLIQUE]

Given $G = \left( {V,E} \right)$ and $k$ , does there exist $U \subseteq V$ with $|U| \geq k$ such that $\left\{ {u,v} \right\} \in E$ for all distinct vertices $u,v \in U$ ?

$\text{CLIQUE} = \left\{ {\left\langle {G,K} \right\rangle:G\ \text{has a clique of size}\ k} \right\}$

No specification on size: in our example above, there are cliques of size 0 through 3

Theorem.

CLIQUE is NP-complete: i.e. CLIQUE is NP-hard, and CLIQUE is in NP.

Proof.

CLIQUE is in NP: because there exists a verifier that can check a possible clique in polytime.

CLIQUE is NP-hard: because 3SAT (known NP-hard problem) reduces to CLIQUE. How can we do that?

Proof. $\text{3SAT}\underset{P}{\leq}\text{CLIQUE}$ (reduction)

$x \in \text{3SAT}$ maps to $f(x) \in \text{CLIQUE}$

If $x = \left\langle \varphi \right\rangle$ where $\varphi$ is a satisfiable 3CNF formula, then $f(x) = \left\langle {G,k} \right\rangle$ where $G$ has a clique of size $k$ .

$x \notin \text{3SAT}$ maps to $f(x) \notin \text{CLIQUE}$

If $x = \left\langle \varphi \right\rangle$ where $\varphi$ has no satisfiable assignments, then $f(x) = \left\langle {G,k} \right\rangle$ where $G$ has no clique of size $k$ .
junk can map to junk

We can show 3SAT can be solved by finding a clique of size $k$ .

Connect every vertex in a block to every other vertex that is not its inverse.
Then, every clique of size $k$ is a possible satisfiable assignment.
We can’t have $x_{i}$ and $x_{i}^{\_}$ both being true: which is represented by no connecting edges.

We still need to “decode” $f(x) \in B$ to $x \in A$ … i.e. $f(x) \in \text{CLIQUE}\Rightarrow x \in \text{3SAT}$ .

Let $U$ be a clique of size $k$ . We must divy it up so that there is exactly one vertex in each group.
Given a $f(x) \in \text{CLIQUE}$ constructed from a $\text{3SAT}$ problem, then we find a satisfying $x \in \text{3SAT}$ .

Aside: suppose we want to ensure there is a clique of at least size $k - 1$ . We can make a separate, disconnected clique of $k - 1$ vertices. What’s this useful for? Don’t know yet…

cook-levin

theorem

When desigining a reduction: if you want to show that your reduction is correct, you need to show that:

$f$ is Polytime computable
$x \in A\Rightarrow f(x) \in B$
Either:
- $f(x) \in B\Rightarrow x \in A$ (converse)
- $x \notin A\Rightarrow f(x) \notin B$ (inverse)

In a reduction, it’s more typical to show $x \in A\Rightarrow f(x) \in B$ , as it’s often more straightforward. You often want to “decode” $f(x) \in B$ to obtain $x \in A$ .

Example. CLIQUE problem

Given $G = \left( {V,E} \right)$ and $k$ , does there exist $U \subseteq V$ with $\left. |U \middle| \geq k \right.$ such that $\left\{ {u,v} \right\} \in E$ for all distinct vertices $u,v \in U$ ?

$\text{CLIQUE} = \left\{ {\langle G,K\rangle:G\ \text{has a clique of size}\ k} \right\}$

No specification on size. In our example above, there are cliques of size $0$ through $3$ .

Theorem: …