P, Np a Np-úplnosť: Základy výpočtovej zložitosti

Recenzie čitateľov

V recenziách sa vyzdvihuje „Zlatý lístok“ od Fortnowa ako cenný úvod do problému P vs NP, ktorý vyvažuje prístupnosť a hĺbku. Mnohí čitatelia oceňujú pútavý štýl písania, anekdoty a jasné vysvetlenia, vďaka ktorým sú zložité témy prístupné aj laikom. Niektorí čitatelia však majú problém s technickými zápismi a ťažko ich sledujú, čo naznačuje potrebu predchádzajúcich znalostí alebo základných poznatkov.

⬤ Pútavý a čitateľný štýl písania
⬤ jasné vysvetlenia zložitých tém
⬤ obsahuje anekdoty a diagramy
⬤ komplexné pokrytie P vs NP a súvisiacich tém
⬤ považuje sa za jemný úvod do náročnej témy.

⬤ Používa nevysvetlené notácie, čo niektorým čitateľom sťažuje sledovanie
⬤ vyžaduje predchádzajúce znalosti pre úplné pochopenie
⬤ môže byť príliš zjednodušený pre pokročilých čitateľov.

(na základe 2 čitateľských recenzií)

Pôvodný názov:

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

Obsah knihy:

Táto kniha sa zameriava na otázku P-versus-NP a teóriu úplnosti NP. Poskytuje tiež primerané predbežné informácie týkajúce sa výpočtových problémov a výpočtových modelov.

Otázka P-versus-NP sa pýta, či nájdenie riešenia je alebo nie je ťažšie ako kontrola správnosti riešenia. Alternatívna formulácia sa pýta, či objavovanie dôkazov je alebo nie je ťažšie ako overovanie ich správnosti. Všeobecne sa predpokladá, že odpoveď na tieto ekvivalentné formulácie je kladná, a to sa vystihuje tvrdením, že P je iné ako NP.

Hoci otázka P verzus NP zostáva nevyriešená, teória úplnosti NP ponúka dôkaz o neriešiteľnosti konkrétnych problémov v NP tým, že ukazuje, že sú univerzálne pre celú triedu. Je prekvapujúce, že problémy NP-úplnosti existujú, a navyše stovky prirodzených výpočtových problémov vznikajúcich v mnohých rôznych oblastiach matematiky a vedy sú NP-úplné.