12 Overview of NP-Complete problems

S. Sridhar

This module 33 focuses on NP-Complete problems. The module also discusses about Class P and NP problems. This module also introduces the theory of NP-Complete problems. The objectives of this module are

 

·         To understand the P and NP Class

·         To understand NP-Complete problems

·         To know some NP-Complete problems

 

Computational Complexity

 

There are two types of complexity theory. One is related to algorithm complexity analysis called algorithmic complexity theory and another related to 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 lower bound on the efficiency of all the algorithms for a given problem and Computational complexity is measured independently of the implementation. In simple words, computational complexity is about the problem and not the algorithm. 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 defines 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.

 

Solvability of Problems

 

A problem is solvable if there exists a program that always terminate and gives the answer.

 

Solvability of the problems is related to the tractability of the problem [2,3].

 

A problem is tractable if it is solvable and we can say Time(x)≤(some polynomial). The problems that can be solved using run time less than polynomial is called polynomial time algorithms.

 

Class P 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. Some of the examples of Class P problems are

 

 

·         Searching

·         Element uniqueness

·         graph connectivity

 

Polynomial time algorithms also give a notion of efficient algorithms. All polynomial time algorithms are efficient algorithms as the problem can be solved. How about O(n log n)? or O(n2) ? yes. These algorithms are polynomial algorithms and hence solvable. On the other hand, the algorithms having complexity like O(2n) or O(n!) are not polynomial algorithms and instead are called exponential algorithms as these functions are not polynomial and whose growth is exponential and hence cannot be solved for larger instances.

 

What is NP Class?

 

The class of decision problems that can be solved by a non-deterministic polynomial algorithm is called class NP problem.

 

What is a Non-deterministic algorithm? Non-deterministic algorithms produce an answer by a sequence “Guesses” while deterministic algorithms (like those that a computer executes) make decisions based on information.

 

 

Some of the examples of NP problems are given as follows:

  •   Traveling Salesman
  •    N-Queens
  •   Classroom Scheduling
  •    Packing
  •    Scheduling

 

These problems are hard problems as it is difficult to solve these problems for larger instances. Also, for most of these problems, no polynomial time algorithm is known and also it can be observed that most of these problems are combinatorial optimization problems. Most of the combinatorial problems are hard.

 

What is a decision Problem?

 

A decision problem is a problem whose output is a single Boolean value: YES or NO and NP is  the set of decision problems with the following property: If the answer is YES, then there is a proof of this fact that can be checked in polynomial time.

 

One can conclude that from this discussion that some problems are hard to solve with the following characteristics:

l   No polynomial time algorithm is known

l   If answer is YES, then it can be checked in polynomial time

l   Most combinatorial optimization problems are hard

 

Computational complexity is an exciting branch of algorithm analysis that discuss about these issues. The next module discusses about one important class of problems called NP-Complete problems.

 

 

Co-NP Proble ms

 

Co-NP is the opposite of NP. If the answer to a problem in co-NP is NO, then there is a proof of this fact in polynomial time [3].

 

NP-I Proble ms

 

NP-I is called NP- Intermediate problems that are said to be between P and NP. Examples of NP-I problems are factoring problem and graph isomorphism problem.

 

What is NP-Hard proble m?

 

NP-Hard are problems that are at least as hard as the hardest problems in NP. A problem A is NP-hard, if there is a polynomial algorithm exists, It implies polynomial algorithms for every problem in NP. In that case , P = NP whose proof is difficult. Clay Institute announced one million dollar prize in its web site for anyone who gives a proof. It is shown below with the other kinds of problems that are considered difficult (http://www.claymath.org/millennium/)

 

1.      Birch and Swinnerton-Dyer Conjecture

2.      Hodge Conjecture

3.      Navier-Stokes Equations

4.      P vs NP

5.      Poincaré Conjecture

6.      Riemann Hypothesis

7.    Yang-Mills Theory

 

 

NP-Complete Problems

 

NP-Complete (or NPC) problems are a set of problems that are well connected. A problem x that is in NP, if any one finds an polynomial time algorithm even for one problem, it implies that polynomial time algorithm for all NP-Complete problems. In other words: Problem x is in NP, then every problem in NP is reducible to problem x. Let us present the overview of NP-Complete Problems

 

1. Decision Problems

 

A decision problem is a problem whose output is a single Boolean value: YES or NO . NP is the  set of decision problems with the following property: If the answer is YES, then there is a proof of this fact that can be checked in polynomial time.

 

2. Language Frame work

 

Let us review some of the important jargons based on [3]  now.

 

Alphabet: An alphabet is a finite set of symbols. For example A = {0,1}

 

String: A finite sequence of symbols

 

Empty String: A string of zero length

 

Language: A set of strings is called a Language

 

Complementary Language: if the strings are not in L, then it is called complementary Language.

 

3. Proble m Encoding

 

Then the decision problem is encoded using Turing machine. Turing machine takes the encoding of the given problem and performs the following actions.

 

·         If input string is invalid, then Reject

·         If input string is valid, but output No, then reject

·         If String is valid and output is Yes, then Accept.

 

One can summarize this for language L as follows:

 

P = { L | L is accepted by a deterministic Turing Machine in polynomial time }

NP = { L | L is accepted by a non-deterministic Turing Machine in polynomial time }

 

NP-Complete problem can be formally defined as follows:

 

Q  is an NP-Complete problem iff

 

1) Q is in NP

 

