Hola

La teoría de la complejidad
Trata de clasificar los problemas que pueden, o no pueden ser resueltos con una cantidad determinada de recursos. A su vez, la imposición de restricciones sobre estos recursos, es lo que la distingue de la teoría de la computabilidad, la cual se preocupa por qué tipo de problemas pueden ser resueltos de manera algorítmica.
Una clase de complejidad es un conjunto deproblemas que poseen la misma complejidad computacional.
Definiendo clases de complejidad
Las clases de complejidad más sencillas se definen teniendo en cuenta factores como:
El tipo de problema computacional: Los problemas más comúnmente utilizados son los problemas de decisión, pero las clases de complejidad se pueden definir para otros tipos de problemas.
El modelo de cómputo: El modelo decómputo más común es la Máquina de Turing determinista, pero muchas clases de complejidad se basan en Máquinas de Turing no deterministas, Máquinas de Turing cuánticas, etc.
El recurso (o recursos) que está(n) siendo acotado(s) y la(s) cota(s): Estas dos propiedades usualmente se utilizan juntas, por ejemplo, "tiempo polinomial", "espacio logarítmico", "profundidad constante", etc.
Máquinas deTuring deterministas y la clase P
La clase P contiene a aquellos problemas que son solubles en tiempo polinómico por una máquina de Turing determinista.5
Para la definición anterior se ha fijado el modelo de cómputo: la Máquina de Turing determinista. Existen distintas variantes de la Máquina de Turing y es conocido que la más débil de ellas puede simular a la más fuerte, adicionando a lo sumoun tiempo polinómico. En las décadas posteriores a la Tesis de Church-Turing surgieron otros modelos de cómputo, y se pudo mostrar que la Máquina de Turing también podía simularlos a lo sumo adicionando también un tiempo polinómico. Por tanto, la clase análoga a P para dichos modelos no es mayor que la clase P para el modelo de cómputo de la máquina de Turing.
La clase P juega un papel importanteen la teoría de la complejidad computacional debido a que:
1. P es invariante para todos los modelos de cómputo que son polinómicamente equivalentes a la Máquina de Turing determinista.
2. A grandes rasgos, P corresponde a la clase de problemas que, de manera realista, son solubles en una computadora.



Computación no determinista y la clase NP
Muchas veces podemos evitar utilizar lafuerza bruta en los problemas para obtener soluciones en tiempo polinómico. Sin embargo, para algunos problemas esto no ha podido lograrse, es decir, no se conocen algoritmos que los resuelvan en tiempo polinómico. Quizás estos problemas tengan algoritmos en tiempo polinomial que se basan en principios por ahora desconocidos, o quizás estos problemas no pueden ser resueltos en tiempo polinómico, debidoa que son "inherentemente difíciles".
La clase de complejidad NP consta de los problemas "verificables" en tiempo polinómico. Por verificable se entiende a un problema tal que dado un certificado de solución (candidato a solución), se puede verificar que dicho certificado es correcto en un tiempo polinómico en el tamaño de la entrada. A los problemas en la clase NP usualmente se lesllama problemas NP.6
El término NP proviene de no determinista en tiempo polinómico y se deriva de un caracterización alternativa de esta clase, donde se utilizan Máquinas de Turing no deterministas. Informalmente, se puede definir la clase NP en términos de un algoritmo no determinista (recordar la equivalencia entre algoritmo y Máquina de Turing).
El algoritmo mencionado está compuesto por 2 etapasseparadas. Dada una instancia del problema I, la primera etapa simplemente "adivina" un candidato a solución S. Entonces, la etapa de verificación recibe como entrada a I y a S, y procede a realizar el cómputo de una manera determinista, finalmente deteniéndose con la respuesta "sí", o con la respuesta "no", o sigue computando sin detenerse.
Al igual que la clase P, la clase NP es insensible a la...