The P versus NP conjecture essentially asks whether any problem whose solution can be easily verified can also be easily solved. Here, ‘easily’ technically means ‘computed in polynomial time on a Turing machine’.
If you think for a moment, it is difficult to imagine that P (easily solvable) does equal NP (easily checkable). For instance, if I asked you to factorise 2^32 + 1 into prime factors, you might be stuck for a while. However, when I tell you that it’s 641 × 6700417, you can very quickly verify that it’s correct. So, prime factorisation lies in NP, but there is no known polynomial-time algorithm for doing it*. Indeed, it could well be a counter-example to the P = NP conjecture.
* Interestingly, we can actually determine whether a number is prime in polynomial time, but this gives no clues as to its factorisation.
If any NP problem is a counter-example, then so is every problem in a broad class known as NP-complete. Contrapositively, solving a NP-complete problem in polynomial time would prove that P = NP for all such problems. Quite a lot of practical problems are known to be NP-complete, which is why there is a large prize of $1000000 for a proof in either direction.
Travelling Salesman Problem
One such example of a NP-complete problem is the Travelling Salesman Problem. This asks for the shortest route on a network which visits every point once and returns to the original location. Surprisingly, the problem of determining whether such a route (a Hamiltonian circuit) even exists is also NP-complete, so precisely as difficult.
Amazingly, there’s actually a thriller exploring the repercussions of a proof that P = NP (although it almost certainly isn’t). It’s being screened for the first time in the UK at the CMS on 20th November.
Even if P = NP and a valid proof is produced, it is unlikely that it would cause all these complications. For instance, it could be that the proof is non-constructive, and therefore people will still have to search for an algorithm to solve one of these NP-complete problems. Additionally, such an algorithm may still have intractably long running time: a computer program taking O(n^100) time would not really be practical, even though it’s strictly polynomial.
There are actually harder problems than NP-complete, and a polynomial-time algorithm wouldn’t extend to those. For example, sliding block puzzles fall into the category of PSPACE-complete, which is strictly harder than P. A popular one of these puzzles is Conway’s Century, displayed below:
It takes 150 moves to solve this variant, if I remember correctly. Robert Hearn and Erik Demaine demonstrated that sliding-block puzzles and some other types of puzzles can simulate logic gates and thus linear-bounded automata, proving the puzzles PSPACE-complete. PSPACE-complete is the hardest type of bounded one-player puzzle possible, and is achieved even by general sliding-block puzzles composed entirely of dominos.
If we allow two-player games such as chess puzzles on arbitrarily large initial configurations (without the stupid 50-move rule, which would ruin this if included), an even harder complexity class is achieved: EXPTIME-complete. These take exponential time to solve, so there is no hope of an efficient algorithm. As such, computer programs fail miserably at playing similar games (such as Go) on large boards.
Take your favourite PSPACE-complete puzzle and extend it to an infinite board (say, an arbitrary finite configuration on an arbitrary repeating background). This is then in general undecidable, so no algorithm has any hope of solving it, not even when allowed to run ad infinitum. There’s even an algorithmic way to build an infinite sliding block puzzle which can be solved if and only if the Riemann hypothesis is false.