What Is NP

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

• Find a route that travels on every road exactly once
• (Sometimes called The Gritter Problem)
• Find a route that visits every city exactly once
• (The Travelling Salesman Problem)

The Gritter Problem is also known as "Finding an Eulerian Cycle."

In particular, the gritter problem can be solved in Polynomial Time, time that only grows as a polynomial function of the size of the instance. Such a problem is said to be in class P, which is the class of all Polynomial Time problems.

The second problem appears not to be in P.

For more details and a less gentle discussion of the Time Complexity of the Travelling Salesman Problem, the wikipedia article is a reasonable reference: http://en.wikipedia.org/wiki/Travelling_salesman_problem Follow the link to "Computational Complexity."

Specifically, for every algorithm we currently have for solving the Travelling Salesman Problem, the time taken (as a function of the size of the instance) grows faster than any polynomial function. At the time of writing the best known algorithms take time proportional to    which grows pretty quickly (although not as quickly as the obvious algorithm, which grows in time proportional to n!. )

Fair enough. The Gritter Problem is easy, the Travelling Salesman Problem is hard. That's life.

But there's a sting in the tail. While finding a solution to the second problem seems to be hard, checking an alleged solution is really easy. For a given instance, if you claim that you have found a way to do it, checking that you're right is quick and simple.

In technical terms, checking your alleged solution only takes Polynomial Time.

I follow your route, mark the cities I visit, then check I got them all. And if you make your map 100 times bigger, it still only takes 100 times longer to check if you're right.

So this is a little puzzling. We have a problem where for each question it's really easy to check an alleged solution, but (as yet) no way even to know if such a solution exists.

This leads to an obvious solution strategy.

The "guessing" part means this is "Non-deterministic" and the checking part takes polynomial time, so this is called a "Non-deterministic Polynomial" (NP) solution attempt, and any problem that lends itself to this sort of "solution" method is called an "NP" problem.

The problem with this "solution" is that for some problems it's very unlikely ever to terminate, so while it might be that it never gives you a wrong answer, it might fail to give you an answer at all.

But all is not lost. Even though we might not be able to solve NP problems efficiently, we now have a handle on the question of how hard problems might be.

The next section gives us our first real result.