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

Abstract

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».