Bibliografia sul problema del millennio P e NP

[Ryukushi1]

Ciao a tutti, sono abbastanza interessato alla teoria della complessità computazionale e mi incuriosisce approfondire l'argomento relativo al problema del millennio riguardante la classificazione P e NP.

Qualcuno conosce qualche articolo o qualche testo da consultare?

[hamming_burst]

Ciao,
che tipo di approfondimento vuoi fare? di tipo divulgativo?

[vict85]

Potresti cominciare a leggerti l'introduzione data dal CMI: http://www.claymath.org/millenium-probl ... np-problem
A fianco trovi dei pdf che lo approfondiscono, anche se sono penso un po' tecnici.

[Ryukushi1]

"hamming_burst":Ciao,
che tipo di approfondimento vuoi fare? di tipo divulgativo?

Sia divulgativo, sia scientifico.

Comincio a leggermi i documenti del sito.

Gracias a todos.

[hamming_burst]

un po' di materiale interessante ed abb. aggiornato:

- The Long Slow Road to a $1 Million Millennium Prize (con svariati rimandi ad articoli e libri)
- P, NP, and NP-Completeness: The Basics of Computational Complexity di Oded Goldreich - 2010
- The Second P=?NP Poll di William I. Gasarch (first poll 2001)
- http://awards.acm.org/info/vardi_9543503.cfm

in italiano:
- Introduzione agli algoritmi e strutture dati 3/ed di Cormen & Co. (disp. anche in inglese) - 2010 : capitolo 34 e other
- Algoritmi e strutture dati 2° ed di Bertossi e Montresor - 2010 : Parte Quarta: Problemi Intrattabili (cap. 18)