Example NP Problems

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

Some examples of NP problems.

Every problem in P :

Examples include:

• Squaring a number
• Eulerian paths (the Gritter Problem)
• Testing primality
• This was a recent surprise.
• http://en.wikipedia.org/wiki/AKS_primality_test

Some strictly harder problems

There are currently no known algorithms for solving these problems in Polynomial Time:

• Factoring Integers
• Given an integer, list all its prime factors
• http://en.wikipedia.org/wiki/Integer_factorization

• Travelling Salesman Problem
• Given a collection of cities and roads, visit each city exactly once.
• (Technically that's the Hamilton Path Problem)
• http://en.wikipedia.org/wiki/Traveling_salesman_problem

• Three Colouring Graphs
• Given a collection of nodes, some of which are joined by lines, colour each node with one of three colours so that no line has the same colour at each end
• http://en.wikipedia.org/wiki/Graph_coloring

• The Knapsack Problem
• Given a collection of numbers and a desired total, find a subcollection that sum to that total.
• http://en.wikipedia.org/wiki/Knapsack_problem

Modern cryptography relies on finding hard instances of problems such as these. The most commonly known - the RSA public-key system - relies on being able to find integers that have a factorisation that's hard to find.

Why are these hard(er)?

Broadly speaking, in each case there are an exponential number of possibilities, and no apparent way to exploit a concept of "closeness". There are n! possible orderings of the cities to visit, but having path that visits all but one city doesn't (necessarily!) help at all. It may be completely wrong in a non-local way.

Similarly with the three-colouring question. The colour of one node may be forced by choices made of colours that are, in some sense, a long way away.

We think that in some very real sense Integer Factorisation (IF) is easier than Graph Three-Colouring (G3C) or the Travelling Salesman Problem (TSP).

Consider integer factorisation. Knowing that 1111111=239*4649 doesn't help at all in trying to find the factorisation of 1111109, even though these numbers only differ by 2.

Intuition about why a given problem is "hard" in this sense is not easy to come by, and once obtained, is not easy to express. At best we can say that the search space is "large" and "brittle." It's not enough simply that there are a lot of possible solutions. The question of finding a minimal spanning tree for a graph has a huge search space, but there is a polynomial time algorithm because the solution space is, in some sense, "nice."

For a large list of NP problems that are in some sense "hard" you can check this page on wikipedia:

• http://en.wikipedia.org/wiki/List_of_NP-complete_problems