Introduction

“P” stands for polynomial time and refers to the class of problems that can be solved (by algorithm) in polynomial time. “NP” stands for non-deterministic polynomial time and refers to the class of problems that can be verified in polynomial time. Thus, P = NP means equivalence of two classes of problems that can be solved and verified in polynomial time. Before we begin to understand the technicalities and functionalities of the Polynomial-time vs. Non-deterministic polynomial time problem, let’s dig in to look at the origin of this profound and the most prominent problem of theoretical mathematics and computer science.

History

Gottfried Leibnitz, a German mathematician around the 17^th century, proposed a machine that could take any mathematical statement as input and determine if it is true or false based on axioms of mathematics. But then a question arises: is every statement determinable? To be a little more precise, the question was whether we could know the answer to every mathematical problem. This became what we call a “decision problem (on which set Polynomial-time and Non-deterministic polynomial time are formed)”, popularly known as Entsheidungsproblem.

After almost two centuries later, another German mathematician, David Hilbert, gave an optimistic answer to this decision problem, stating that we can know and we will know the answer to any mathematical question, emphasising a doctrine that our mathematical knowledge is complete. However, his point of view was short-lived. In the same year, an Austrian Mathematician Kurt Gödel signified that our knowledge is limited in mathematics. This was done by proving his famous “Incompleteness theorem”. As an illustration, let’s work on a simple problem. 

It is known to us beforehand that a mathematical statement can either be true or false. Now consider this statement,

S: This problem is not provable.

If we could prove S to be true in the mathematical setting, it implies that it cannot be proved. However, we proved that the statement is true, a contradiction to the statement itself. Now, if we take otherwise, say S cannot be proved. Then it means that S is true in itself. We confer two things from these hypotheses; either mathematics is inconsistent [statement can be true and false at the same time] or incomplete [There exits at least one statement in mathematics that is true but cannot be shown to be true]. Assuming it to be consistent in accordance with our prior know-how, then we get that the mathematics is incomplete and there are true statements that cannot be shown to be true.

The actual proof is quite complicated and beyond the scope of this article. Just like Gödel introduced the limits of knowledge in mathematics, Alan Turing came up with limits of computation. Inspired by Gödel’s incomplete theorem, Turing proved that computer science is incomplete, just like mathematics. Turing was dealing with a halting problem: can there be a program that can determine whether the other program will halt or not?

It was proved by contradiction similar to the proof of incompleteness theorem that program halts cannot exist. Thus, by proving that problems are not solvable, Gödel and Turing demonstrated that there are theoretical limits to our knowledge of what we can possibly know. Just like that, there are problems solvable in theory but not in practice. It is due to the huge amount of time taken to compute the solution. This is how we arrive at categories of P and NP problems. The Polynomial time vs. Non-deterministic polynomial time problem was then introduced by Steven Cook, a mathematical theorist in the University of Toronto in 1971 in his paper titled “The complexity of theorem-proving procedures”, as we know it today. 

The Technicalities of P vs NP

Before we begin to define technicalities such as Polynomial-time (P) and non-deterministic polynomial-time (NP), we need to understand the Computational Complexity of an algorithm. Computational complexity is a subfield of theoretical mathematics and computer science that computes the amount of time and space required by an algorithm for a given input size ’n’. Running an algorithm takes some time in computing, and it mainly depends on how complex our algorithm is.

In other words, more operations needed to perform an algorithm imply more complexity and a larger size of input adds to the complexity. There are two classifications of an algorithm based on the number of operations it needs to perform. One of them defines polynomial time which is proportional to n^c where n is the size of input and c is some constant {name comes because of n^c, which is a polynomial}. Another class of algorithms takes up constant time rather than input size, for example, 2ⁿ time.  These algorithms run as the exponential of input and are very slow.

• Polynomial Time Problems: Algorithms whose complexity is no more than a polynomial function of the input are classified in the category of ‘P’ problems. In easy language, these are sets of problems that can be solved in polynomial time.
  
• Non-deterministic Polynomial Time Problems: These are sets of problems that can’t be solved but can be verified in polynomial time. In easy terms, NP problems are those which cannot be solved in a realistic frame of time, but if we get to know about the solution, we can verify it in a polynomial time by a deterministic TM (Turing machine).
  
• Turing Machine: Invented in 1936 by Alan Turing, it is an abstract computational device defined by a mathematical model which is used as an aid in investigating the extents and limitations of what can be computed. It is said that if anything is computable, it can be computed by a Turing machine. NP problems are verified by deterministic TM in polynomial time or can be solved by a non-deterministic TM in polynomial time.

