4 ms·
Sipser was the one my alma mater used, so if you could, please post the one you used! I’d be interested in an alternative.
by sixstringtheory 7y ago
Sipser was the one my alma mater used, so if you could, please post the one you used! I’d be interested in an alternative.
- goric 7y agoHopcroft, Motwani, and Ullman's Introduction to Automata Theory, Languages, and Computation by is another classic text
- einpoklum 7y agoIt 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