Introduction




Figure 1:  Relation between P, NP, NP Complete and NP Hard problems


In this blog we are going to discuss about the types of problems in computer science like P, NP, NP Hard, NP Complete and the solution to P vs NP.  Each term is explained in detail and in an easy to understand way. So let’s dive deep into the topic!

 


P Problems

P (polynomial) complexity class basically contains all the problems that can be solved by a deterministic Turing machine in polynomial time (for example: O (n), O (n2) and so on). An algorithm is said to be solvable in polynomial time if for some k>0, its running time on input size of n is O (nk). The algorithms with exponential running time are not polynomial.

Which problems fall under P complexity class?

1.            Recognizing Palindrome

The problem of recognizing palindromes is solvable in linear time, which is polynomial time.

To decide if x is a palindrome, just reverse x and check whether the reversal of x is equal to x. For example, aabcbaa is a palindrome. Let's define it

     PALINDROME = {x | x∈{a, b, c}* and x is a palindrome}

 

2.            String matching

Input: Consider two strings, p and t. Question is if p is contiguous substring of t.

Suppose p = expert and t = the rocketry expert is here, then the answer is yes.

The algorithm just checks each position in t to see if p occurs at that position. This continues until it finds a match or exhausts the positions that it can try.

Suppose that p is of length m and t has length q. There are q − m + 1 positions to try.

 


NP Problems

NP stands for Non deterministic polynomial time which basically is a complexity class using which we can classify decision problems.

NP contains set of decision problem which are solvable in polynomial time by non-deterministic Turing machine. NP is also considered as set of decision problems whose solutions or proofs can be verified in polynomial time by a deterministic Turing machine. Since there are large number of problems in this class, great amount of efforts have been take to find polynomial time solutions for the problems in NP. But still question remains…Whether these problems are even decidable or not in polynomial time?

NP contains all the problem in P and NP is contained in EXPTIME, since that same algorithm can be achieved in exponential time (Ex: O (2n), O (nn), where n is the input size).

Before we dive into NP-complete and NP-hard let’s understand the concept of reduction.

 


What is Reduction?

Consider we have two decision problems P and Q out of which Q is solvable by using algorithm A. That is we can get a decision yes or no by applying algorithm A for problem Q for any given input Y. Now that we know the solution for Q, we can try to reduce problem P such that algorithm A can be part of algorithm used to solve P. This transformation from P to Q can be called Reduction.

 


NP Complete Problems

The name "NP-complete" stand for "nondeterministic polynomial-time complete". NP-Completeness is applied to decision making problems because it seems comparatively easier to compare difficulty of decisions problems than that of optimization problems.

A decision problem P is said to be NP-complete if:

1. P belongs to NP and

2. Every problem in NP can be reduced to P in polynomial time.

Now the 2nd condition looks impossible but idea is to take a known NP-Complete problem and reduce it to P, if it’s done in polynomial time we can say that P is NP-complete by transitivity of reduction.

NP-complete problems are considered to be hardest in NP. If any NP-complete problem can be solved using polynomial time algorithm, all problems in NP can be solved similarly. No one has been able to prove that NP-complete problems can be solved in polynomial time.

 

Which problems are NP-complete?

SAT (Boolean satisfiability problem) is the first NP-complete problem which was proven by Cook. Few of the well-known NP-complete problems are listed below.

·       Knapsack problem

·       Hamiltonian path problem

·       Travelling salesman problem

·       Clique problem

·       Vertex cover problem

·       Independent set problem

At present, all known NP-complete algorithms take time that is super polynomial in input size, and no one knows if there even are any faster algorithms.

 


NP Hard Problems

A decision problem L is considered to be NP-hard if for every problem H in NP, there is polynomial time reduction from H to L. NP-hard problem does not need to be in NP class, they may not even be decidable. NP-hard problems are also informally defined as “at least as hard as the hardest problems in NP”. NP in “NP-hard” is considered as “non-polynomial” which stands for “non-deterministic polynomial acceptable problems”. Finding a polynomial time algorithm for any NP-hard problem would lead to polynomial time algorithm for all the NP problems. Since it is highly suspected that P ≠ NP, it is unlikely that such an algorithm exist.

 