2) every other NP problem polynomial time reducible to Q

 

So, to prove a problem A is NP-Complete, then reduce a known NP-C problem to A. Hence, reductions are basis of NP-Complete problems.

 

NP-Complete problems are solved by non-deterministic algorithms. A non-deterministic algorithm consists of two phases. The first phase is guessing of solutions and the second phase is the verification of the guesses using an algorithm or certificate. If the verification stage of a nondeterministic algorithm is of polynomial time-complexity, then this algorithm is called an NP (nondeterministic polynomial) algorithm [1,2,3].

 

The verification algorithm A has two components. One is input string x and another string called certificate. Certificate is another string y. It takes the input string x, and if A(x,y) = 1 implies the language is verified by the verification algorithm

 

One of the famous NP-Complete problems is Circuit Satisfiability problem. It can be formalized 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.

 

 

Cook-Levin theore m states that: Circuit- SAT is NP-Complete. [3]

 

 

The circuit Satisfiability is formulated mathematically as follows: Given a Boolean formula, determine whether this formula is satisfiable or not.

 

A  literal : xi or -xi

A clause : x1 v x2 v – x3 º Ci

 

A formula : conjunctive normal form

 

C1& C2 & … & Cm

 

 

Example 1: Is there any one assignment that makes the expression true :

 

x1 v x2 v x3

  • & – x1
  • & – x2

Solution:

 

It can be observed that the following assignment x1 ← F , x2 ← F , x3 ← T will make the above formula true

 

A related problem is called Formula Satisfiability problem. A Boolean formula is in CNF (Conjunctive Normal Form) if it is a conjunction (AND) of clauses. All clauses are disjunction (OR) of many literals. Every literal is a variable or its negation.

 

Another related problem is 3-SAT. In 3-SAT or 3SAT, there must be exactly 3 literals per clause. 3-SAT problem is : Given 3-CNF formula, Is there an assignment that makes the formula to evaluate to TRUE.

 

 

Examples of NP Hard Proble ms

 

 

Some of the known NP Hard problems are listed here. One of the major NP hard problem is vertex cover.

 

(i) Vertex Cover

 

Vertex cover is an important problem. It is formally stated as follows: Given a graph G=(V, E), S is the node cover if S Í V and for every edge (u, v) Î E, either u Î S or v Î S or both.

 

Solution

 

Like vertex cover, set cover finds the minimum number of sets that covers all the elements.

 

Some of the possible solutions are T = {s1, s3, s4} and T = {s1, s2}.

 

Set cover is a NP hard problem as the solution involves guessing a subset of vertices, count them, and show that universal set is well covered. This is simple if the number of elements is smaller. But if the number of elements becomes large, the number of possible set covers becomes larger. Therefore, the algorithm for set cover becomes exponential algorithm. Therefore, set cover problem is NP hard.

 

(iii) Sum of Subsets

 

Given a set of positive numbers A = { a1, a2, …, an } and constant C, find the set of elements whose sum equals C.

 

Example 3:     Consider the following set, A = {7, 5, 19, 1, 12, 8, 14} and C = 21, Find one

 

solution.

 

Solution

 

One solution is A¢ = {7, 14} for C = 21. Some other solutions are {12,8,1}, {7,5,8,1}.

 

If C = 11, then there would be no solution at all.

 

Sum of subsets is a NP hard problem. The solution of sum of subsets involves generating a a subset of numbers. If the sum of elements equals C, then the subset is a solution. Finding a solution is simple if the number of elements is smaller. But if the number of elements becomes large, the number of possible subsets becomes larger and algorithm becomes exponential as there are n! possible subsets for a set of ‘n’ elements. Therefore, the algorithm for sum of subsets becomes exponential algorithm. Therefore, sum of subsets is NP hard.

 

(iv) Hamiltonian Cycle

 

A Hamiltonian cycle is a closed path along n edges of G which visits every vertex once and returns to its starting vertex.

 

 

Hamiltonian cycle is NP hard problem as there are are n! different sequences of vertices that might be Hamiltonian paths in a given n-vertex graph [2,3].Therefore, if the number of vertices of graphs become larger, the algorithm becomes exponential. Therefore, Hamiltonian cycle problem is NP hard.

 

 

Solution

 

One possible Hamiltonian cycle is given as 4, 3, 1, 2, 4.

 

The concept of NP – Completeness and proofs of some of these problems are NP-Complete is discussed in next module.

 

 

Summary

 

One can conclude from this module 33 that

  • P and NP problems are important
  • NP-Complete problems are problem whose status is unconfirmed.
  • Non-Deterministic algorithms have important components – Guess and verification stage.
  • Satisfiability problem is NP-Complete

 

References:

 

  1. S.Sridhar , Design and Analysis of Algorithms , Oxford University Press, 2014.
  2. A.Levitin, Introduction to the Design and Analysis of Algorithms, Pearson Education, New Delhi, 2012.
  3. T.H.Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, MI T Press, Cambridge, MA 1992.
  4. K.S.Easwarakumar, Design and Analysis of Algorithms, MCA Text, Anna University.