Reductions Between NPCs

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.

The graph below corresponding to \($(\\overline x \\vee y \\vee \\overline z)(x \\vee \\overline y \\vee z)(x \\vee y \\vee z)(\\overline x \\vee \\overline y)\)$

Independent Set to Vertex Cover

This reduction is very easy, we just need to notice that a set of nodes \($S\)$ is a vertex cover of graph \($G=(V, E)\)$ if and only if the remaining nodes, \($V-S\)$ are an independent set of \($G\)$.

Independent Set to Clique

The input of Clique is a graph \($G\)$ and a number \($g\)$, the problem is to find a \($g\)$ vertices such that all possible edges between them are present.

This reduction is also very easy. Define the complement of a graph \($G=(V,E)\)$ to be \($\\overline G=(V, \\overline E)\)$, where \($\\overline E\)$ contains precisely those unordered pairs of vertices that are not in \($E\)$. Then a set of nodes \($S\)$ is an Independent Set of \($G\)$ if and only if \($S\)$ is a clique of \($\\overline G\)$.

Given an instance \($(G,g)\)$ of Independent Set, simply mapping it to the corresponding instance \($(\\overline G, g)\)$ of Clique, and the solution to both is identical.

3SAT to 3D Matching

In graph theory, a matching or independent edge set in a graph is a set of edges without common vertices. 3D matching is a generalization of matching to 3-uniform hypergraphs. Let \($X\)$, \($Y\)$, \($Z\)$ be finite, disjoint sets, and let \($T\)$ be a subset of \($X \\times Y \\times Z\)$. That is \($T\)$ consists of triples\($(x, y, z)\)$ such that \($ x \\in X, y \\in Y, z \\in Z\)$. Now \($ M \\subset T\)$ is a 3D matching if the following holds: for any two disjoint triples \($(x_1, y_1, z_1) \\in M\)$ and \($(x_2, y_2, z_2) \\in M\)$, we have \($x_1 \\neq x_2, y_1 \\neq y_2, z_1 \\neq z_2\)$.

3SAT to 3D Matching is really trivial and hard to think. For simplicity, we may assume that each matching of the 3D Matching is a girl-boy-pet triple, the problem of 3D Matching is to find all matching satisfying that each girl/boy/pet is in exactly one triple. Consider the following set of four triples, each represented by a red node joining a boy, girl and pet

suppose that boys \($b_0, b_1\)$ and girls \($g_0, g_1\)$ are not involved in any other triples except the above triples. Then the matching must contain either the two triples \($(b_0, g_1, p_0)\)$, \($(b_1, g_0, p_2)\)$ or \($(b_0, g_0, p_1)\)$, \($(b_1, g_1, p_3)\)$. Therefore, this “gadget” has two possible states, just like a boolean variable, so it can be used to represent a variable in 3SAT.

To Be Continued

3D Matching to ZOE

Given an instance of 3D matching(m boys, m girls, m pets and n boy-girl-pet triples). In the language of ZOE, we have 0-1 variables \($x\_1, x\_2, …, x\_n\)$, one per triple, where \($x_i =1\)$ means that the i-th triple is chosen for the matching, and \($x_i=0\)$ means that it is not chosen.

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

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:

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