Which are the NP-hard problems?

A decision problem “subset sum problem” is considered to be NP-hard in which we are given a set of integers, does any non-empty subset of them add up to zero? This problem is also considered NP-complete. Traveling salesman is another NP-hard problem.

There are some decision problems which are NP-hard but not NP-complete, example - halting problem. It is a problem which asks if for given input, the program will run forever. The NP-hard problems that are neither NP-complete nor undecidable.

 


P versus NP

There are seven Millennium Problems given by Clay Mathematics Institute. These problems are difficult to solve and there is no solution for these problems yet except for Poincaré Conjecture.

  1. Yang–Mills and Mass Gap
  2. Riemann Hypothesis
  3. P vs NP Problem
  4. Navier–Stokes Equation
  5. Hodge Conjecture
  6. Poincaré Conjecture
  7. Birch and Swinnerton-Dyer Conjecture 

Let’s discuss about our topic which is the P vs NP (Is P=NP?). This is one of the seven Millennium Problems given by Clay Mathematics Institute. As discussed in the above section, P class problems can be solved in polynomial time and NP class problems can be solved in exponential time but they can be verified in polynomial time. A simple example can be of Sudoku. Finding a solution for the game is a bit difficult and it increases exponentially with increase in the number of grids. But verifying whether a solution is correct or not is easy. Verification can be done in polynomial time.


So let’s start with the question “Is P=NP?” What exactly is P vs NP?



P is a class of easy problems and NP is a class of relatively difficult problems. When we ask this question "Is P=NP?" it basically means the following two things:

1. If solution to a particular algorithm can be verified in polynomial time, is it possible to find the solution to the same problem in polynomial time?

2. When we say that P=NP, we are actually saying that hard problems have easy solutions.

  

Points supporting P ≠ NP

Most of the scientists say that P ≠ NP. There are proper proofs and some good examples which support this point. The examples given below can be verified in polynomial time but it takes exponential time to solve them. For ex: Travelling Salesman problem takes O (2n * n2) time to solve (which is exponential) but for verification it needs polynomial time.

1.  An art gallery has many rooms. Each wall of the room is covered with multiple expensive paintings. The gallery owner wants to buy cameras to keep a watch on those expensive paintings, in case a thief tries to steal them. He wants to make sure, if 100 cameras would be sufficient for him to ensure that each painting can be observed through one camera.

2.  There is a travelling salesman who wants to travel to 100 different cities. But he has a limited supply of gasoline and hence he can only drive for a total of 10,000 km. He wants to know if he can visit all the cities with no shortage of gasoline.

 


Is P=NP?

As discussed in the NP-Complete section, there is one more class called NP-Complete (NPC). It is a subset of NP. If at least one problem in the NPC class is shown to be reducible to P, then we can say with conviction that all problems in the NP class can also be reduced to P and hence we could prove P=NP. But no one has proved this yet. And hence as we don’t have a proper proof for that, we can’t say with confidence that P = NP.

 

What if P becomes equal to NP?


Source: csoonline.com

If P would have been equal to NP, then the field of cryptography would be in danger. In cryptography, the essential and the most important element is the cryptographic code, which is very secure. The cryptographic algorithms handle this code and also other confidential data. The security of this code depends on the computational complexity of the algorithm in NP. If P becomes equal to NP, which means the solutions to all these complex cryptographic algorithms were found, then all your passwords would be leaked and all your confidential data would be open to the world. There would be security breaches everywhere.

 


Conclusion

Hence, from the above points, we can conclude that P vs NP, is a complex problem in the field of theoretical computer science which needs critical thinking and a huge research to solve it.  Researchers and computer scientists are continuously working on it to find a solution. It’s a very interesting problem to solve. Till now most of the evidences are in favor of P ≠ NP. But if someone is able to prove that P=NP, it will open new doors in the field of computer science.

 


 

 

Comments

Post a Comment