Căderea barierelor algoritmice: P=np?

Recenzii ale cititorilor

Cartea „Algorithmic Barriers Falling: P = NP” conține un lung interviu cu Donald E. Knuth, în care sunt discutate diverse subiecte precum istoria, complexitatea algoritmică și anecdote personale. Cartea îmbină perspective tehnice cu povești captivante, subliniind în special momentele de descoperire în teoria algoritmilor.

Cartea oferă subiecte diverse legate de Knuth, contexte interesante privind conceptele algoritmice și anecdote personale pătrunzătoare. Ea oferă informații valoroase care nu au fost incluse în lucrări anterioare, cum ar fi „TAOCP”, și prezintă idei complexe într-o manieră accesibilă, făcând-o plăcută pentru cititorii interesați de informatică.

Unii cititori ar putea găsi detaliile tehnice provocatoare dacă nu sunt bine versați în algoritmi. De asemenea, discuțiile ample pot părea tangențiale sau copleșitoare pentru cei care caută o explorare mai concentrată a P vs. NP.

(pe baza a 1 recenzii ale cititorilor)

Titlul original:

Algorithmic Barriers Falling: P=np?

Conținutul cărții:

"Un premiu de 10 $ de la Blum, 10 $ de la Meyer, 4 $ de la Paterson și 30-DM de la Schnorr este oferit celui care rezolvă primul problema Cook-Karp dacă P = NP.

Blum a pariat 100 $ că P = NP față de 1 $ Paterson că P = NP". -- SIGACT News, ianuarie 1973, pagina 3 Aceste pariuri jucăușe reflectă optimismul tineresc în teoria complexității.

A împărtășit Donald E. Knuth acest optimism la acea vreme? Și cum s-au împletit descoperirile teoreticienilor complexității cu munca de pionierat a lui Knuth în analiza algoritmilor? Prin investigarea gândurilor lui Knuth cu privire la fundamentele teoretice ale calculului eficient, această carte pune în lumină presupunerea actuală a lui Knuth că P = NP.