«¿P = NP? Ecuación fácil: N = 1», dirá el alumno de instituto. «Te olvidas de que P = 0», añadirá su compañera, más rigurosa. La realidad es algo más complicada. Antes de comprender su significado preciso, intentemos captar la idea mediante un ejemplo.
Resolver un rompecabezas
------------------
En 2007, la empresa japonesa de juegos Takara Tomy Co. propuso un rompecabezas de doscientas cincuenta y seis piezas cuadradas, que deben colocarse en un cuadrado de 16 × 16. Cada lado de una pieza tiene el color del triángulo que se apoya en él —como en el ejemplo de abajo, con nueve piezas en la figura de la izquierda—. Hay que completar el rompecabezas respetando una única condición: solo pueden colocarse dos piezas contiguas si los dos lados que se tocan tienen el mismo color (el rompecabezas está resuelto en la figura de la derecha).
