P, Np a Np-úplnost: Np a základy výpočetní složitosti

Recenze čtenářů

V recenzích je vyzdvižena kniha Fortnowa „The Golden Ticket“, která je cenným úvodem do problematiky P vs. NP a vyvažuje přístupnost a hloubku. Mnoho čtenářů oceňuje poutavý styl psaní, anekdoty a jasná vysvětlení, díky nimž jsou složitá témata přístupná i laikům. Někteří čtenáři však mají potíže s technickými poznámkami a obtížně je sledují, což naznačuje potřebu předchozích znalostí nebo základních poznatků.

⬤ Poutavý a čtivý styl psaní
⬤ jasná vysvětlení složitých témat
⬤ obsahuje anekdoty a diagramy
⬤ komplexní pokrytí P vs NP a souvisejících témat
⬤ považováno za jemný úvod do obtížného tématu.

⬤ Používá nevysvětlené notace, což některým čtenářům ztěžuje porozumění
⬤ vyžaduje předchozí znalosti pro plné pochopení
⬤ může být příliš zjednodušené pro pokročilé čtenáře.

(na základě 2 hodnocení čtenářů)

Původní název:

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

Obsah knihy:

Těžištěm této knihy je otázka P versus NP a teorie úplnosti NP. Poskytuje také odpovídající předběžné informace týkající se výpočetních problémů a výpočetních modelů.

Otázka P-versus-NP se ptá, zda je nalezení řešení těžší než kontrola správnosti řešení. Alternativní formulace se ptá, zda objevování důkazů je či není těžší než ověřování jejich správnosti. Obecně se má za to, že odpověď na tyto ekvivalentní formulace je kladná, a to se vystihuje tvrzením, že P se liší od NP.

Ačkoli otázka P versus NP zůstává nevyřešena, teorie úplnosti NP nabízí důkaz o neřešitelnosti konkrétních problémů v NP tím, že ukazuje, že jsou univerzální pro celou třídu. Je až s podivem, že problémy NP-úplnosti existují, a navíc stovky přirozených výpočetních problémů vznikajících v mnoha různých oblastech matematiky a vědy jsou NP-úplné.