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:
el conjunto de los problemas de decisión que pueden ser resueltos por una máquina M utilizando O(f(n)) del recurso R (donde n es el tamaño de la entrada).
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
Escribe un comentario o lo que quieras sobre Clase de complejidad (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)