Every decision problem in P is also in NP. If a problem is in P, we can verify YES answers in polynomial time. Similarly, any problem in P is also in Co–NP. One of the important open questions in theoretical computer science is whether or not P = NP. Nobody knows. Intuitively, it should be obvious that P ≠ NP, but nobody knows how to prove it. Another open question is whether NP and Co–NP are different. Even if we can verify every YES answer quickly, there’s no reason to think that we can also verify NO answers 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 a long time to even check them. That means, if someone gives us a solution for an NP-hard problem, it takes a long time for us to check whether it is right or not. A problem K is NP-hard indicates that if a polynomial-time algorithm (solution) exists for K then a polynomial-time algorithm for every problem is NP. Thus:
K is NP-hard implies that, if K can be solved in polynomial time, then P = NP.
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 a 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
From the above discussion, we can write the relationships between different components as shown below (remember, this is just an assumption). The set of problems that are NP-hard is a strict superset of the problems that are NP-complete. Some problems (like the 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 includes everything easier than its “toughest” problems – if a problem is not in NP, it is harder than all the problems in NP.
Does P = NP?
If P = NP, it means that every problem that can be checked quickly can be solved quickly (remember the difference between checking if an answer is right and actually solving a problem). This is a big question (and nobody knows the answer) because right now there are lots of NP-complete problems that can’t be solved quickly. If P = NP, that means there is a way to solve them fast. Remember that “quickly” means not trial-and-error. It could take a billion years, but as long as we didn’t use trial and error, it was quick. In the future, a computer will be able to change that billion years into a few minutes.
Reductions
Before discussing reductions, let us consider the following scenario. Assume that we want to solve problem X but feel it’s very complicated. In this case, what do we do? The first thing that comes to mind is, if we have a similar problem to that of X (let us say Y), then we try to map X to Y and use Y’s solution to solve X also.
This process is called reduction.
In order to map problem X to problem Y, we need some algorithm that may take linear time or more. Based on this discussion the cost of solving problem X can be given as:
Cost of solving X = Cost of solving Y + Reduction time
Now, let us consider the other scenario. For solving problem X, sometimes we may need to use Y’s algorithm (solution) multiple times. In that case, the Cost of solving X = Number of Times * Cost of solving X + Reduction time.
The main thing in NP-Complete is reducibility. That means, we reduce (or transform) given NP-complete problems to other known NP-Complete problems. Since the NP-Complete problems are hard to solve and in order to prove that a given NP-Complete problem is hard, we take one existing hard problem (which we can prove is hard) and try to map the given problem to that and finally we prove that the given problem is hard.
Note: It’s not compulsory to reduce the given problem to a known hard problem to prove its hardness. Sometimes, we reduce the known hard problem to a given problem.
Attempt free Data Structures MCQ Test