Polynomial time=? Non-deterministic polynomial time entails: Is there a possibility that the problems which can be verified in polynomial time can also be found within a polynomial time or not? There is a subset of problems to which finding solution takes exponential time, and they are called NP-Complete problems (defined in coming sections). The alluring factor about it is that if one of those problems gets a polynomial-time solution, the entire class can be solved in polynomial time.

The reason behind the fame of the P = NP problem

Computer science tells us that a non-deterministic Turing machine cannot be converted into a deterministic Turing machine. If proved affirmatively, the P vs NP problem would mean that if a problem can be solved in polynomial time by a non-deterministic Turing machine, then one can also build a deterministic Turing machine that would solve the same problem in polynomial time. This can create a massive breakthrough in almost every domain. It would mean that many problems which seemed hard will be now easily solvable. The reason that the problem is so famous is that no one has been able to prove otherwise either.

There have been a lot of research attempts to solve this fascinating problem but nothing is yet achieved apart from insights to what shall either of them imply, and that bothers a lot of mathematicians as well as computer scientists. In fact, this problem is one of the seven problems for which Clay Mathematical Institute will give a prize of $1 million for either proving or disproving it. What’s more interesting is that nobody even has an idea of what the solution might be. As a matter of fact, in a 2002 poll, around 61 mathematicians and computer scientists gave an assumption that Polynomial time probably isn’t equal to Non-deterministic polynomial time. And around 9 of them assumed otherwise and said that they took this stance just to be contrarians. The predominant reason behind the fame of this problem actually comes with implications that will follow if we can prove that P = NP.  If proven, P =NP would drastically change the world we live in. In a world where you can solve anything as easily as you can verify, it will surely bring a revolution. To put it philosophically, if P = NP, it would mean that magic exists. In the mathematical community, the P vs NP problem is recognised as a mathematics question that is fundamentally important and beautiful (by Michael Sipser- American computer scientists), and it has connected mathematics and computer science together.

P ≠ NP Implications

Every mathematician and computer scientist desperately wants to solve P vs NP; however, this is more than just an abstract puzzle. If this problem is solved, it will clarify once and for all that what categories or class of problems are solvable by computer and what are not. If P = NP, then every class of problems in NP will have a hidden shortcut that will enable computers to find perfect solutions to them easily and quickly. Now, if P ≠ NP, then no such shortcut exists and thus computational abilities of computers will stay limited permanently. Many believe that P ≠ NP, but the proof for the same continues to evade them. Another aspect to look at comes is the concept of NP-complete problems. NP-complete problems are the hardest problems in the set of NP. To get a better idea, let us try to define the NPC problem.

• Definition:  A problem X  is NP-complete if it satisfies the two conditions given below:

1. X should lie in NP
2. For all Y belonging in the NP set, they should be polynomial-time reducible to X.

Now, NPC problems can only be solved if P = NP, and it would also imply that all NP problems are solvable as per NP-completeness property. NPC cannot be solved as of now, and presently, there hasn’t been established any efficient algorithm which can solve NP-complete problems. Proving that P ≠ NP will ensure that such a thing isn’t even possible to be found. This may not lead to anything new in the world as such but its proof might give some new ideas and insights which will be very interesting for both mathematicians as well as computer scientists. Although many researchers believe that P isn’t going to be equal to NP (due to its huge implications, which shall be discussed in the following section) they are now getting skeptical towards this hypothesis. Even after several attempts by scientists to prove it, there haven’t been any fruitful results. This creates a way for the other side to be true, or perhaps there is no way to solve this problem at all. One might need to discover whole new mathematics in order to get its solution. All in all, it might be realized that this P vs NP problem is de facto an example of Gödel’s incompleteness property (as of now).

P = NP Implications

Here we shall look at some of the practical implications if P is in fact equal to NP. We shall consider a few of the areas where it can bring plenty of changes; mathematics, computer science, and biology.

Cryptography

Modern cryptography is derived from three disciplines, i.e. mathematics, computer science and information security. It is a process of encryption and decryption using algorithms which has huge applications in all forms of network security. Cryptographic algorithms are designed in such a manner that breaking their security will take thousands of years. However, once we know the keys to the ciphertext, verifying procedure can be taken out in a reasonable time. With the powerful computational abilities of computers, it is done quicker than ever.

