4 ms·

Any recommended books on complexity theory?

• ScottAaronson 8y ago
  A classic from 1994 is "Computational Complexity" by Papadimitriou. Two good sources for newer material (from the past quarter-century) are "Complexity Theory: A Modern Approach" by Arora and Barak, and "The Nature of Computation" by Mertens and Moore. A personal, idiosyncratic favorite is "Gems of Theoretical Computer Science" by Uwe Schoning.