2 ms·
It was a university-internal booklet written by Prof. Oded Goldreich when he had taught the course in the early 1990s. Don't think it was ever published as a pr
by einpoklum 7y ago
It was a university-internal booklet written by Prof. Oded Goldreich when he had taught the course in the early 1990s. Don't think it was ever published as a proper book.
See:
https://webcourse.cs.technion.ac.il/236343/Spring2004/book.html https://webcourse.cs.technion.ac.il/236343/Spring2004/book.h...
- sixstringtheory 7y agoAh I see. Well in any case, thanks for the link, it led to several books I'm interested to check out... - Computers and Intractability: A Guide to the Theory of Np-Completeness - Computational Complexity (your page has the one by Papadimitriou, but putting it on my Goodreads list led to two others of the same name by Goldreich and Arora/Barak I didn't know of)
- einpoklum 7y agoPapadimitriou is older, but good, in that the Barak-Arora one is huge, I think. Computers and Intractability is a class, it's from 1979. It's most famous for having "the list" of NP complete problems. Obviously not an exhaustive list, but it still merits the definite article :-) Nowadays this is maintained on-line of course: https://www.nada.kth.se/~viggo/problemlist/compendium.html https://www.nada.kth.se/~viggo/problemlist/compendium.html