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.
[youtube=http://www.youtube.com/watch?v=6ybd5rbQ5rU]
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.
Beyond NP-complete
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:
Slide the blocks in the puzzle above to flip the initial configuration.
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.
Actually, it is still not known if even PSAPCE is harder than P.
P!=PSPACE may be easier to prove than P!=NP (it can’t be harder), but apparently not enough easier.
Right. I was using the idea that since it takes an exponential time to write down the solution, it must be outside P. However, I suppose it is conceivably possible (if unlikely) that determining whether a solution exists (rather than actually finding it) merely takes polynomial time.
The only way it can take exponetial time to write down a solution is if the solution is exponentially long, so it takes exponetial space to write it as well. So the definition of PSPACE only really works for decision problems anyway.
What you may mean is that it takes exponential time to step through a solution to a PSPACE complete puzzle.
It is ineresting that if you are allowed to communicate with a “prover” (who can use as much time and space as he likes), it is possible to determine if a solution exists in probabilistic polynomial time. Even though the prover can’t show you a solution (they are too long), he can prove that one exists (or not), you don’t need to take his word for it. This fact is known as PSPACE=IP.
Of course it is intuitively obvious that PSPACE!=P (even more so than NP!=P), but intuitively obvious things have been wrong before.
Sliding-block puzzles are PSPACE-complete, yet the solution can be of exponential length. For instance, the Tower of Hanoi puzzle (the optimal solution of which takes 2^n moves) can be embedded in a sliding-block puzzle of size polynomial in n. If I interpret your last paragraph correctly, this means that a proof of the (non-)existence of a solution is only of polynomial size, despite the solution itself being exponentially long? That is indeed very interesting.