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:
Relación entre las principales clases de complejidad 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
Problema de decisión Archivo:solidLine.png Archivo:solidLine.png Lenguaje recursivo enumerable Problema indecidible Archivo:solidLine.png Problema decidible Archivo:solidLine.png ESPACIOEXP Archivo:dottedLine.png TIEMPOEXP Archivo:dottedLine.png ESPACIOP Archivo:solidLine.png Archivo:solidLine.png Archivo:dottedLine.png Archivo:dottedLine.png Archivo:dottedLine.png Archivo:dottedLine.png Gramática sensible al contexto Archivo:solidLine.png Archivo:dottedLine.png Archivo:dottedLine.png Archivo:dottedLine.png ESPACIOP-completo Archivo:solidLine.png Archivo:solidLine.png Archivo:dottedLine.png Archivo:dottedLine.png Archivo:dottedLine.png Archivo:solidLine.png Archivo:solidLine.png Co-NP Archivo:dottedLine.png NP Archivo:solidLine.png Archivo:solidLine.png Archivo:dottedLine.png Archivo:dottedLine.png Archivo:dottedLine.png Archivo:dottedLine.png Archivo:solidLine.png Archivo:solidLine.png Archivo:dottedLine.png BPP BQP NP-completo Archivo:solidLine.png Archivo:solidLine.png Archivo:dottedLine.png Archivo:dottedLine.png Archivo:dottedLine.png Archivo:solidLine.png Archivo:solidLine.png P Archivo:solidLine.png Archivo:solidLine.png Archivo:dottedLine.png Archivo:dottedLine.png Archivo:solidLine.png NC P-completo Archivo:solidLine.png Archivo:solidLine.png Gramática libre de contexto Archivo:solidLine.png Gramática regular
Ejemplos La clase NP es el conjunto de problemas de decisión que pueden ser resueltos en tiempo polinómico por una máquina de Turing no determinista. La clase PSPACE es el conjunto de problemas de decisión que pueden ser resueltos por una máquina de Turing determinista en espacio polinómico.
Véase también Anexo:Clases de complejidad Cota superior asintótica