From this, we confer that cryptography belongs to the NP class. To understand it in a mundane way, take the example of ATM PINs. They are hard to crack for anyone due to the strong algorithms used to encrypt them, such as triple-DES. However, if we know the code, verifying it is easy. Similarly, e-commerce transactions via credit cards use RSA encryption and hence security is ensured. RSA is public-key cryptography that is very secure against brute force hacking attempts that lie in the NP difficulty class.

If P = NP, public-key cryptography becomes obsolete, and hence, everything which depends on it, including HTTPS, stands vulnerable. However, it shall all depend on the nature of the proof of P = NP. What I mean by saying that is there are two possible ways in which proof of this problem can be carried out, either in a constructive way or in a non-constructive mechanism. Constructive methodology means that its proof will provide us with all the requisition to formulate and find out the algorithms to which we can reduce an NP problem and then solve it in polynomial time. Whereas non-constructive proof shall only prove the statement that P = NP, it will ensure that there does exist an algorithm that can break cryptosystems but no knowledge on that algorithm shall be provided or even the way to figure it out. If the former happens, then there is a serious threat to the forms of cryptosystems in action. It still won’t end cryptography as a concept because even if we know the algorithm which gives the solution in polynomial time, it can still be inefficient in practicality.

For example, an algorithm that takes running time O (n^2^100) is in polynomial time, but it can take very long to reach its solution. Now, if the proof is of the latter type, then there is not much to worry about. Obviously, it will render the current definition of security, by all means, obsolete. However, it won’t pose much risk to existing strong algorithms of cryptography since non-constructive proof will only tell us about the possibility that there is an algorithm that can break cryptography in polynomial time, but no idea about which algorithm or how to create such an algorithm. In fact, finding out such an algorithm can take several years.

Protein Folding

This is another major practical implication of P = NP. We know proteins play a crucial role in our lives, and they are of various types. Every protein has its unique structure as well as function to perform. Proteins contain a certain sequence of amino acids; the unique structure of proteins is formed by their folding from the sequence of these amino acids. These folds in every protein are of different types as well as they have different energy levels. Prediction and understanding of how exactly a given sequence of amino acids folds up to form its 3D shape are considered an NP-hard problem. Today, with the help of artificial intelligence and machine learning techniques, the folding of proteins is tried out, and their folding rates are also being predicted. All of this is done because, in order for proteins to function correctly, it is very important for them to fold properly.

Unfolded and misfolded proteins are responsible for many incurable diseases, e.g. Alzheimer’s disease, cystic fibrosis etc. If we are able to prove P = NP, then we can understand the process of protein folding in polynomial time, and it can also help in drug design. Computation of protein folding might even help us in determining which kind of amino acid sequence is more prone to misfolds, and this way, we can develop drugs to target that mishap if possible in any way. This will help in curing a number of diseases that are incurable right now, perhaps even cancer. 

Similarly, there are many other areas that can witness a lot of changes, good or bad, both of great significance if P = NP is proven. Optimization problems that are approximated can have exact solutions which will again have a number of applications in all the optimization-based scenarios such as vehicle routing will be done optimally to move things around quicker and cheaper. Mathematical proofs can be generated as easily as they can be verified, and hence we can get short, precise, logical proofs to every theorem, which is generally quite long. Artificial intelligence, machine learning, weather prediction etc. will also witness giant leaps.

Philosophical Aspects to P = NP

Traditionally philosophical thoughts have come before a mathematical expression. Similarly, the P vs NP problem has also captivated a philosophical perspective into its account. The question here is what interest this apparently technical problem shall have for the philosophers. With every understanding we have so far regarding the P vs NP problem, we can certainly translate it into ontological premises. It fundamentally has two mathematical operation categories to ponder over; solving problems and verifying solutions. If it is established that the two categories have equivalency between them, the philosophical implications are also going to be profound. 

Stepping out of the technical terminologies and explanations, we can look at the P vs NP problem as philosophy. To begin with, it is quite clear that mathematics which involves computational complexity and philosophy, are two different genres, but when it comes to queries that lie in the domain of meta-mathematics, one gets confused where to put it exactly; under mathematics or philosophy? Meta-mathematics in easy language means the math about mathematics itself and its structure, formal properties etc. As an example, we have Gödel’s Incompleteness theorem to consider. Epistemology speaks of nature and limits of knowledge in general, whereas Gödel’s Incompleteness theorem is analogous to it, specifically about the limits of knowledge to know all mathematics.

