The question of whether the class of problems called NP is the same as the class P is one of the million dollar millennium prize challenges. Even if it wasn't, it would still be important. If NP=P then the world is a very strange place. This is a bonus chapter for Programmer's Guide To Theory.

We all know about the complexity classes P and NP - if not read the relevant chapter in Programmer's Guide To Theory, ISBN  978-1871962895.

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

Contents

1. What Is Computer Science?
   Part I What Is Computable?
2. What Is Computation?
3. The Halting Problem
4. Finite State Machines
   Extract 1: Finite State Machines
   Extract 2: Turing Thinking
5. Practical Grammar
6. Numbers, Infinity and Computation
   Extract 1: Numbers 
   Extract 2: Aleph Zero The First Transfinite
   Extract 3: In Search Of Aleph-One
   Extract 4: Transcendental Numbers
   
7. Kolmogorov Complexity and Randomness
   Extract 1:Kolmogorov Complexity 
   Extract 2: Random?  
8. The Algorithm of Choice
9. Gödel’s Incompleteness Theorem 
10. Lambda Calculus
    Part II Bits, Codes and Logic
11. Information Theory 
12. Splitting the Bit 
13. Error Correction 
14. Boolean Logic 
    Part III Computational Complexity
15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From
16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete

<ASIN:1871962439>

<ASIN:1871962587>

The rough idea however is easy to restate in a nutshell. There are some questions that are very difficult to answer because you have to perform a nearly exhaustive search to find the answer, but if someone offers you a solution you can check its correctness in a much shorter time. Here we use the term "shorter time" to mean that the solution can be found in "polynomial time" i.e. P. If you increase the size of the problem then the solution takes no more than the size squared or cubed or raised to some power. 

Classifying Problems 

Problems that can be solved in polynomial time are said to be in the complexity class P and these are generally regarded as "easy" - but notice that they can still take a long time, too long, in practice. Problems that take longer than polynomial time are such that with a small increase in the size of the problem we get solution times that are comparable to the lifetime of the universe. There is a hierarchy of complexity classes, but P is the one we are most interested in.

That is, for problems in NP, the finding-the-solution part of the problem is not in P, but the checking-correctness is in P.

NP is usually taken to mean "Nondeterministic Polynomial" because if you guess a correct solution then it can be confirmed in polynomial time. Another way of looking at this is if you have an oracle that gives you the correct answer you can check that it is in P.

So there is a sort of sense that NP problems are sort of close to being in P - but this impression goes away once you look at a real NP problem.

The Traveling Salesman Problem

The best known is the traveling salesman problem. You have a set of cities and distances between then and you have to solve a problem involving the distance required to visit all of the cities.

There are three variations on this problem:

1. The decision problem
   Is there a tour with distance equal to or less than D?
2. The search problem
   Find a tour with distance equal to or less than D
3. The optimization problem
   Find a tour with minimum distance Dmin

Confusingly, in general discussion, each of these is called the traveling salesman problem. You can see that they are related in that a solution to the optimization problem gives you a solution to the search problem which in turn gives you a solution to the decision problem. 

The decision problem is in NP because if you need to discover if there is a tour that is D or less in distance you need to check all of the possible tours against D and this is task that grows very quickly as  the number of cities increases (if there are n cities there are n! tours to check),  i.e. it is not in P. However, if I give you a tour that has a distance D or less, this is called a witness or a certificate for the problem. you can check it simply by seeing it if visits each city and it has a distance D or less. This is a task that increases with the number of cities and is in P.

Notice that this also works for the search problem, but not for the optimization problem. Clearly finding a tour with minimum distance means examining all possible tours and so it isn't in P, but if I give you a witness claimed to be the smallest tour, you can only say that it is or isn't if you already know the answer. That is, you still have to do a complete search to confirm that there is no tour that is shorter.

The optimization problem isn't in NP, but as a solution to it provides a solution to the decision and search problem, which are in NP, it is called NP-hard because it is a problem that isn't in NP but has to be at least as hard as a problem that is in NP as a as solution to it is a solution to an NP problem.