P vs NP Problem

What are Complexity Classes:

Complexity classes are the main concept of complexity theory which is a central topic in theoretical computer science. A complexity class contains a set of problems that take a more or less the same range of space and time to solve for instance “all problems solvable with exponential space with respect to input size”. The problems are proven to be in some complexity class by executing the problem on abstract computational model. Some of the largest unsolved problems in the field of computer science have to do with proving whether or not two complexity classes are equivalent or not. The most classical example of this is the infamous N=NP problem.

Complexity class is based on how much time and space it requires to solve problems and verify the solutions. The Complexity classes consider Time Complexity and space complexity while grouping the problems into the complexity class.

The Time Complexity of an algorithm gives an idea of how much time the algorithm or the problem need to solve the given problem or the number of step it will require.

The Space Complexity gives a brief estimate of how much memory the algorithm need to operate.

P Class:

The class P contains decision that are solvable in polynomial time by a deterministic Turing machine. Sometimes this is phrased as: P is the class of languages that are decidable in polynomial time by a deterministic Turing machine.

Many problems can be solved using a brute force approach, but this often takes exponential time. If a problem has a polynomial time algorithm, it can be solved much more efficiently than by the brute force method. Many of the algorithms that are actually used in practice are polynomial time algorithms — exponential time algorithms are typically less useful and are avoided as much as possible.

A problem in P can be solved in time for some constant k and where n is the size of the input.

Sample Problem in P:

Bubble Sorting

NP Class:

The class NP contains decision problems that are solvable by a Turing machine in non deterministic polynomial time. this includes problems that are solvable in polynomial time up to problems that are solvable in exponential time. While they can take a long time to solve, some time thousands of years. But they can be verified by Turning Machine in polynomial time.

The example of this class is:

Travelling Sales man

NP- Complete class:

NP-Complete is a complexity class which represents the set of all problems in NP for which it is possible to reduce any other NP problem to in polynomial time.

What makes NP-complete problems important is that if a deterministic polynomial time algorithm can be found to solve one of them, every NP problem is solvable in polynomial time (one problem to rule them all).

The examples of this class are:

1. 0/1 Knapsack.
2. Hamiltonian Cycle.
3. Satisfiability.

NP-hard class:

A NP hard problem is at least as hard as the hardest problem in NP and it is the class of the problems such that every problem in the NP reduces to NP-hard.

It takes a long time to check them. This means if a solution for an NP-hard problem is given then it takes a long time to check whether it is right or not.

One of the example of problem in Np-hard is:

Halting problem.

What happens if all ‘NP hard’ problems find a solution in polynomial time complexity?

Every problem in our day to life would have been easy. The tasks like transport routing, job scheduling, production of goods, circuit and database design, optimization of these problems will lead to massive advancement in the problems that are easy to check would now be easy to solve. These solutions would make a huge deal in the economy. This also means that all the problems with complex solutions would be made easy, which also include ATM Pins, Passwords etc. Our important and private information will be available to the world.

What happens if P does in fact, equal to NP?

The consequences of N and NP being equal would surely affect the academics, but more importantly it would lead to a massive change in some practical situations, like:

· Cryptography — Starting from the PINs of our ATMs to the various passwords of the social media or bank accounts. We totally depend on the codes to govern our everyday lives since they are easy to check but hard for people to crack.

· Vehicle Routing — The profitability of any e commerce business exists in reduction of their transportation costs, if by any algorithm we are successful in finding the most optimized path, it would bring in a huge difference.

· Protein Folding— If we could unravel the sequence of amino acids(proteins) it will help in many areas such as drug design and perhaps even cure cancer.

If the ‘P problem’ would become equal to the ‘NP hard problem’ it would surely bring in some advancements in the medical and economical fields, but this would also threaten the cryptography world, since it is based on the fact that NP hard and P problem exist in different classes. These unsolvable problem which exists in the NP hard class drives our password and encryption and in turn drives our economy.

References:

1. https://en.wikipedia.org/wiki/P_versus_NP_problem
2. https://www.youtube.com/watch?v=e2cF8a5aAhE&list=PLDN4rrl48XKpZkf03iYFl-O29szjTrs_O&index=72
3. http://news.mit.edu/2009/explainer-pnp
4. https://ieeexplore.ieee.org/document/7819075
5. https://www.cse.iitk.ac.in/users/sb/papers/a-talk.pdf

Published By:

Mugdha Dhopade

Shivam Ghadge

Janhvi Godle

Mihika Gulhane