P versus NP: el problema estrella de la matemàtica de la computació

El problema «P versus NP» és un dels set Problemes del Mil.lenni de l?Institut
Clay de Matemàtiques, la solució del qual estaria premiada amb un milió de dòlars. En
aquest article presentem de manera divulgativa el problema i els seus orígens, donant
pel camí exemples de problemes computacionals de diferents nivells de dificultat,
alguns algoritmes no trivials, la definició de màquina de Turing ?el model matemàtic
d?ordinador? i el concepte de reducció polinòmica entre problemes. La part més
avançada de l?article presenta una demostració del teorema de Razborov sobre circuits
monòtons de l?any 1985 que resol un cas especial de la conjectura. També donem
una traducció al català d?una carta de Gödel a Von Neumann de l?any 1956 que es va
descobrir l?any 1988 i que es pot considerar com la primera formulació per escrit del
problema «P versus NP».