Carregant...
Fitxers
Tipus de document
ArticleVersió
Versió publicadaData de publicació
Llicència de publicació
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/136062
P versus NP: el problema estrella de la matemàtica de la computació
Títol de la revista
Autors
Director/Tutor
ISSN de la revista
Títol del volum
Recurs relacionat
Resum
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».
Matèries
Matèries (anglès)
Citació
Citació
MANEVA, Elitza. P versus NP: el problema estrella de la matemàtica de la computació. _Butlletí de la Societat Catalana de Matemàtiques_. 2012. Vol. 27, núm. 1, pàgs. 39-62. [consulta: 29 de gener de 2026]. ISSN: 0214-316X. [Disponible a: https://hdl.handle.net/2445/136062]