As per Gödel, there are properly posed questions involving only the arithmetic of integers that cannot be solved. So there are certain truths (set of axioms related to the arithmetic of natural numbers) that are simply non-provable. Similar to the P vs NP case, where (if P ≠ NP) there are certain problems that can be verified but are not solvable. Philosophers mostly believe P and NP cannot be equivalent because they believe that humans are better at verifications than solving a problem, and the same goes for computer programs. If P = NP, then everything around us changes, including the things we believe in. The P vs NP problem in realms of philosophy asks a huge question, i.e. how do we figure things out? Do we know the things prior to having them figured out or do we only find them out after working on them? If P = NP, it would mean that everything we once thought or considered hard wasn’t actually really so and under such a paradigm, phenomena such as randomness, independence, unpredictability etc. that exist in the physical world won’t be justifiable. MIT scientist Scott Aronson in his blog “Why Philosophers Should Care About Computational Complexity”, says, 

“If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in ‘creative leaps,’ no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett.”

This, in my opinion, is no less than magic. This entire argument shows the significance of the P vs. NP problem in academia and the real world. Whoever comes with the solution to this exquisite unsolved problem will doubtlessly be a celebrity, and the proven result will bring with itself whole new mathematics or mathematical insights that might astonish the entire world, perhaps even the philosophy of mathematics.

References

1.  https://news.mit.edu/2009/explainer-pnp

2.  https://stackoverflow.com/questions/111307/whats-p-np-and-why-is-it-such-a-famous-question

3.  https://brilliant.org/wiki/p-versus-np/

4.  https://towardsdatascience.com/the-aged-p-versus-np-problem-91c2bd5dce23

5.  https://www.technologyreview.com/2010/08/19/262224/what-does-p-vs-np-mean-for-the-rest-of-us/

6.  https://en.wikipedia.org/wiki/P_versus_NP_problem

7.  https://cs.stackexchange.com/questions/13625/what-exactly-is-polynomial-time

8. https://www.techopedia.com/definition/21028/non-deterministic-polynomial-time-np

9.https://cs.stackexchange.com/questions/1243/what-is-meant-by-solvable-by-non-deterministic-algorithm-in-polynomial-time

10.https://www.newyorker.com/tech/annals-of-technology/a-most-profound-math-problem

11.https://www.ijser.org/researchpaper/History-of-P-versus-NP-Problem.pdf

12.http://uru.ac.in/uruonlinelibrary/Cyber_Security/Cryptography_and_Network_Security.pdf

13.https://stackoverflow.com/questions/111307/whats-p-np-and-why-is-it-such-a-famous-question#:~:text=The%20statement%20P%3DNP%20means,it%20cannot%20be%20done%2C%20either.

14. https://www.quora.com/What-is-the-P-vs-NP-problem-and-why-is-it-so-important

15. https://bigthink.com/technology-innovation/what-is-p-vs-np

16.https://math.stackexchange.com/questions/1593085/is-there-any-significant-consequence-if-p-does-not-equal-np-complete

17.https://www.quora.com/Why-do-the-majority-of-computer-scientists-believe-that-P-is-not-equal-to-NP-P-NP

18.https://stackoverflow.com/questions/58304787/p-vs-np-how-to-prove-that-they-are-not-equal

19.https://www.smashingmagazine.com/2015/11/p-vs-np-assumption-that-runs-internet/

20.https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_np_hard_complete_classes.htm

21.https://www.reddit.com/r/compsci/comments/3dcain/what_would_happen_if_p_np_was_solvedproved/

22.https://softwareengineering.stackexchange.com/questions/148836/what-would-be-the-impact-of-p-np/148853

23.https://www.quora.com/What-would-it-mean-if-P-NP-How-could-you-attempt-to-prove-it-How-would-it-change-the-world

24.https://www.quora.com/What-would-be-the-philosophical-implications-of-P-NP

25.https://thenewantique.blog/2018/07/23/p-%E2%89%A0-np-a-philosophical-perspective/

26.https://www.reddit.com/r/askphilosophy/comments/3xft9b/broader_philosophical_implications_of_the_p_v_np/

27.https://www.scottaaronson.com/papers/philos.pdf

28.https://math.stackexchange.com/questions/1013805/philosophical-implications-of-p-vs-np-proof

29.https://philosophy.stackexchange.com/questions/14509/what-would-be-the-philosophical-implications-of-a-solution-to-the-p-versus-np-pr