P versus NP Problem

Jitesh Singh
Jan 1, 2019 · 5 min read

P versus NP is a major unsolved problem in computer science, specifically in computability theory and computational complexity theory. The solution also will have profound implications in the fundamental understanding of mathematics, cryptography, artificial intelligence, life sciences, philosophy, economics and many other fields.
It is one of the seven millenium problems selected by Clay Mathematics Institute.

Photo by Christian Fregnan on Unsplash

Introduction

We humans invented computers because we are not very good at performing complex calculations. Computers have amazing computational power as they were designed to be such, but have no thinking power. One major implication of which is they can not solve a real world problem entirely on their own. They do not possess the ability to transform a given problem into a series of computations.

So we humans need to describe them how to solve a given problem, basically the ‘which and how’ about the computations.
The description has to be ‘unambiguous’ as it has to be followed by something which can not derive any sense out of ambiguity.

This unambiguous description about how to solve a given problem is called an “Algorithm”.
A computational problem always has some input data, and the solution is called the output data. An algorithm takes as input the input data of the problem and produces an output, which is the solution.

In order for an algorithm to reach to the solution, it needs ‘resources’, which can be anything the algorithm needs other than the input data.
For example; time needed to reach to solution, space needed to store intermediate computation data etc. can be called resources.

The input data of the problem can keep changing, for example; ‘how to multiply two numbers’ is a problem, but the numbers themselves can be anything and can change from one instance of the problem to another.
Also the numbers can be of any given size, this measurement of input data is called “input-size”.

Generally, resources required by an algorithm increase with the increase in input-size.
This growth in resource requirement with respect to the growth in input-size is called “asymptotic growth” and is represented as a ‘function of input-size’.

If the asymptotic growth of an algorithm can be represented as a polynomial function, then it’s called a “polynomial-time” algorithm and the problem is called to be solvable in polynomial-time.

Sometimes it’s possible to break a problem in terms of another problem.
For example, the problem of multiplication can be broken into problem of addition.
So if one figures out how to perform addition, then multiplication can be performed by performing repetitive addition.
This conversion of one problem into another is called “reduction”.
If both the time required in conversion and number of repetitions is polynomial, then the reduction is called “polynomial-time reduction”.

Computational Complexity Classes

Asymptotic growth is also known as “complexity”.
According to their complexity, problems in computer science have been classified into various categories.
These classes are called “computational complexity classes”.
For understanding the P vs NP problem, we need to understand four complexity classes: P, NP, NP-Complete and NP-Hard.

Photo by Elijah O'Donnell on Unsplash

P is a set of problems which can be solved in polynomial-time.

NP is a set of problems which may or may not be solved on polynomial-time.
But if one has the solution, the correctness of the solution can be verified in polynomial-time.
Intuitively, all problems in P also belong to NP, as solutions of P can be verified in polynomial-time just by solving them.

NP-Hard is a set of problems to whom any problem in NP can be reduced to in polynomial-time.
There are no known polynomial-time algorithms to solve these problems. Also, some of these may not even be verifiable in polynomial-time, meaning these may or may not belong to NP.

NP-Complete is a set of problems which belong to both NP-Hard and NP.
Meaning, these are NP-Hard problems whose solution can be verified in polynomial-time.
NP-Complete is an intersection of sets NP and NP-Hard.

The classes in increasing order of complexity:
P < NP < NP-C < NP-H


The Problem

Photo by Olav Ahrens Røtne on Unsplash

Consequences

Although highly unlikely, but if it turns out that P = NP with a ‘constructive and efficient’ proof, then it will be a groundbreaking achievement in mathematical theorem prooving, protein structure prediction which in turn implies considerable advances in life sciences, biotechnology, bioinformatics, structural genomics, genome sequencing, medicine, drug design, may provide treatments for some of the incurable diseases; more efficient compiler design, better circuit design, most efficient transport routing, scheduling, logictics, lot more easier and accurate machine learning, natural language processing, computer vision, image recognition, weather forecasting, accurately predicting earthquakes and other natural phenomena and many more far-reaching consequences, this is just the surface.
As one of the major negative consequences, it will break all cryptosystems based on integer factorisation which implies it will break the entire modern internet security infrastructure.

As a philosophical consequence, it will change the picture of reality, where in solving a problem and verifying the solution would mean the same thing!
This will have a huge deal of implications on how we understand the world and reality.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store