Please use this identifier to cite or link to this item:
http://hdl.handle.net/2445/136062
Title: | P versus NP: el problema estrella de la matemàtica de la computació |
Author: | Maneva, Elitza |
Keywords: | Teoria de la computació Theory of computation |
Issue Date: | 2012 |
Publisher: | IEC |
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». |
Note: | Reproducció del document publicat a: https://doi.org/10.2436/20.2002.01.41 |
It is part of: | Butlletí de la Societat Catalana de Matemàtiques, 2012, vol. 27, num. 1, p. 39-62 |
URI: | http://hdl.handle.net/2445/136062 |
Related resource: | https://doi.org/10.2436/20.2002.01.41 |
ISSN: | 0214-316X |
Appears in Collections: | Articles publicats en revistes (Matemàtiques i Informàtica) |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
605241.pdf | 588.8 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License