np-hardness [np-hardness]

— title: NP-Hardness —

Definition 1. NP-hardness [np-hard]

A Language LL is NP-hard if it is at least as hard as every problem in NPNP, i.e., ∀A∈NP,A≤PL\forall A \in NP,A\underset{P}{\leq}L.

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

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

Definition 2. NP-complete [np-complete]

cook-levin

theorem

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

  1. ff is Polytime computable
  2. x∈A⇒f(x)∈Bx \in A\Rightarrow f(x) \in B

  3. Either:

    • f(x)∈B⇒x∈Af(x) \in B\Rightarrow x \in A (converse)
    • x∉A⇒f(x)∉Bx \notin A\Rightarrow f(x) \notin B (inverse)

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

Example. CLIQUE problem

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

CLIQUE={⟨G,K⟩:Ghas a clique of sizek}\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 00 through 33.

Theorem: …