NP-Complete is one of those concepts that takes quite a bit of background knowledge to get a really good handle on. Disclosure: I just finished an undergraduate Algorithm Analysis course this week, so this knowledge is fresh in my mind, I'll try to explain in the way that I learned, but do note that it may not be strictly correct academically.

When speaking about the efficiency of a program or algorithm, we frequently use Asymptotic, or "Big-O" notation [1] to describe how the time requirements of a program scale relative to its input. For example, Bubble sort is an example of an O(n^2) Algorithm[2], which means that if it takes 1 second to sort a list of size=10, then it will take roughly 10 seconds to sort a list of size=100. The reason we use Big-O notation is because it gives an idea of how the program will perform on any computer independent of other factors like processor speed.

Bubble sort is an example of an algorithm that, while not the most efficient algorithm for sorting, does take polynomial time, which means that its big-O is expressible as some O(n^k) where k is some reasonably small number (My professor says that k<=3 is what many agree as reasonable, but I'm sure that number varies). Many problems however do not have an algorithm that solves the problem in Polynomial time. To solve the Traveling Salesman Problem exactly can take O(n!) time[3], and solving the knapsack problem takes O(2^n) time[4]. Note that there are algorithms that may solve exponential problems such as these approximately, or heuristically in polynomial time, but finding the exact solution takes massive amounts of time for any decently large value of n.

It's natural to wonder why some problems are "easy" to solve, and why some are "hard" to solve, researchers have been puzzling over this for some time and have come up with a classification for "easy" and "hard" problems that they call P and NP. For the sake of this classification, we consider an algorithm to have two stages: stage 1 is where the problem is solved and a candidate answer is produced, stage 2 is where the candidate answer produced by stage 1 is verified to be a correct and valid answer to the problem. For a problem to be classified as P (which which stands for Polynomial), both stage 1 and stage 2 of its algorithm must have polynomial time requirements. On the other hand we have NP, which does not stand for Non-Polynomial like you might expect, instead it stands for Non-Deterministically Polynomial. There's a lot of theory behind this concept, but essentially it means that the only possible way for stage 1 of this algorithm to have polynomial time is to resort to non-deterministic algorithms[5], one example of which is an oracle algorithm which will instantly provide you the correct answer magically[6]. NP-complete is a term that means that once stage 1 of an NP-complete algorithm has magically produced the correct answer, stage 2 can still verify that answer in polynomial time. Also note that NP as a set of problems contains all problems in P, since even though a polynomial time stage 1 may exist, the problem still could employ a non-deterministic stage 1 also.

The first problem shown to be NP-complete was the Boolean Satisfiability Problem or SAT problem in 1971[7] which asks, given a formula consisting of boolean input statements, AND's, OR's and NOT's, is there any combination of inputs such that the result of the formula is true. Researchers soon discovered that it was possible to show other problems like the 3-CNF SAT problem are NP-complete by showing that problems could be transformed so that they could be solved directly by the SAT algorithm. A good way to think about this is that if you have an algorithm to solve mathematical addition, you could create an algorithm to solve mathematical multiplication by transforming the inputs, for example 2x3 could be transformed into 2+2+2, and this would let you solve multiplication by transforming to addition. This is how researchers today prove that a problem is NP-complete, by reducing their problem to a known NP-complete problem. An interesting side effect of this is that all known NP-complete problems today form a network of transformations, from any problem to any other problem, see [8] for an example of this. This also means that if a true Polynomial solution to ANY NP-complete problem is found, then every other NP-complete problem would also be solved automagically through transformations.

From the Abstract of the paper: "We prove that completing an untimed, unbounded track in TrackMania Nations Forever is NP-complete by using a reduction from 3-SAT and showing that a solution can be checked in polynomial time." which means that this researcher takes the TrackMania problem, and reduces it to the 3-SAT to prove that the TrackMania problem is NP-complete

Hope this helps. If anyone who knows more than me has any corrections to make, please let me know.

[1] https://en.wikipedia.org/wiki/Big_O_notation

[2] https://en.wikipedia.org/wiki/Bubble_sort

[3] https://en.wikipedia.org/wiki/Travelling_salesman_problem

[4] https://en.wikipedia.org/wiki/Knapsack_problem

[5] https://en.wikipedia.org/wiki/Nondeterministic_algorithm

[6] https://en.wikipedia.org/wiki/Oracle_machine

[7] https://en.wikipedia.org/wiki/Boolean_satisfiability_problem

[8] https://en.wikipedia.org/wiki/NP-completeness#NP-complete_pr...