Example NP Problems

Links to this page
Edit this page
Entry portal
Advice For New Users

Prev: Problem A Is Harder Than Problem B / Next: What Is NP-Complete?

Some examples of NP problems.

Every problem in P :

We showed earlier that P problems are in NP , so every P problem is an example of an NP problem.

Examples include:

This is, to some extent, the nub of the problem. We don't know that there are any problems in NP that aren't also in P, because we don't know that NP is strictly bigger. That is the P vs NP question, and now you can see it arising naturally from just thinking about these things.
But that's not interesting. What we want are examples of problems that are strictly harder (See problem A is harder than problem B) - problems which are in NP, but for which no Polynomial Time algorithm is know.

Some strictly harder problems

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

It's important to note that not every instance of these problems takes a long time to solve. It's conjectured that the vast majority of instances can be solved in polynomial time, and that it's only a vanishingly small proportion that take longer.

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:

The sense in which these are known to be "hard" is the subject of the next section.
Prev: Problem A Is Harder Than Problem B / Next: What Is NP-Complete?
Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout