Complexity Theory
Study of computational complexity and resource requirements
Complexity Theory#
Complexity theory studies the resources required to solve computational problems, focusing on time and space complexity, and the classification of problems into complexity classes.
Topics#
- Time Complexity
- Space Complexity
- P vs NP Problem
- NP-Completeness
- Polynomial Time Reductions
- Complexity Classes
- Randomized Complexity
- Quantum Complexity
- Circuit Complexity
- Communication Complexity
Resources#
Books#
- Computational Complexity by Christos H. Papadimitriou
- Introduction to the Theory of Computation by Michael Sipser
- The Nature of Computation by Cristopher Moore, Stephan Mertens
- Computational Complexity: A Modern Approach by Sanjeev Arora, Boaz Barak
Online Resources#
- MIT OpenCourseWare: Computational Complexity
- Stanford: Complexity Theory
- Princeton: Algorithms and Complexity