What is the best book for a student learning about concepts such as NP-hard, NP-complete and P=?NP?
I've already got the CLR but it doesn't really cover these particular topics as thoroughly.
+1
A:
Any textbook on computability and complexity would be useful. Introduction to the Theory of Computation by Sisper is a good one.
Also there are lots of good resources if you google those terms - this is a common undergrad course and many professors post class notes online.
David
2010-03-26 17:28:28
A:
Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael Garey and David S. Johnson. is a classic (1979).
anno
2010-03-26 19:15:22
+1
A:
Introduction to Algorithms by Thomas Cormen is a very good book on Algorithms and also there is The Algorithm Design Manual
Rachel
2010-03-29 23:18:15
Introduction to Algorithms is very good.
Ralf
2010-04-09 08:56:15
A:
Introduction to Algorithms has a very good chapter on NP-completeness and tractability, and it's the one I usually recommend to my students.
Garey & Johnson's guide is basically list of the known NP-complete problems, and while certainly useful as a reference book, I wouldn't recommend it as an introduction.
olaan
2010-04-09 08:54:01