P vs NP

Is P = NP?

Computer Scientists and Mathematicians have puzzled about the answer to this problem for many years. To most of them, it represents nothing more than an abstract concept akin to a puzzle. To the realists, however, the solution to this question is much more than just that. Many have prophesied that the answer is probably a resounding ‘No’. Things start getting interesting, however, when you begin to think about the repercussions of obtaining a positive answer to this infamous mathematical puzzle. In order to really understand what this means, let us begin by looking at which each of the terms (a.k.a complexity classes) in the equation means. Before we get to that, however, we are required to state a few more definitions.

Decision Problems

These are problems for which the answer is either a Yes or a No. Easy enough to understand, right? What are some examples of these? Well, these can really be anything. For instance, the question of ‘Did the chicken come before the egg?’ is absolutely valid in this context and if it could be modeled in a mathematical framework, this would be a very important question indeed. For now though, let us focus on more ‘math-y’ topics. An example of a question pertaining to such a topic would be ‘Is (0,0) a solution to the equation x_1 + x_2 = 0?’. The answer to this question, of course, is yes.

Polynomial Time Solutions

Let us first state here that ‘Time’ is a little more abstract in comparison to what you and I deal with in the real world. The ‘Time’ of an algorithm here is primarily a measure that looks at the number of ‘steps’ involved in performing the algorithm. For instance, consider the following setup: You are given a set A of two possible elements, i.e., A = {(0,0),(0,1)}. The decision problem is ‘Does there exist an element in A that solves the equation x_1 + x_2 = 0?’. The way to answer this question is to try out each element in A and see if any of them solves the given equation. Now, in the worst case, if we were forced to go through every single element in A, we would be forced to try out two options before ascertaining that (0,0) does indeed solve the equation and that the answer to our decision problem is ‘Yes’. Here’s the thing though, if you were to consider the process of plugging in an element and viewing the output as one single ‘step’, then the worst case number of ‘steps’ is 2, since we are required to check two elements in order to answer the question.

Let’s step the game up a little. What if A now had three elements instead of two? How many steps would we need now, in the worst case? You could try it yourself or you could take my word for it when I say you’d need 3 steps. You can clearly see that the increase in the number of steps is linear and as we all know, a linear function is merely a special case of a polynomial function. I could very easily conceive of an example where the number of steps increases in a quadratic manner with an increase in the number of elements. Essentially, any question that involves a polynomial increase in the number of steps in order to determine an answer is a question that is answerable in polynomial time. It must be noted that with modern computing breaking all barriers, polynomial time algorithms are fairly quick to run. Our problem arises when we’re dealing with exponential time algorithms. Essentially, what this means is that as the number of elements increases, the number of steps involved in arriving at an answer increases in an exponential manner. This is bad, since exponential problems can be extremely hard to answer.

P

The letter \textbf{P} here stands for \textit{Polynomial}. Essentially, this is a complexity class that represents all those decision problems that can be solved in Polynomial time. As we stated earlier, these are the ‘easy’ problems that do not pose much of a hassle to answer. An example of a problem belonging to this complexity class was provided earlier when we posed a decision problem to determine if an element in a set satisfied a given equation.

NP

The acronym \textbf{NP} is often confusingly thought to stand for Non-Polynomial. However, this is incorrect and \textbf{NP} actually stands for Nondeterministic Polynomial. Let us provide an explanation for what problems in this complexity class are all about. It is often thought that decision problems in this complexity class can only be answered in non-polynomial (or exponential) time. Before moving on, let us define what a ‘certificate’ is, in our context. A ‘certificate’ is essentially a ‘guess’ for an answer. Here’s an example.

Consider the equation x_0 + x_1 + ... + x_n = 7. Assume that the decision problem is ‘Does there exist a solution to this equation?’. It is clear that this cannot be answered in polynomial time. However, let us assume that we are given a certificate or a ‘guess’. An example of this is one possible set of values for the vector x, such as (0,1,0,...,1). Now, given this certificate that satisfies the equation, we can answer the question with ease, since we now know that there exists a solution, since our certificate was a solution.

This, in essence, is what problems in the \textbf{NP} class are all about. If one could answer the decision problem with ease, given a good guess, then the decision problem is said to be ‘in \textbf{NP}‘. You might think to yourself, ‘Well, can’t any decision problem be answered with ease once you’re given the right guess?’. The thing is, though, a decision problem can always be formulated such that despite the right guess, one can’t come up with an answer easily. Consider the question ‘Does there not exist a solution to this problem?’. Take a moment and think about this. Even if one were given a good guess for a solution that doesn’t solve the equation, we can’t be sure that there isn’t some other set of values for x that will solve the equation. As a result, we are forced to run through all possible values that the vector of textbf{x} can take. This, as you might have figured out, takes an exponential amount of time, since in the worst case, we are required to run through 2^n possibilities for the vector \textbf{x}. This decision problem is hence, not in \textbf{NP}.

Implications of P = NP

So now you know what \textbf{P} and \textbf{NP} are. We did mention earlier that the question of P = NP is significant not only to pure mathematicians or computer scientists. In fact, the answer to this question could have grave consequences with regards to the functioning of every single security system on the planet. Think of a simple 128 bit encryption key. To put it in simple terms, this is a password system of 128 bits where each bit can be a value of 0 or 1. The whole point of this being a good security system is due to the fact that in order to crack the password, in the worst case, one would have to run through 2^{128} (an exponential number of) options. So far, we are safe, since this is hard to do and as we construct tougher encryption keys, it becomes harder and harder to crack as the exponential function keeps getting bigger and bigger.The problem of cracking the password is, thus, a problem in the complexity class of \textbf{NP}.

Let us now assume, hypothetically, that all problems in the complexity class of NP also belong to the complexity class of P (this is essentially what P=NP means). This would mean that any password that was earlier tough and nearly impossible to crack now becomes vulnerable, since the cracking of the passwords could be done in polynomial time. As we already stated earlier, with modern computing the way it is, a polynomial time algorithm is pretty quick and easy to perform.

I’m sure you’ve understood the magnitude of what would happen if P = NP were true. Every security system would be obsolete. There would be no point in having banks. There would be no point in having classified government data. Literally every electronic system in place in the world would break down and we would effectively be thrown back into the stone age. Pretty scary, right? Of course, the fact does remain that no one has managed to prove that P = NP is true. Many feel that it is almost certainly not true and this helps the world maintain peace and order.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s