The P vs NP Problem

I wanted to write an entry about P vs. NP because I think it’s a perfect topic for a short expository essay. I also happen to think it’s incredibly interesting, but there’s more than a little bias that goes into a statement like that.

So first , we should talk about what P vs. NP actually is. It’s a major unsolved problem in mathematics, so much so that it is one of the Seven Millennium Problems in mathematics, each of which carry a prize of one million dollars to be awarded to the person that solves them first ( I almost wrote “mathematician” there, but who knows?).  Of these problems only one has been solved thus far, and it’s called the Poincaré conjecture.

P vs. NP is cool for two reasons. The first  is that I believe it’s the most interesting of the seven and  one of the most interesting problems in all of mathematics, but that’s of course just an opinion.  The second one has more nuance, as I believe P vs. NP is the only Millennium problem you can explain to someone who has a limited understanding of math.  That’s what I meant when I said I think it’s the perfect article topic.

The title of P vs. NP is interesting because it implies some sort of adversarial relation.  The basis of the problem is this : we have two sets P and NP.  We know that P is inside of NP, that is to say that everything in P is also in NP.   What we want to figure out is if the converse is true, which is to say that everything in NP is also in P.  We want to know whether P and NP are equal or not.

In order to kick this off, let’s introduce the concept of an algorithm. An algorithm is a finite set of steps that a problem solver (like a computer) can follow.  The “elements” of the “sets” of P and NP are languages – which here is abstracted to mean any collection of strings of 0s and 1s.  A language is in P if it has a decision algorithm  that satisfies a certain property.  A decision algorithm for a language is one that takes a string of 0s and 1s and outputs “1” if it’s in the language and “0” if it’s not.  This may seem pretty abstract, but it can be phrased in a simpler way.  If we have a language, can we construct an algorithm with some sort of property such that it will tell us if something is in the language or not?

Now the elephant in the room is : what is the mysterious property we need these algorithms in P to have? P stands for polynomial. and that’s the property we want. We want the algorithm to take at most f(n) steps for an input of size n, where f is some polynomial.  I think now a rather classic question arises : Isn’t this class huge and unwieldy? After all I just lumped in functions that are linear, like n+3, with functions that grow much faster, like n^1000.  Those are both polynomials, but one is significantly more pleasant than the other to work with.

The reasons (as I was told) to use P are as follows: P is closed under many operations we are interested in and all of P is dominated by anything exponential.  It’s useful to have something closed under operations like multiplication and addition since usually when we talk about algorithms we want to invoke things like subroutines. The second reason comes from the fact that any exponential function eventually will completely overpower and dominate any polynomial function – you can prove it yourself if you are so inclined by using L’Hopital’s rule.  This might lead you to venture that the exponential algorithms make up another class, and you would be right – we call it EXP.

So now that we have all that, it’s time for an example.  An example of a language in P is multiplication.  This means if we are given two inputs and their supposed answer, we can decide if the answer if  the multiplication of the two inputs with an algorithm that takes a polynomial number of steps.  There’s also a proof that “decision problems are everything” which means if have a P algorithm for deciding the language of multiplication problems we also have a P time algorithm to actually multiply two numbers.  It’s not as artificial as it may seem. There are also some pretty cool problems in P, like deciding whether a graph has a cycle, deciding whether a graph is 2 – colorable, and multiplying matrices. Recently it was shown that determining whether a number was prime or not was in P, which was a really cool step forward.

Now we can introduce NP, which in a cruel but ancient mathematical tradition has a name that’s incomprehensible without studying beforehand. It stands for Nondeterministic Polynomial time, and here the Nondeterministic refers to a type of Turing machine. We won’t be using that for our discussion, and I’ll opt to provide my own explanation instead.

In a way of thinking, NP is the set of problems that can “checked” in polynomial time. This means that if we are given the answer to a problem , we can check whether the answer is right in polynomial time. It should be clear why P is now contained in NP, if we generate an answer in polynomial time then we can just cross – reference against the given answer in polynomial time.

The classic example here is something like Sudoku. Anyone who has done a Sudoku knows it’s a lot easier to check whether your completed grid is correct than to fill the grid yourself.  There’s an easy way to check if your Sudoku is correct that is seemingly independent from how to solve it. The question here is, is it truly?  This brings us to P vs. NP – or rather – if a set of problems can be checked quickly , can they also be solved quickly?

You can kind of think of NP as “easy” search problems, in that we are looking for something of a relatively “short” size that can be verified easily. Most people , including myself, think that P is not equal to NP.  Note that proving things is itself a search type problem (we cannot say “proofs” are in NP since we do not know the size of the proof). We can check if a proof is correct in polynomial time, but we certainly don’t know any good ways to generate them with an algorithmic procedure. A result of P = NP would mean that all sorts of advancements in automation would be possible, our current cryptographic systems would need to be retooled, and a whole lot of other things. A result of  P = NP, in my opinion, would be equivalent to humans suddenly discovering that they had magic powers.

So what work has been done with regards to P and NP? The answer is a whole lot.  I think one of the most startling results is that P and NP can be separated through an oracle.  For this thought experiment lets imagine we have a black box that immediately decides a language of our choosing, and let’s factor this box in when we are constructing algorithms. This black box is called an oracle.

It turns it’s possible to construct an oracle so that P with the oracle is different than NP with the same oracle.  Note that this definitely doesn’t work like an equation, we can’t subtract oracle from both sides to get P not equal to NP.  We can also construct an oracle such that P with oracle is the same as P with NP with the oracle.  However, the proof of this is beyond the scope of my blog entry and I won’t be showing it.  If you would like to know, feel free to email me (srajasek93@gmail.com).

One way to prove that P = NP would be showing that any special NP problem is in P. We call these special problems NP – complete.  An NP complete problem must be both in NP and be NP hard. Of these two conditions I think the only one that needs explaining is the latter.

A problem is NP hard if any problem in NP can be transformed into an instance of it  with a polynomial time algorithm. That means if we had any problem in NP, we can set up a “short” (read: polynomial time) conversion that transforms it into an instance of our NP complete problem.  Strangely enough I think nearly every problem in NP (and not just in P) we know of is also NP complete. However it has been proven that if P is indeed not NP then NP intermediate problems exist, problems that are in NP and not NP complete.  Oddly enough, if I recall correctly, this proof is non-constructive. One of the candidates for an NP intermediate problem would be factoring integers, as we know when we factor we are always guaranteed an answer and factoring has been shown to be possible by quantum algorithms that probably cannot generalize to all NP problems.

Note that if even one NP complete problem is in P , all of NP is in P.  In order to decide any NP problem, apply a polynomial time transformation to the NP complete problem in P and apply the  polynomial time algorithm that solves the NP complete problem.  This leads to the popular phrases “solve one and you solve them all” or my personal favorite ” if you can solve a Sudoku quickly you can cure cancer”.

 

Senthil Rajasekaran

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s