Complexity Zoo
The Complexity Zoo is a menagerie of animals (and monsters!) that inhabit the landscape of computational complexity classes. It showcases the diversity of computational problems — from \(\mathsf{P}\) and \(\mathsf{NP}\) to \(\mathsf{Unsolvable}\). While computer scientists have long worked to draw precise boundaries between these classes, many boundaries remain uncertain and the overall picture may change as research progresses.
This section presents an exhibit of complexity classes for decision problems, reorganized to emphasize quantum-related classes such as \(\mathsf{BQP}\) and \(\mathsf{QMA}\). It also includes a zoo of parameterized decision problems, which may be of interest to some visitors.