En teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada.
Una clase de complejidad tiene una definición de la forma:
|
La siguiente tabla muestra algunas de las clases de problemas (o lenguajes o gramáticas) que se consideran en teoría de la complejidad computacional. Cuando la clase X es un subconjunto estricto de Y, X aparece en la tabla bajo Y con una línea sólida uniéndolos. Cuando es subconjunto pero no se sabe si es estricto, la línea es cortada y gris. Técnicamente hablando, el corte entre problemas decidibles e indecidibles es tema de la Teoría de la computabilidad, pero resulta interesante mencionarlos aquí para poner en perspectiva las clases de complejidad