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

Autores/as

  • Elitza Maneva

Resumen

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

Descargas

Publicado

2012-07-12

Cómo citar

Maneva, E. (2012). P <i>versus</i> NP: el problema estrella de la matemàtica de la computació. Butlletí De La Societat Catalana De Matemàtiques, 27(1), 39–62. Recuperado a partir de https://revistes.iec.cat/index.php/BSCM/article/view/75930.001

Número

Vol. 27 Núm. 1 (2012)

Sección

Artículos

Licencia

La propietat intel·lectual dels articles és dels respectius autors.

Els autors en el moment de lliurar els articles a la revista Butlletí de la Societat Catalana de Matemàtiques per a sol·licitar-ne la publicació accepten els termes següents:

  1. Els autors cedeixen a la Societat Catalana de Matemàtiques (filial de l’Institut d’Estudis Catalans) els drets de reproducció, comunicació pública i distribució dels articles presentats per a ser publicats a la revista Butlletí de la Societat Catalana de Matemàtiques.
  2. Els autors responen davant la Societat Catalana de Matemàtiques, de l'autoria i l'originalitat dels articles presentats.
  3. És responsabilitat dels autors l’obtenció dels permisos per a la reproducció de tot el material gràfic inclòs en els articles.
  4. La Societat Catalana de Matemàtiques, està exempta de tota responsabilitat derivada de l’eventual vulneració de drets de propietat intel·lectual per part dels autors.
  5. Els continguts publicats a la revista estan subjectes —llevat que s’indiqui el contrari en el text o en el material gràfic— a una llicència Reconeixement - No comercial - Sense obres derivades 3.0 Espanya (by-nc-nd) de Creative Commons, el text complet de la qual es pot consultar a https://creativecommons.org/licenses/by-nc-nd/3.0/es/deed.ca. Així doncs, s’autoritza el públic en general a reproduir, distribuir i comunicar l’obra sempre que se’n reconegui l’autoria i l’entitat que la publica i no se’n faci un ús comercial ni cap obra derivada.
  6. La revista Butlletí de la Societat Catalana de Matemàtiques no es fa responsable de les idees i opinions exposades pels autors dels articles publicats.