11 P and NP problems

S. Sridhar

This module 32 focuses on introducing theory of computational complexity. The module also discusses about Class P and NP problems. The objectives of this module are

 

·         To understand the concept of Polynomial Algorithms

·         To Understand Non-Deterministic Polynomial

·         To understand NP-Hard 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.

 

Algorithmic complexity theory 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 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.

 

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.

 

Polynomial Time Algorithms

 

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. Why is it called polynomial time algorithms? The reason is that Jack Edmonds and Alan Cobham proposed this terminology. It can be recollected from module 3 and module 4 that the run time of an algorithm is represented as an polynomial. The polynomials have the following characteristics.

 

 

·         Polynomials are closed under composition

·         Polynomials are closed under addition

·         All sequential digital computers are related

 

 

So, no matter what machines are used, T(n) would remain a polynomial whose coefficients vary as per the machine. The constants ate immaterial as in asymptotic analysis, the polynomials are in any way approximated.  Hence polynomial or class P problems are a class of decision problems that are solvable in O(p(n)) time, where p(n) is a polynomial of problem’s input size n

 

 

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 ca n 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 about the algorithms like N100? Or algorithms whose degree is large, say 100 [1,2,3]. Still, these algorithms are classified as polynomial algorithms as these kinds of algorithms are never encountered in algorithms. In fact, most of the algorithms may never have degree more than 5 [2,3] and hence theoretically this classification of algorithms is still valid.

 

Solvability leads to another question. Are there any problems that can’t be solved? Yes. There are many problems that cannot be solved. Let us discuss about them now.

 

 

Unsolvable problems

 

One such problem was introduced by Alan Turing 1912-1954, who is widely regarded as “Father” of modern computing science. In 1936, he introduced a problem called “halting problem”. He is also credited with other accomplishments like Turing Machine, Church- Turing thesis, and Turing test.  What is a Turing problem? It can be formulated as  Can we write a program that will look at any computer program and its input and decide if the program will halt (not run infinitely)? [2,3,4]  Turing proved that writing such algorithm is not possible. His argument is like using a Program prog and using it as parameter to itself! The general formal of the program is given as follows:

 

if halts(prog, prog):

 

while True:

 

print “looping“

 

else:

 

print “done”

 

 

The kind of argument given by Turing [2,3,4] is that if the segment, If halts(prog,prog) returns True, that means the program will halt when given itself as input. However, in this case the program would go into an infinite loop (symbolically represented as Print “looping”). . Therefore the program doesn’t halt. If halts(prog,prog) returns False, that means that it wouldn’t halt, but in that case the program does halt.

 

Hard Problems

 

Solvable and Unsolvable problems represent two extreme ends. In between, there are many problems that are hard.

 

Hard problems [2,3] are problems whose solution is not guaranteed with limited computer resources such as time and space. In order to analyze these algorithms let us discuss some issues so that some framework can be developed.

 

Turing machine

 

Since algorithm analysis should be independent of machines, theoretical machines like Turing machines are useful. A Turing machine is a very simple theoretical “computer” with a couple basic elements such as infinitely long tape broken up into cells that can each store a single symbol from a finite set of symbols, a head that can read or write one symbol at a time from the tape and a state diagram that tells the head what to do, move left/right, print a symbol.

 

 

The advantage of Turing machine is that it can theoretically all problems if it is solvable. This is given as Turing – Church theorem given by Alanzo Church in his thesis. This thesis proves that  a Turing Machine could theoretically be created that can do anything any modern digital computer can do.  To use Turing machine, the problem should be encoded in a suitable form. So , these terminologies are important.

 

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.

 

The given problem should be posed as a decision problem. What is a decision problem? A decision problem is a problem whose output is a single Boolean value: YES or NO. Developing decision problems are useful as NP problems are a 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.

 

Once the given problem is encoded as a decision problem, the problem should be encoded. The encoded decision problem is given as input for Turing machine. The Turing machine does as follows:

 

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.

 

With this framework, the concept of hard problems can be discussed.

 

 

NP Problems

 

NP problems stand for Non-Polynomial deterministic algorithms. A NP-Hard problem can be defined as follows:

A problem Π is NP-hard if a polynomial-time algorithm for Π would imply a polynomial-time algorithm for every problem in NP.

 

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

l  Traveling Salesman

 

l   N-Queens

 

l   Classroom Scheduling

 

l   Packing

 

l   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.

 

 

Related to NP problems are co-NP problems. Co-NP problems are 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.

 

NP-I is called NP- Intermediate problems that are said to be between P and NP. Some of the examples of these problems are

 

–   Factoring problem

 

–   Graph isomorphism

 

 

All these point to a important issue whether P = NP? In fact, Clay Institute constituted one million dollar prize for solving this problem. This problem is ranked with other problems as shown below:

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

 

The heart of P Vs NP problem is that many problems do not have any polynomial algorithms. At the same time, there is no proof that these problems can’t be solved in polynomial time. Also, these problems are linked with each other. So, if one problem is solved, then all related problems can be solved. In that case, the problem complexity is reduced to P.

 

Computational complexity

 

Summary

 

One can conclude from this module that

  •    Solvability deals with the question of an existence of a program for solving a given problem. Tractability of a problem checks whether the problem is bounded by a polynomia  P and NP problems are importan   Halting problem is an important NP- Hard problem

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, MIT Press, Cambridge, MA 1992.

4.        K.S.Easwarakumar, Design and Analysis of Algorithms, MCA Text, Anna University.