Distinguish decidability from tractability and identify the model behind a complexity claim.
Open the source ↗How to study this source
What can a machine compute?
Distinguish decidability from tractability and identify the model behind a complexity claim.
Ideas and questions
Read background definitions when a term blocks the argument. Then return to the source and reconstruct its claim in your own words.
Read alongside, read against
Computational Complexity
Christos Papadimitriou. Compare assumptions, evidence and scope with the source above. These are editorial companions, not necessarily direct responses.
Introduction to the Theory of Computation
Michael Sipser. Compare assumptions, evidence and scope with the source above. These are editorial companions, not necessarily direct responses.
A New Kind of Science
Stephen Wolfram. Compare assumptions, evidence and scope with the source above. These are editorial companions, not necessarily direct responses.
An Introduction to Kolmogorov Complexity
Li · Vitányi. Compare assumptions, evidence and scope with the source above. These are editorial companions, not necessarily direct responses.
The Annotated Turing
Charles Petzold. Compare assumptions, evidence and scope with the source above. These are editorial companions, not necessarily direct responses.