P, Np e Np-Completezza: I fondamenti della complessità computazionale

Recensioni dei lettori

Le recensioni evidenziano che “Il biglietto d'oro” di Fortnow è una valida introduzione al problema P vs NP, in grado di bilanciare accessibilità e profondità. Molti lettori apprezzano lo stile di scrittura accattivante, gli aneddoti e le spiegazioni chiare, che rendono gli argomenti complessi accessibili anche ai non addetti ai lavori. Tuttavia, alcuni lettori hanno difficoltà a comprendere le notazioni tecniche e a seguirle, il che suggerisce la necessità di una conoscenza preliminare o di una comprensione di base.

⬤ Stile di scrittura coinvolgente e leggibile
⬤ spiegazioni chiare di argomenti complessi
⬤ include aneddoti e diagrammi
⬤ copertura completa di P vs NP e argomenti correlati
⬤ considerata un'introduzione delicata a un argomento difficile.

⬤ Utilizza notazioni non spiegate, rendendo difficile per alcuni lettori seguirle
⬤ richiede conoscenze pregresse per una piena comprensione
⬤ potrebbe essere troppo semplicistico per i lettori avanzati.

(basato su 2 recensioni dei lettori)

Titolo originale:

P, Np, and Np-Completeness: The Basics of Computational Complexity

Contenuto del libro:

Il libro è incentrato sulla questione P-versus-NP e sulla teoria della completezza NP. Fornisce inoltre adeguati preliminari sui problemi computazionali e sui modelli computazionali.

La domanda P-versus-NP chiede se trovare soluzioni sia più difficile o meno che verificare la correttezza delle soluzioni. Una formulazione alternativa chiede se scoprire le prove sia più difficile o meno che verificarne la correttezza. È opinione diffusa che la risposta a queste formulazioni equivalenti sia positiva, e ciò si coglie dicendo che P è diverso da NP.

Sebbene la questione P-versus-NP rimanga irrisolta, la teoria della completezza NP offre una prova dell'intrattabilità di problemi specifici in NP, dimostrando che sono universali per l'intera classe. È sorprendente che i problemi NP-completi esistano e che centinaia di problemi computazionali naturali che si presentano in molte aree diverse della matematica e della scienza siano NP-completi.