13 Reductions and NP-Complete Proofs

S. Sridhar

This module 34 focuses on reductions and proof of NP-Complete problems. The module illustrates the ways of reducing one problem to another. Then, the module illustrates the outlines of proof of NP-Complete problems with some examples. The objectives of this module are

· To understand the concept of Reductions among problems

· To Understand proof of NP-Complete problems

· To overview proof of some Important NP-Complete problems.

Computational Complexity

There are two types of complexity theories. One is related to algorithms, known as algorithmic complexity theory and another related to complexity of problems called computational complexity theory [2,3].

Algorithmic complexity theory [3,4] aims to analyze the algorithms in terms of the size of the problem. In modules 3 and 4, we had discussed about these methods. The size is the length of the input. It can be recollected from module 3 that the size of a number n is defined to be the number of binary bits needed to write n. For example, Example: b(5) = b(1012) = 3. In other words, the complexity of the algorithm is stated in terms of the size of the algorithm.

Asymptotic Analysis [1,2] refers to the study of an algorithm as the input size reaches a limit and analyzing the behaviour of the algorithms. The asymptotic analysis is also science of approximation where the behaviour of the algorithm is expressed in terms of notations such as big-oh, Big-Omega and Big- Theta.

Computational complexity theory is different. Computational complexity aims to determine complexity of the problems itself. In simple words, computational complexity is about the problem and not about the algorithms of problems. In computational complexity theory, two things are important. One is the upper bound and another is the lower bound of the algorithm. Lower and upper bounds define the limits of the algorithm. Upper bound indicates the worst case performance of the algorithm and lower bound indicates the best case performance of the given algorithm.

Class P and NP class of proble ms

P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine. A problem is feasible if it has a solution cost as a polynomial. All problems that can be solved in polynomial time is called polynomial time or class P problems. The class of decision problems that can be solved by a non-deterministic polynomial algorithm is called class NP problem.

Class NP problems are hard problems. ‘Hard’ in the sense, these problems require more computer resources such as CPU time and memory to solve these problems. Also, for most of these problems, no polynomial time algorithms exist for these problems. Also, it can be observed that most of these problems are combinatorial optimization problems and most of the combinatorial problems are hard problems. NP-Complete (or NPC) problems are a set of problems that are well connected. A problem x that is in NP, if known to have a polynomial time algorithm, it implies that polynomial time algorithm exist for all NP-Complete problems.

Reductions

Reduction algorithm reduces a problem to another problem. The input of a problem is called instance. Problem A is reduced to another problem B, if any instance of A “can be rephrased” as instance of B, the solution of which provides a solution to the instance of A [3]. There are two types of reduction. One is called Turing reduction and another is called Karp reduction.

Turing reduction

Let us assume two problems A and B. Problem B has a solution while problem A does not have any solution. Then reduction reduces attempts to solve problem A using procedure of solving problem B. In Turing reduction, problem A is solved using a procedure that solves B. Thus, efficient procedure for Problem A would be the efficient procedure for problem B. It can be shown mathematically denoted as follows:

A £P B

This implies that problem B is at least as hard as problem A and also in other words, problem A cannot be harder than problem B.

Karp Reduction

Karp reduction is another important concept in NP-Complete theory. It can be mathematically represented as follows:

A £P B

It illustrates that problem B is as hard as problem A and solving problem A cannot be harder than problem B.

Karp reduction algorithm reduces a problem to another problem. It can be denoted as follows:

A £P B

The input of a problem is called instance. Mathematically, if there exists a polynomial time computable function f, such that for instance w,

“w, w Î A Û f (w) Î B

Then, the reduction is called Karp reduction.

So, the steps of Karp reduction can be said follows:

1. Construct f.

2. Show f is polynomial time computable.

3. Prove f is a reduction, i.e show for instance w,

1. If wÎA then f(w)ÎB

2. If f(w)ÎB then wÎA

Polynomial time Turing reduction is also called Cook Reduction. It must be observed that all Karp reductions are Cook Reductions but vice versa is not true and Turing Reduction and Oracle Reduction are synonymous.

Karp reduction is suitable for NP-C proof, Cook reduction is general and Karp reduction is suitable for decision problems. Cook reduction is applicable for all problems in general [2,3]

Example of Reduction

Consider the example of reducing Hamiltonian path problem to Hamiltonian cycle problem.

Consider the following graph based on [1] shown in Fig. 1.

In Hamiltonian cycle, the aim is to find Hamiltonian cycle. In Fig 1, the Hamiltonian cycle is given as 4-3-1-2-4. The aim of reduction is to reduce a Hamiltonian cycle to Hamiltonian path and vice versa. The Hamiltonian path problem can be stated as follows:

Instance: a directed graph G=(V,E) and two vertices s¹tÎV.

Hamiltonian Path Problem: To decide if there exists a path from s to t, which goes through each node once.

