Reductions Between NPCs

| Tags Algorithm

To Be Continued

NPC is short for NP-complete problems, it is a class of decision problems. A decision problem $$L$$$is NP-complete if it is in the set of NP problems and also in the set of NP-hard problems. An NP problem is NP-complete if all other NP problems can reduced to it. Below is the reduction relations between NP-complete problems. SAT to 3SAT Given an instance $$I$$$ of SAT, replace any clauzse with more 3 literals, such as $$(a_1 \vee a_2 \vee … \vee a_k)$$$where $$k > 3$$$, with a set of clauses $$(a_1 \vee a_2 \vee y_1)(\overline y_1 \vee a_3 \vee y_2) … (\overline y_{k-3} \vee a_k-1 \vee a_k)$$

where the $$y_i$$$are new variables. The result is a 3SAT instance $$I'$$$. The conversion from $$I$$$to $$I'$$$ is clearly polynomial time.

3SAT to Independent Set

The input of Independent Set is a graph $$G$$$and a number $$g$$$, the problem is to find a set of $$g$$$pairwise non-adjacent vertices. Given an instance $$I$$$ of 3SAT, create an instance $$(G, g)$$$of Independent Set as follows, 1. Graph G has a triangle(edge or vertex) for each clause, with vertices labeled by the clause's literals 2. Add edge between any two vertices that represent opposite literals. 3. The goal $$g$$$ is set to the number of clauses.

In ZOE matrix, each column represents a boy-girl-pet triple, and each row represents a boy(or girl, or pet), and if $$A_{ij} = 1$$$, it states that the ith item is in the jth triple. Because each item must be exactly in one of these triples, so the sum of row is 1. For example, given an instance of 3D Matching described in the graph below, $$x_i, y_i, z_i$$$ represent items, and $$t_i$$$represents triple, so the corresponding instance of ZOE is $$\mathbf{A}= \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$$ each row represents a item, from top to bottom are $$x_1, x_2, …, z_4$$$, and each column represents a triple, from left to right are $$t_1,…, t_4$$$. ZOE to Subset Sum Both of these problems are special cases of ILP, one with many equations but only 0-1 coefficients, and the other with a single equation but arbitrary integer coefficients. For example, given an instance of ZOE: $$\mathbf{A} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix}$$ we are looking for a set of columns of $$A$$$ that, added together, make up the all-1's vector. But if we think of the columns as binary integers(read from top to bottom), we are look for a subset of the integers $$\{18, 5, 4, 8 \}$$$that add up to the binary integer $$11111_2 = 31$$$. And this is an instance of Subset Sum.

To avoid the problem of carry, that caused by adding binary integers, we can think of each column as an integer in base n+1, this way, since at most n integers are added, add all their digits are 0 and 1, there won't be any carry.

ZOE to ILP

ZOE is a special case of ILP, but it still takes a little work to reduce ZOE to ILP. In ILP, we are looking for an integer vector $$x$$$taft satisfies $$Ax \leq b$$$, for given matrix $$A$$$and vector $$b$$$. To write an instance of ZOE in this precise form, there are two steps,

1. for $$Ax = 1$$$in ZOE, we rewrite it to $$Ax \leq 1$$$ and $$-Ax \leq -1$$$. 2. for each $$x_i$$$, we rewrite it to $$x_i \leq 1$$$and $$-x_i \leq 0$$$.

After these two steps, we get an instance of ILP.

ZOE to Rudrata Cycle

It needs two steps to convert an instance of ZOE into an instance of Rudrata Cycle.

1. ZOE => Rudrata Cycle with Paried Edges
2. Rudrata Cycle with Paired Edges => Rudrata Cycle

To visits all internal nodes in graph above, there are only two ways, the first way is marked red which starts from a, ends up with b, and the other way starting from c, ending up d. This gadget can be used to get grid of pairs edges in the "Rudrata Cycle with Paired Edges".

To Be Done

Rudrata Cycle to TSP

These two problems are similar to each other, and the reduction is no so hard, given an instance $$G=(V,E)$$$of Rudrata Cycle, convert it to an instance of TSP as below, 1. The set of cities is the same as $$V$$$.
2. The distance between cities $$u$$$and $$v$$$ is 1 if $$\{u,v\}$$$is an edge of $$G$$$ and 2 otherwise.
3. The budget of TSP instance is equal to the number of nodes, $$|V|$$$. If there is a tour within the budget of the TSP instance, then the tour is a Rudrata Cycle in $$G$$$.

Rudrata Path to Rudrata Cycle

Given an instance $$(G=(V,E), s, t)$$$of Rudrata Path, just add a node $$x$$$ to $$V$$$, and $$\{s,x\}, \{t,x\}$$$ to $$E$$$to construct an instance $$G'=(V', E')$$$ of Rudrata Cycle.

If there a rudrata cycle in $$G'$$$, then the cycle must include $$\{s,x\}, \{t,x\}$$$, just by removing these two edges we can get a rudrata path.

Any NP Problem to SAT

There are two steps to reduce a problem $$A$$$in NP to SAT. 1. Search problem => Circuit SAT 2. Circuit SAT => SAT The main feature of a search problem is that any solution to it can be quickly checked, there is a algorithm $$C$$$ that checks, given an instance $$I$$$and a proposed solution $$S$$$, whether or not $$S$$$is a solution of $$I$$$.

Unsolvable Problems

For all NP-complete problems, three are some algorithms which can solve them, although the time may not be polynomial.But there are some problems that can never be solved, that is there is no algorithm to solve it.

Suppose we have a program terminates(p, x), which can tell us that whether the program p with input x will terminate. Then we can use it to construct a evil program which is impossible to determinate whether it will terminate.

function paradox(p, x)
{
while(terminates(p, x));
}


To Be Done