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).
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
clase, complejidad, teoría, complejidad, computacional, clase, complejidad, conjunto, problemas, decisión, complejidad, relacionada, clase, complejidad, tiene, definición, forma, conjunto, problemas, decisión, pueden, resueltos, máquina, utilizando, recurso, d. En teoria de la complejidad computacional una clase de complejidad es un conjunto de problemas de decision de complejidad relacionada Una clase de complejidad tiene una definicion de la forma el conjunto de los problemas de decision que pueden ser resueltos por una maquina M utilizando O f n del recurso R donde n es el tamano de la entrada Relacion entre las principales clases de complejidad EditarLa siguiente tabla muestra algunas de las clases de problemas o lenguajes o gramaticas que se consideran en teoria de la complejidad computacional Cuando la clase X es un subconjunto estricto de Y X aparece en la tabla bajo Y con una linea solida uniendolos Cuando es subconjunto pero no se sabe si es estricto la linea es cortada y gris Tecnicamente hablando el corte entre problemas decidibles e indecidibles es tema de la Teoria de la computabilidad pero resulta interesante mencionarlos aqui para poner en perspectiva las clases de complejidad Problema de decision Lenguaje recursivo enumerable Problema indecidible Problema decidible ESPACIOEXP TIEMPOEXP ESPACIOP Gramatica sensitiva al contexto ESPACIOP completo Co NP NP BPP BQP NP completo P NC P completo Gramatica libre de contexto Gramatica regularEjemplos Editar La clase NP es el conjunto de problemas de decision que pueden ser resueltos en tiempo polinomico por una maquina de Turing no determinista La clase PSPACE es el conjunto de problemas de decision que pueden ser resueltos por una maquina de Turing determinista en espacio polinomico Vease tambien EditarAnexo Clases de complejidad Cota superior asintotica Datos Q908207Obtenido de https es wikipedia org w index php title Clase de complejidad amp oldid 124357243, wikipedia, wiki, leyendo, leer, libro, biblioteca,
