Complexity Classes
In Computer Science, in order to understand the problems for which solutions exists or not, the problems are divided into different classes and they are termed as complexity classes. In complexity theory, a complexity class is a set of problems with related complexity. It is a branch of theory of computation that studies the resources required during computation to solve a given problem. The most common resources are time (how much time the algorithm takes to solve a problem) and space (how much memory it takes)
Types of Complexity Classes
P Class
The complexity class P is the set of decision problem that can be solved by a deterministic machine in polynomial time (P stands for polynomial time). P problems are a set of problems whose solutions are easy to find.
NP Class
The complexity class NP (NP stands for non-deterministic polynomial time) is the set of decision problems that can be solved by a non-deterministic machine in polynomial time. NP class problems refer to a set of problems whose solutions are hard to find, but easy to verify. That means, if someone give you a solution to the problem, you can tell them whether it is right or not in polynomial time. For the NP class problems, if the answer is yes, then there is a proof of this fact, which can be verified in polynomial time.
Example
Let’s consider this example to understand the P and NP problems better. Suppose that you are organizing housing accommodations for a group of five hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker’s list also appears on the list from the Dean’s office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical.
Indeed, the total number of ways of choosing one hundred students from the five hundred applicants is greater than the number of atoms in the known universe! Thus, no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer.
Co-NP Class
Co-NP (Complement of NP) is the opposite of NP. If the answer to a problem in Co-NP is no, then there is a proof of this fact that can be checked in polynomial time.
Relationship between P, NP, and Co-NP
Every decision problem in P is also in NP. If a problem is in P, we can verify YES answer in polynomial time. Similarly, any problem in P is also in Co-NP.
One of the important question in theoretical computer science is whether or not P = NP. Until now, nobody knows. Intuitively, it should be obvious that P ≠ NP, but nobody knows how to prove it.
Another question is whether NP and Co-NP are different. Even if we can verify every YES answer quickly, there is no reason to think that we can also verify NO answer quickly. It is generally believed that NP ≠ Co-NP, but again nobody knows how to prove it.
NP-hard Class
It is a class of problems such that every problem in NP reduces to it. All NP-hard problems are not in NP, so it takes long time to even check them. That means, if someone gives you a solution for NP-hard problem, it takes a long time for you to check whether it is right or not.
NP-complete Class
Finally, a problem is NP-complete if it is part of both NP-hard and NP. NP-complete problems are the hardest problems in NP. If anyone finds a polynomial-time algorithm for one NP-complete problem, then we can find polynomial-time algorithm for every NP-complete problem. This means that we can check an answer fast and every problem in NP reduces to it.
Relationship between P, NP, Co-NP, NP-hard, and NP-complete
The relationship between different components is as shown below (remember, this is just an assumption).
The set of problems that are NP-hard is strict superset of the problems that are NP-complete. Some problems (like halting problem) are NP-hard, but not in NP. NP-hard problems might be impossible to solve in general. We can tell the difference in difficulty between NP-hard and NP-complete problems because the class NP include everything easier than its “toughest” problems — if a problem is not in NP, it is harder than all the problems in NP.
Conclusion:
The purposes of complexity theory are to ascertain the amount of computational resources required to solve important computational problems, and to classify problems according to their difficulty. The main challenge of the theory is to prove lower bounds, i.e., that certain problems cannot be solved without expending large amounts of resources. Although it is easy to prove that inherently difficult problems exist, it has turned out to be much more difficult to prove that any interesting problems are hard to solve. There has been much more success in providing strong evidence of intractability, based on plausible, widely-held conjectures.