To illustrate reduction, let us first restate the problem as follows:

1. If there exists a Hamiltonian path (v =s,v ,…,v =t) in the original graph, then

0 1 n

(u,v =s,v ,…,v =t,u) is a Hamiltonian cycle in the new graph. This is called completeness

0 1 n

property.

2. (u,s) and (t,u) must be in any Hamiltonian cycle in the constructed graph, thus removing u yields a Hamiltonian path from s to t. This is called soundness property.

In other words, Hamiltonian path is converted to a cycle by adding a source vertex to form a cycle and by removing it the cycle to a path.

So, the proof can be shown as follows:

1. Construct f.

2. Show f is polynomial time computable.

3. Prove f is a reduction, i.e show:

1. If wÎHAMPATH then f(w)ÎHAMCYCLE

2. If f(w)ÎHAMCYCLE then wÎHAMPATH

NP-Complete proof outline

Using the concept of reduction, the NP-Complete proof can be done. The proof outline is given

as follows:

1. Take one existing well known NP-Complete Problem

2. Reduce the NP-Complete problem to the given problem to be proved.

3. Argue that the given problem is as hard as the well-known NP-Complete problem.

Proof of SAT is NP- Complete

Let us consider a simple case of proving Formula Satisfiability problem as NP-Complete. Let us

use the outline of NP-Complete proof outline.

1. Let us take a well-known NP-Complete problem called Circuit Satisfiability problem. It can be recollected from module 33, that Circuit Satisfiability problem is given as follows:

Given a Boolean circuit, consisting of gates such as, NOT, OR, AND, is there any set of inputs that makes the circuit output TRUE. Simultaneously, one can check for circuit output NO also. Circuit satisfiability is a NP-Complete problem as per Cook-Levin theorem.

2. Now take the problem of Formula Satisfiability problem, SAT, for which the NP-Complete proof is required. The formula Satisfiability problem is given as follows:

Given a Boolean formula, determine whether this formula is satisfiable or not. SAT problem formula consists of following components:

A literal : x1 or x1

A clause C : x1 v x2 v x3

A formula : conjunctive normal form

C1& C2 & … & Cm

So, the proof outline based on [1,2,3] is given as follows:

Circuzt-SAT is NP-Complete. Given an assignment, we can just check that each clause is covered in polynomial time. It is also possible to reduce a circuit for a formula in a polynomial time. Let us consider the circuit shown in Fig. 3.

3. In the third step, one can conclude that as any Circuit-SAT solution will satisfy the formula SAT instance and a Circuit-SAT solution can set variables giving a SAT solution, the problems are equivalent. Therefore, one can conclude that formula SAT is NP-Complete.

3-SAT is NP-Complete

One can extend the above proof for showing that 3-SAT is also NP-Complete. In 3-SAT or 3SAT, there must be exactly 3 literals per clause. The problem can be formulated as follows:

Given 3-CNF formula, Is there an assignment that makes the formula to evaluate to TRUE.

3-SAT is NP. Given an assignment, we can just check that each clause is covered. Based on the outline, one can say 3-SAT is hard.

To give a proof of 3-SAT, a well-known NP-Complete problem SAT can be taken. SAT can be converted to 3-SAT in a polynomial time as shown below:

We will transform each clause independently based on its length. Suppose a clause contains k literals:

1. if k = 1 (meaning Ci = {z1} ), we can add in two new variables v1 and v2, and transform this into 4 clauses:

{v1, v2, z1} {v1, Øv2, z1} {Øv1, v2, z1} {Øv1, Øv2, z1}

2. if k = 2 ( Ci = {z1, z2} ), we can add in one variable v1 and 2 new clauses: {v1, z1, z2} {Øv1, z1, z2}

3. if k = 3 ( Ci = {z1, z2, z3} ), we move this clause as- is

4. if k > 3 ( Ci = {z1, z2, …, zk} ) we can add in k – 3 new variables (v1, …, vk-3) and k – 2 clauses:

{z1, z2, v1} {Øv1, z3, v2} {Øv2, z4, v3} … {Øvk-3, zk-1, zk}

To prove 3-SAT is hard, a reduction from SAT to 3-SAT must be provided. This is done using the above said rules.

Then in third step, the NPC of 3-SAT can be argued like this: Since any SAT solution will satisfy the 3-SAT instance and a 3-SAT solution can set variables giving a SAT solution, the problems are equivalent. In other words, If there were n clauses and m distinct literals in the SAT instance, this transform takes O(nm) time. Therefore, SAT = 3-SAT.

Summary

One can conclude from this module 34 that

Karp reduction reduces a problem A to problem B
NP completeness proof is to reduce a given problem to a well known NP-Complete problem
Using SAT, proofs can be given for many problems

References:

S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.
A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.
T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA 1992.