«P = NP? Equazione facile, N = 1», dirà lo studente delle superiori. «Dimentichi P = 0», aggiungerà la sua compagna più rigorosa. La realtà è un po’ più complicata. Prima di comprenderne il significato preciso, proviamo a coglierne l’idea attraverso un esempio.
Risolvere un puzzle
------------------
Nel 2007, l’azienda giapponese di giocattoli Takara Tomy Co. propose un puzzle di duecentocinquantasei tessere quadrate, da collocare in un quadrato di dimensioni 16 × 16. Ogni lato di una tessera ha il colore del triangolo che poggia su quel lato (come nell’esempio qui sotto, con nove tessere nella figura a sinistra). Occorre completare il puzzle rispettando un unico vincolo: due tessere possono essere affiancate solo se i due lati a contatto hanno lo stesso colore (il puzzle è risolto nella figura a destra).
