Reduction And Intractibility

Complexity Classes

With complexity classes, we aim to determine the “difficulty” of a problem. They allow us to know what is solvable in polynomial time and what isn’t. This is what the $P = NP$ problem deals with. $P=NP$ implies that for any polynomial time verification solution, there is a polynomial time solver for the problem. Most computer scientists believe that $P \neq NP$. Assuming $P \neq NP$,

P

Loosly, $P$ is defined as the set of all problems such that there is a polynomial time solution. This means that the solution to a problem $a \in P$ runs in $O(n^k)$ time where $k$ is some constant.

NP

Loosly, $NP$ is defined as the set of all problems such that there is a polynomial time verification.

NP-Hard

Loosly, $NP-Hard$ problems are such that any problem in $NP$ can be reduced to that $NP-Hard$ problem. Notice that the problen need not be in $NP$. We have a special class of problems for those, as seen below.

NP-Complete

Loosly, $NPC$ problems are considered the hardest problems in $NP$. Basically, any problem in $NP$ can be reduced to a $NPC$ problem. This means that any $NPC$ problem can be reduced to another $NPC$ problem. As you can see $NPC \subset NP-Hard$

Reductions

Reductions allow us to to determine the difficulty of a problem.

We say that for two problems $Y$ and $X$, $Y \leq_p X$ if instances of $Y$ can be solved by a polynomial amount of computation plus a polynomial number of calls to a “black-box” that solves $X$.

You can think of reduction as calling a library as part of your solution. For example.

In order for reductions to work, we have to have some set of problems that are known to be $NPC$. A common starting point is $SAT$, or boolean satisfiability. Karp has a famous paper containing 21 $NPC$ problems you can view here. Here are some popular $NPC$ Problems

3SAT

For $3SAT$, we are given a boolean formula $\Phi$ in CNF form (conjunctive normal form) such that for each clause $C_r$, $C_r = l_1 \lor l_2 \lor l_3$. We return true if this boolean formula is satisfiable.

Clique

We say that a graph $G$ has a clique of size $k$ if there is a set of vertices $I$ such that $\left\vert{I}\right\vert = k$ and $I$ is fully connected.

We will give a reduction from $CLIQUE$ to $3SAT$.

We can define our function $A$ as follows:

For each $C_r = ( l_1 \lor l_2 \lor l_3)$ for $r =1,\ldots,k$ , create corresponding vertices $v_1, v_2, v_3$ in $V$. Now add an edge between $v_i^r$ and $v_j^s$ if $r \neq s$ and the corresponding literals are consistent( You can’t connect $\neg l_1$ to $l_1$). Now we se that if there is a clique of size $k$, there is a satisfiable boolean formula for 3SAT.

Vertex Cover

We will prove that $VERTEX\ COVER \leq_p CLIQUE$.

We say that a graph $G = (V,E)$ has a vertex cover of size $k$ if there is a subset of vertices $S \subset V$ that covers all edges in the graph and $\left\vert{S}\right\vert = k$.

Given a graph $G = (V,E)$, we can generate the complement graph $\bar{G} = (V, \bar{E})$. Now, we solve the problem $CLIQUE(\bar{G}, \left\vert{V}\right\vert - k)$, and return $YES$ if we have a solution, and $NO$ otherwise.

You can see a full proof here