P, Np i Np-zupełność: Podstawy złożoności obliczeniowej

Opinie czytelników

Recenzje podkreślają „The Golden Ticket” Fortnowa jako wartościowe wprowadzenie do problemu P vs NP, równoważące przystępność z głębią. Wielu czytelników docenia wciągający styl pisania, anegdoty i jasne wyjaśnienia, dzięki którym złożone tematy stają się przystępne dla laików. Jednakże, niektórzy czytelnicy zmagają się z technicznymi zapisami i uważają je za trudne do zrozumienia, co sugeruje potrzebę wcześniejszej wiedzy lub zrozumienia podstaw.

⬤ Wciągający i czytelny styl pisania
⬤ jasne wyjaśnienia złożonych tematów
⬤ zawiera anegdoty i diagramy
⬤ kompleksowe omówienie P vs NP i powiązanych tematów
⬤ uważany za łagodne wprowadzenie do trudnego tematu.

⬤ Używa notacji, które nie zostały wyjaśnione, co utrudnia niektórym czytelnikom śledzenie
⬤ wymaga wcześniejszej wiedzy dla pełnego zrozumienia
⬤ może być zbyt uproszczony dla zaawansowanych czytelników.

(na podstawie 2 opinii czytelników)

Oryginalny tytuł:

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

Zawartość książki:

Książka ta koncentruje się na pytaniu P-versus-NP i teorii NP-zupełności. Zawiera ona również odpowiednie wprowadzenie dotyczące problemów obliczeniowych i modeli obliczeniowych.

Pytanie P-versus-NP dotyczy tego, czy znajdowanie rozwiązań jest trudniejsze niż sprawdzanie ich poprawności. Alternatywne sformułowanie pyta, czy odkrywanie dowodów jest trudniejsze niż weryfikacja ich poprawności. Powszechnie uważa się, że odpowiedź na te równoważne sformułowania jest pozytywna, co można uchwycić, mówiąc, że P różni się od NP.

Chociaż pytanie P-versus-NP pozostaje nierozstrzygnięte, teoria NP-zupełności oferuje dowody na niewykonalność konkretnych problemów w NP, pokazując, że są one uniwersalne dla całej klasy. Co zadziwiające, problemy NP-zupełne istnieją, a ponadto setki naturalnych problemów obliczeniowych pojawiających się w wielu różnych dziedzinach matematyki i nauki są NP-zupełne.