¿Qué es fácil para una computadora y qué es casi imposible? Estas preguntas están en el corazón del tema de la complejidad computacional. Te presentamos un mapa de este paisaje.
Las diferentes clases de complejidad clasifican las tareas en forma jerárquica. Una clase puede contener todas las tareas de otra, además de tareas que requieren recursos informáticos adicionales.¿Cuál es la dificultad fundamental de la tarea? Esta es la formulación de la tarea básica de los informáticos que intentan clasificar las tareas de acuerdo con lo que se llama.
clases de dificultad Estos son grupos que contienen todas las tareas computacionales que no requieren más que una cantidad fija de recursos computacionales, como el tiempo o la memoria. Tomemos un ejemplo simple con un número grande como 123 456 789 001. Uno puede preguntarse: ¿es un número primo, uno que se divide solo por 1 y por sí mismo? Los informáticos pueden responderlo con algoritmos rápidos, de modo que no comiencen a reducir la velocidad en números arbitrariamente grandes. En nuestro caso, resulta que este número no es primo. Entonces podemos hacer la pregunta: ¿cuáles son sus factores primos? Pero no hay un algoritmo rápido para responderlo, solo si usa una computadora cuántica. Por lo tanto, los informáticos creen que estas dos tareas pertenecen a diferentes clases de complejidad.
Hay muchas clases diferentes de dificultad, aunque en la mayoría de los casos los investigadores no pudieron demostrar que una clase es claramente diferente de las demás. La evidencia de diferencias entre clases es una de las tareas más difíciles e importantes en esta área.
La diferencia entre clases puede ser apenas distinguible u obvia, y es bastante difícil entender bien todas las clases. Por lo tanto, hemos compilado esta guía de las siete clases de dificultad más fundamentales. Y sí, ya no confundirá a BPP y BQP.
P
Denota : tiempo polinómico
Breve descripción : todas las tareas que una computadora clásica (no cuántica) puede resolver fácilmente.
Descripción exacta : los algoritmos de clase P deberían dejar de funcionar y dar la respuesta correcta en no más de tiempo n
c , donde n es la longitud de los datos de entrada, c es una constante.
Tareas Típicas :
- ¿Es el número primo?
- ¿Cuál es el camino más corto entre dos puntos?
Lo que a los investigadores les gustaría saber : ¿Coincide P con NP? La coincidencia revolucionaría la informática y haría que la mayoría de los sistemas criptográficos carezcan de sentido (pero casi nadie cree esto).
NP
Denota : tiempo polinómico no determinista
Breve descripción : todas las tareas que una computadora clásica puede verificar fácilmente si hay una solución.
Descripción exacta : el problema cae en la clase NP cuando, si la respuesta es sí, hay una breve prueba de la exactitud de la respuesta. Si la entrada es una cadena X, y necesita decidir si la respuesta coincide con "sí", entonces una breve prueba será otra cadena, Y, que se puede usar para verificar la respuesta correcta "sí" en tiempo polinómico. (Y a veces se le llama “testigo corto”: todas las tareas de NP tienen testigos cortos, gracias a los cuales se pueden verificar).
Tareas Típicas :
- La tarea de hacer clic . Imagine un gráfico con aristas y vértices; por ejemplo, los vértices indican usuarios de la red social y el borde indica que son "amigos". Una camarilla es un subconjunto de este gráfico en el que todas las personas son amigas entre sí. Puede hacer las siguientes preguntas sobre el gráfico: ¿hay un clic de 20 personas en él? 50 personas? 100? Encontrar una camarilla es una tarea completa de NP , es decir, su complejidad es la más alta de todas las tareas de NP. Pero tener una respuesta potencial (un subconjunto de 50 nodos que puede o no ser un clic) es fácil de verificar.
- La tarea del vendedor . Dado un conjunto de ciudades con distancias entre dos pares, ¿hay alguna manera de recorrer todas las ciudades, conduciendo a menos de una cierta distancia? Por ejemplo, ¿puede un vendedor viajar por todas las capitales de los Estados Unidos con menos de 11,000 millas?
Lo que a los investigadores les gustaría saber: P = NP? Especialistas en informática y no se acercaron a resolver este problema.
PH
Denota : jerarquía polinómica
Descripción breve : PH es una generalización de NP. Contiene todas las tareas que se pueden obtener comenzando con una tarea de NP e imponiendo niveles adicionales de dificultad.
Descripción exacta : PH contiene tareas con diferentes "cuantificadores" que complican estas tareas. Un ejemplo de un problema con diferentes cuantificadores: si se nos da X, ¿existe Y de tal manera que para cada Z exista W para el cual R está satisfecho? Cuantos más cuantificadores haya en el problema, más complicado será y mayor será la jerarquía polinómica.
Una tarea típica es determinar si realmente hay un clic del tamaño 50 y si no hay un clic del tamaño 51.
Lo que los investigadores desearían saber : nadie ha podido demostrar que PH sea diferente de P. Este problema es equivalente a la igualdad de P y NP, porque si de repente resulta que P = NP, todos los PH se reducirán a P (P = PH).
PSPACE
Denota : restricción de espacio polinomial
Breve descripción : PSPACE contiene todas las tareas que se pueden resolver con una cantidad razonable de memoria.
Descripción exacta : al resolver tareas de PSPACE, ya no te preocupas por el tiempo, solo te preocupa la cantidad de memoria que se requiere para que el algoritmo funcione. Los científicos informáticos han demostrado que PSPACE contiene un PH que contiene NP que contiene P.
Tarea típica : todas las tareas de P, NP y PH están contenidas en PSPACE.
Lo que a los investigadores les gustaría saber : ¿PSPACE es diferente de P?
Bqp
Denota : tiempo polinómico cuántico con limitación de probabilidad de error
Breve descripción : todas las tareas que se pueden resolver fácilmente en una computadora cuántica.
Descripción exacta : todas las tareas que se pueden resolver en una computadora cuántica en tiempo polinómico.
Problema típico : encontrar factores primos de un número entero.
Lo que a los investigadores les gustaría saber : hasta ahora, se ha demostrado que BQP está contenido en PSPACE y que BQP contiene P. Los investigadores no saben si BQP está contenido en NP, pero creen que estas dos clases no se pueden comparar: hay tareas que forman parte de NP, pero no en BQP, y viceversa.
EXPTIME
Denota : tiempo exponencial
Breve descripción : todas las tareas que se pueden resolver en tiempo exponencial en una computadora clásica.
Descripción exacta : EXP contiene todas las clases anteriores: P, NP, PH, PSPACE y BQP. Los investigadores demostraron que es diferente de P: descubrieron tareas que son parte de EXP y no parte de P.
Tarea típica : generalización de juegos como ajedrez y damas. Si un tablero de ajedrez puede ser de cualquier tamaño, la tarea de determinar si uno de los jugadores tiene una ventaja se convierte en tarea de EXP.
Lo que a los investigadores les gustaría saber : les gustaría probar que PSPACE no contiene EXP. Creen que hay tareas que son parte de EXP pero no parte de PSPACE, porque a veces lleva mucho tiempo resolver una tarea desde EXP. Los investigadores saben cómo separar EXP y P.
BPP
Denota : tiempo polinómico con limitación de probabilidad de error
Breve descripción : tareas que pueden resolverse rápidamente utilizando algoritmos que utilizan la aleatoriedad.
Descripción exacta : BPP es lo mismo que P, con la diferencia de que el algoritmo puede incluir pasos en los que las decisiones se toman al azar. Los algoritmos en BPP necesitan dar las respuestas correctas con una probabilidad cercana a 1.
Tarea típica : tiene dos fórmulas diferentes que dan polinomios con muchas variables. ¿Estas fórmulas calculan el mismo polinomio? Esta es la tarea de verificar la identidad polinómica.
Lo que a los investigadores les gustaría saber : ¿Son iguales BPP y P. Si son iguales, entonces cualquier algoritmo con aleatoriedad podría eliminarse de la aleatoriedad. Creen que es así, que para cada problema para el que existe un algoritmo aleatorio efectivo, existe un algoritmo determinista efectivo, pero aún no han podido probarlo.