I feel like a travelling salesman for wolfram.com! (Pun definitely intended!). NP complete is: A problem which is both NP (verifiable in nondeterministic polynomial time) and NP-hard (any other NP-problem can be translated into this problem). Examples of NP-hard problems include the Hamiltonian cycle and traveling salesman problems. and polynomial time is "under construction" at mathematics.wolfram.com! Argh! Well, lets see... (google, google, google...): From http://www.nist.gov/dads/HTML/polynomialtm.html (another authority in these matters): -=-=-=- Polynomial time Definition: When the execution time of a computation, m(n), is no more than a polynomial function of the problem size, n. More formally m(n) = O(n^k) where k is a constant [n is raised to k. -hooya27]. See also NP, exponential, logarithmic. Note: Broadly speaking, polynomial time algorithms are reasonably to compute. The time to run exponential algorithms grows too fast to expect to be able to compute exact solutions in all cases. -=-=-=-

A problem has a polynomial-time solution if the computation time is bounded by a polynomial function of the input length. Usually, the "time" is measured in terms of the number of elementary computations required, so that it is independent of the platform (although it could depend on what model of computation is being used: Church's thesis posits that it shouldn't, but this hasn't been proven). A problem is NP if there is a program such that for every input which has a yes answer to the problem, there is a certificate that when inputted into the computer program, runs in polynomial time in the input length and returns "yes". Polynomial time algorithms are NP, since one may take the certificate to just be the input. Map coloring is a good example of an NP problem. Given a map, the question is can one color the map with 3 colors (so that adjacent countries have distinct colors). A simple algorithm is to try all combinations of 3 colors for each country. If the number of countries is n, then the number of combinations of colors is 3^n, which is exponential in n. So if the graph is not 3-colorable, then this simple-minded algorithm will take exponential time to determine that there is no 3-coloring, and thus is not a polynomial time algorithm. But if the map is 3-colorable, then the obvious certificate is a 3-coloring. Given a 3-coloring, one only needs to check that for every pair of adjacent countries, the colors are distinct. This gives an algorithm which is polynomial-time in the input length, which is essentially the number of countries, along with which pairs of countries are adjacent. Thus, this problem is NP. An NP-complete problem has the property that any other NP problem can be translated into it in polynomial time. For example, 3-coloring maps is an NP-complete problem. Given any other NP-problem, there is some way to translate the input for that problem into a map, which will be 3-colorable if and only if the problem has a positive answer. It is conjectured that no matter what algorithm one constructs to answer an NP-complete problem, there will be a sequence of inputs for which the algorithm run time will be greater than any polynomial function of the input length. There is a precise mathematical formulation of this question which requires the computer to be a Turing machine. This is the NP vs. P question, and the Clay math institute offers a prize for $1,000,000 to a published answer to this question (www.claymath.org). To say that a puzzle is NP-complete that means one has to translate the puzzle into a yes/no question. It has been shown that Minesweeper and Tetris are NP-complete, but to make this precise, one needs to formulate these as mathematical questions.