Computability and Complexity Theory

This book surveys theoretical computer science, presenting fundamental concepts and results. Updated and revised, the new edition includes two new chapters on nonuniform complexity, circuit complexity and parallel complexity, and randomized complexity.