Książka o złożoności obliczeniowej


(Quester) #1

Czy mógłby ktoś polecić książkę, w której byłyby od podstaw opisane kwestie złożoności obliczeniowej algorytmów i trudności problemów, w szczególności klas P, NP, NP-zupełnych oraz transformacji wielomianowej? Pytam, bo ciężko znaleźć materiał opisujący to w sposób przystępny i od podstaw.


(kostek135) #2

Możesz zacząć od tego LINK. Jeśli będzie to za mało w sekcji 8.1 masz odnośniki do literatury.

 

Zdefiniuj przystępny sposób. Jeśli masz nadzieję na uniknięcie części matematycznej to zapomnij. Dział ten to praktycznie sama matematyka, a wyłącznie wnioski z twierdzeń mają odzwierciedlenie w informatyce.