NP-Completeness and NP-Hardness

NP-Completeness

The next question we need to address is “how can I tell if my problem can be solved efficiently?” We’ve had a go at writing algorithms for simple problems and found some we can’t solve efficiently - but is there a way to tell if there’s no chance of finding an efficient solution?

One way to determine if a problem can be solved efficiently is to try to find an algorithm that solves the problem in polynomial time. If such an algorithm exists, then the problem is considered to be in the class P, which represents problems that can be solved efficiently. If it is not possible to find an algorithm that solves the problem in polynomial time, then the problem might still be solvable, but it may take a longer amount of time and computational resources to find a solution.

Another way to determine the efficiency of a problem is to consider whether the problem is in NP, which represents problems whose solutions can be verified in polynomial time. If a problem is in NP, it means that it is possible to verify a solution to the problem quickly, even if finding a solution may take longer. However, if a problem is not in NP, it means that it is not possible to verify a solution to the problem efficiently, even if a solution can be found quickly.

Finally, some problems may be in co-NP, which represents problems whose non-solutions can be verified in polynomial time. If a problem is in co-NP, it means that it is possible to quickly verify that a given solution is not valid, even if finding a valid solution may take longer.

Overall, it is often difficult to determine the efficiency of a problem, as it may not be clear whether an efficient solution exists or not. It is important to continue researching and testing different approaches to solve a problem, in order to determine the most efficient way to solve it.

The answer is, sort of!

If we can show that a problem is NP-Complete (or harder) it means that there is no known efficient solution to it. We can’t prove that there never will be but we can say that it is beyond the realms of efficient computation at present.

NP-Complete problems are a special class of NP problems that are at least as hard as any other problem in NP. In other words, if we can find an efficient solution to an NP-Complete problem, then we can also use that solution to solve all other problems in NP efficiently. This makes NP-Complete problems the "hardest" problems in NP.

To show that a problem is NP-Complete, we need to prove that it is both in NP and that it is at least as hard as any other problem in NP. This is usually done by demonstrating a polynomial-time reduction from the problem to an NP-Complete problem.

If a problem is in P, then it can be solved efficiently and we don't need to worry about whether it is NP-Complete or not. If a problem is in NP but not known to be in P, then it might be possible to find an efficient solution, but we don't know for sure. If a problem is NP-Complete, then it is definitely not known to be solvable efficiently, and it is unlikely that an efficient solution will be found in the near future.

If a problem is NP-Complete, it means that finding an efficient solution to that problem is equivalent to finding an efficient solution to all of the problems in NP. Additionally, the problem must be a member of NP itself. The NP-Complete problems are the hardest of all problems in NP. Subset sum and Travelling Salesperson are NP-Complete, amongst many others.

To show that a problem is NP-Complete, we can use a process called "reduction". Reduction is the process of taking an instance of an NP-Complete problem and transforming it into an instance of another problem, without changing the answer. If we can find a way to transform an instance of an NP-Complete problem into an instance of our problem, and we can transform the solution of our problem back into a solution of the NP-Complete problem, then we can say that our problem is at least as hard as the NP-Complete problem. If we can show that our problem is at least as hard as every problem in NP, then we can say that our problem is NP-Complete.

The first problem to have been proved NP-Complete was the boolean satisfiability (SAT) problem. It was proved NP-Complete by Stephen Cook in 1971, the proof being known as Cook’s Theorem or the Cook-Levin Theorem.

The boolean satisfiability problem asks whether it is possible to assign values to a set of variables in a boolean formula such that the formula evaluates to true. For example, given the formula (a ∨ ¬b ∧ c), we might ask whether it is possible to assign values to a, b, and c such that the formula evaluates to true. This problem is important because many problems in computer science can be reduced to the boolean satisfiability problem.

To prove that a problem is NP-Complete, we must first show that it is a member of NP. This means that we need to be able to verify a "yes" instance of the problem in polynomial time. We then need to find a way to reduce an instance of any other problem in NP to an instance of the problem we are trying to prove is NP-Complete. This reduction must be done in polynomial time, and it must preserve the answer to the problem (i.e., if the original problem is a "yes" instance, the reduced problem must also be a "yes" instance, and vice versa). If we can do this, we can say that the problem is NP-Complete.

It involves transforming the description of a nondeterministic Turing machine into an instance of SAT. The proof is not greatly complex but it is long and requires an explanation of nondeterministic Turing machines.