Complexity Zoo

This article has been published at Function Space.

(This is just my back up copy of the thing, do check this out on FS for better experience.)

In this article, we dive into computational complexity theory. You might want to check out our previous article to get informally introduced to some of the concepts that we elaborate here, although it is not a strict requirement.

Let’s look at a few similar looking problems :

  1. Given a graph, can you find if it has a cycle?
  2. Given a graph, can you find if it has a cycle which covers each vertex exactly once?
  3. Given a weighted graph, can you find the shortest cycle which covers each vertex exactly once?

The above problems do look similar. They all seem to be about finding a kind of cycle in a given graph. In fact, the second problem is exactly what we discussed in our previous article. Intuitively, the first problem looks somewhat easier than the second problem as it is about finding any cycle in the graph as opposed to finding a cycle containing all of the vertices. And the third problem looks difficult than the second, since here we want to find the shortest cycle and not just any cycle covering each vertex exactly once.

Our intuition can be verified by classifying the above problems into complexity classes. Our definition of class NP suggests that if a solution to the problem is given to us, it can be verified in polynomial time. In the case of Problem 1, given a graph and a sequence of vertices forming a cycle (solution), we can check in polynomial time if it is a valid cycle by simply traversing the nodes in the sequence as given in the solution. If this is a valid cycle, we will be able to trace it out completely in the graph. This will be a linear time algorithm and hence Problem 1 belongs to class NP. Further, we know that a problem is in class P if it can be solved as well as verified in polynomial time. So, if we can find the solution to problem 1 in polynomial time, it will further belong to class P (Remember that P is a subset of class NP). A simple graph traversal algorithm like depth first search (DFS) can be used to detect a cycle. And, of course, DFS is a polynomial time algorithm. Hence, we have established that Problem 1 is indeed an “easy” problem as it belongs to class P.

In the case of problem 2, given a graph and a solution (a cycle that covers each vertex exactly once), we can easily verify in polynomial time if the solution is indeed correct or not. Hence, it belongs to class NP. But there is no known algorithm which solves the problem in polynomial time. So, for now, we don’t know whether it belongs to class P as well. ( The open problem, remember?! ) This problem is famously known as Hamiltonian Cycle Problem.

Moving on to problem 3, given a weighted graph and a solution (claimed to be shortest cycle that covers each vertex exactly once), can we verify that this is a correct solution? It can be verified that it is a valid cycle covering all the vertices or not in polynomial time, but to verify if it is the shortest such cycle, we will first need to find out all such cycles and compare. From our knowledge of problem 2, we know that finding any cycle that covers each vertex exactly once is in class NP. Hence, we can not even verify the solution to problem 3 in polynomial time. Hence, for now, this problem is placed in a class beyond NP. In fact, this is a very famous problem called Travelling Salesman Problem.

To visualize the scope of the above mentioned complexity classes, a simplified view is shown in the figure below :

alt text

There is another important notion of NP-Completeness that we shall discuss next. NP Complete (NP-C) problems are a subset of NP problems, with a very nice property that all the problems in class NP are convertible to any problem in class NP Complete, in polynomial time. This has a very deep and important consequence. If we can find a polynomial time solution to any problem in class NP-C, then all of the problems in class NP can also be solved in polynomial time (first, conversion to NP-C problem in polynomial time, second, solving the NP-C problem in polynomial time). Consequently, all of the problems in class NP would be solved and verified in polynomial time, thereby making P=NP! But no researcherhave succeeded to come up with polynomial time solution for any NP-C problem yet.

Finally, those problems which are in class NP, but not in class NP-C or class P, are classified as NP-Intermediate class problems. Based on this observation, we modify the above figure as follows :

alt text

In this article we introduced you to a few complexity classes, namely – P, NP, NP-Complete and NP-Intermediate. We also introduced the concept of problems which are even more “difficult” than NP, terming them Beyond NP. In future article(s) we will venture inside Complexity Jungle to witness some more classes and study the overlap between them. Also, we will discuss how to prove a problem belongs to class NP-Complete. This is an amazing thing if you think about it! Without even knowing what all problems exist in class NP, and how many NP problems are there, there’s a notion of NP-Completeness saying all NP problems(even the ones yet undiscovered!) can be reduced into them in polynomial time. Moreover, we are able to prove, mathematically that a given problem is NP Complete. How exactly that happens? Stay tuned to demystify all these ‘Complex’ things!

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