Editing ExampleNPProblems
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Wed Apr 24 18:46:12 2024.
Press
to finish editing.
Who can edit this page?
The World
Members
Council
Admin
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: * Squaring a number * Eulerian paths (the Gritter Problem) * Testing primality ** This was a recent surprise. ** http://en.wikipedia.org/wiki/AKS_primality_test [[[>50 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: * 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 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. [[[>50 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 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?