One of the disadvantages of high profile classes like NP is that many function problems that sound as if they might reduce to a decision problem in NP don’t. For example, the problem of finding the shortest path through a network clearly isn't a suitable candidate for NP. Why not? Because you cannot supply a witness that verifies that a path is the shortest in polynomial time. If I provide you with a path that I claim is shortest you still have to compare it to all the other possible paths to prove that it is, which is clearly not in polynomial time.
Compare this to the seemingly similar problem of proving that a given path is not the shortest - i.e. you don't actually have to find the shortest path, just prove that the one given is or is not the shortest. This is NP because all that has to be done is to provide an example path, i.e. one path, that is shorter. There is no requirement to compare it to every possible path, just to one that is actually shorter. Thus, given a path A it clearly isn't the shortest if you are given the extra piece of information that path B is shorter, i.e. B is a witness that A isn't the shortest path.
Perhaps the best known “difficult” problem is the TSP – Traveling Salesman Problem. Given a list of cities simply find the shortest route that visits each city and returns to the starting point. Clearly this is not in NP because no witness verifiable in polynomial time can be found. If I give you a candidate path you cannot verify it is the shortest without searching the entire solution space for the shortest. The witness doesn't help.
As before, we can turn it into an NP problem by changing the question to “is there a route shorter than L”. This is in NP, but it isn’t the full TSP problem. We will return to these not-quite NP problems later, in the context of NP-hard problems.
The Hamiltonian Problem
Another well known example is the Hamiltonian. A graph (another name for a network) is said to be “Hamiltonian” if there is a path through it visiting each node exactly once.
The graph in the diagram below is Hamiltonian because there exists a path that visits each node exactly once -shown on the right.
The following should be fairly obvious to you now:
Is proving that a graph is Hamiltonian in P? No, it takes exponential time to find a path that visits each node by examining each path until you find one that is Hamiltonian.
Is proving that a graph is not Hamiltonian in P? Obviously not, because you have to check every path to prove that a suitable one doesn't exist and so this must take longer on average than (1).
Is proving that a graph is Hamiltonian in NP? Yes. The witness is a path that visits each node exactly once. Once you have the description of such a path, checking that it visits each node only once is trivial and obviously in P.
Is proving that a graph is not Hamiltonian in NP? Probably not because you can't give a piece of information that allows someone to check that a suitable path doesn't exist. You have no choice but to check them all and that's clearly the same as (2).
Is proving that a graph is not Hamiltonian in co-NP? As it is the complement of the original problem, which is in NP, it is in co-NP.
Not included in this extract:
Boolean Satisfiability
NP-Complete and Reduction
Proof That SAT Is NP-Complete
NP-Hard
What if P = NP?
Summary
We generally recognize two types of algorithm - function evaluation and decision problems. However, function evaluation can be converted into a decision problem.
NP decision problem are easy to check if you have a proposed solution, a witness, but otherwise may be hard to solve. Any problem for which a witness exists can be checked in polynomial time and is therefore in NP.
A problem in NP needs, at most, exponential time and thus P ⊆ NP ⊆ Exp.
Co-NP problems are derived from NP problems by changing the decision around. For example, "is there a subset that sums to zero" is in NP, whereas "there is no subset that sums to zero" is in co-NP. It isn't known if all co-NP problems are also in NP.
The Boolean satisfiability problem, CircuitSAT, is an archetypal NP problem - find the inputs to a Boolean circuit that produces a true output.
There are many variants on the more general SAT problem. The k-SAT problem restricts the form of the Boolean function to use nothing but k inputs ANDed together and then ORed with other similar clauses. What is surprising is that 2-SAT is in P, but k-SAT for k>2 is in NP.
One of the most important theorems in computer science is that k‑SAT for k>2 or CircuitSAT is NP-complete. That is, any problem in NP can be reduced to SAT. What this means is that if a polynomial algorithm exists for any NP-complete problem then there is a polynomial algorithm for all NP problems and P=NP.
NP-hard problems are NP-complete problems that are not necessarily in NP. If you were to find a polynomial solution to any NP-hard problem then P=NP. Problems in NP cannot be harder than NP-hard problems.
The consequences of proving P=NP are often assumed to be serious – cryptographic codes would suddenly be insecure, for example. However, the concept of a "galactic" algorithm puts this idea in perspective. A galactic algorithm is one that only achieves its asymptotic performance for galactically large values of problem. If P=NP but only for a galactic polynomial algorithm, then nothing has changed from a practical point of view.
A Programmers Guide To Theory
Now available as a paperback and ebook from Amazon.
Contents
What Is Computer Science? Part I What Is Computable?
A novel investigation into the gender gap between men and women regarding coding ability was undertaken by Dr Siân Brooke. Her conclusion? There is a difference in the Python code [ ... ]
