4 ms·
The best book on the subject I know of is Introduction to the Theory of Computation, by Michael Sipser. Very readable and lucid. Great exercises.
by gcv 18y ago
The best book on the subject I know of is Introduction to the Theory of Computation, by Michael Sipser. Very readable and lucid. Great exercises.
- neilc 18y agoYes, definitely the best introductory book on the subject I've ever seen. Indeed, the Sipser book is a model for how to write a very readable, accessible CS theory textbook. As far as how complexity theory on parallel computing, communication complexity is one related approach: http://en.wikipedia.org/wiki/Communication_complexity http://en.wikipedia.org/wiki/Communication_complexity which provides a rigorous way to characterize how much communication is inherently required to solve a particular problem.