Explicando la teoría de la complejidad computacional
https://stackoverflow.com/questions/308213
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Suponiendo algunos antecedentes en matemáticas, ¿cómo le darías una visión general de la teoría de la complejidad computacional a los ingenuos?
Estoy buscando una explicación de la pregunta P = NP. ¿Qué es p? ¿Qué es NP? ¿Qué es un NP-Hard?
A veces Wikipedia se escribe como si el lector ya entendiera todos los conceptos involucrados.
Solución
Hoooo, flashback doctoral comp. Bien, aquí va.
Comenzamos con la idea de un problema de decisión, un problema para el cual un algoritmo siempre puede responder "sí". o "no". También necesitamos la idea de dos modelos de computadora (máquina de Turing, en realidad): determinista y no determinista. Una computadora determinista es la computadora normal en la que siempre estamos pensando; una computadora no determinista es una que es igual a la que estamos acostumbrados, excepto que tiene un paralelismo ilimitado, por lo que cada vez que llegas a una rama, engendras un nuevo "proceso". y examinar ambos lados. Como dijo Yogi Berra, cuando llegas a una bifurcación en el camino, debes tomarla.
Un problema de decisión está en P si hay un algoritmo de tiempo polinómico conocido para obtener esa respuesta. Un problema de decisión está en NP si hay un algoritmo de tiempo polinómico conocido para que una máquina no determinista obtenga la respuesta.
Los problemas que se sabe que están en P están trivialmente en NP --- la máquina no determinista nunca se preocupa por bifurcar otro proceso, y actúa como uno determinista. Hay problemas que se sabe que no están ni en P ni en NP; Un ejemplo simple es enumerar todos los vectores de bits de longitud n. No importa qué, eso toma 2 n pasos.
(Estrictamente, un problema de decisión está en NP si una máquina nodo-terminal puede llegar a una respuesta en tiempo poli, y una máquina determinista puede verificar que la solución es correcta en tiempo poli.)
Pero hay algunos problemas que se sabe que están en NP para los cuales no se conoce ningún algoritmo determinista de poli-tiempo; en otras palabras, sabemos que están en NP, pero no sabemos si están en P. El ejemplo tradicional es la versión de problema de decisión del problema del vendedor ambulante (decisión-TSP): dadas las ciudades y las distancias, ¿Hay una ruta que cubra todas las ciudades, volviendo al punto de partida, en menos de x distancia? Es fácil en una máquina no determinista, porque cada vez que el vendedor ambulante no determinista llega a una bifurcación en el camino, lo toma: sus clones se dirigen a la siguiente ciudad que no han visitado, y al final comparan notas y ven si cualquiera de los clones tomó menos de x distancia.
(Entonces, los exponencialmente muchos clones luchan por cuáles deben ser asesinados).
No se sabe si decision-TSP está en P: no se conoce una solución de poli-tiempo, pero no hay pruebas de que tal solución no exista.
Ahora, un concepto más: dados los problemas de decisión P y Q, si un algoritmo puede transformar una solución para P en una solución para Q en tiempo polinómico, se dice que Q es reducible en tiempo polivinílico (o simplemente reducible) a P.
Un problema es NP-completo si puede probar que (1) está en NP, y (2) muestra que es poli-tiempo reducible a un problema que ya se sabe que es NP-completo. (La parte difícil de eso fue proporcionar el primer ejemplo de un problema de NP completo: eso fue hecho por Steve Cook en Teorema de Cook .)
Entonces, realmente, lo que dice es que si alguien alguna vez encuentra una solución poli-tiempo para un problema NP-complete, automáticamente tiene una para all los problemas NP-complete; eso también significará que P = NP.
Un problema es NP-hard si y solo si es '' al menos como '' difícil como un problema NP-completo. El problema de vendedor ambulante más convencional para encontrar la ruta más corta es NP-hard, no estrictamente NP-complete.
Otros consejos
Michael Sipser 's Introducción a la teoría de la computación es un gran libro y es muy legible. Otro recurso excelente es genial de Scott Aaronson Curso de Ideas en Informática Teórica .
El formalismo que se utiliza es mirar los problemas de decisión (problemas con una respuesta Sí / No, por ejemplo, "¿este gráfico tiene un ciclo hamiltoniano") como "idiomas". - conjuntos de cadenas - entradas para las cuales la respuesta es Sí. Existe una noción formal de lo que una "computadora" es (máquina de Turing), y hay un problema en P si hay un algoritmo de tiempo polinómico para decidir ese problema (dada una cadena de entrada, diga Sí o No) en una máquina de Turing.
Un problema está en NP si es comprobable en tiempo polinómico, es decir, si para las entradas donde la respuesta es Sí, hay un certificado (de tamaño polinómico) dado que puede verificar que el la respuesta es sí en tiempo polinómico. [P.ej. dado un ciclo hamiltoniano como certificado, obviamente puede verificar que sea uno.]
No dice nada acerca de cómo encontrar ese certificado. Obviamente, puede probar "todos los certificados posibles" pero eso puede llevar un tiempo exponencial; no está claro si siempre tendrá tomar más tiempo que el polinomio para decidir Sí o No; Esta es la pregunta P vs NP.
Un problema es NP-hard si ser capaz de resolver ese problema significa ser capaz de resolver todos los problemas en NP.
También vea esta pregunta: ¿Qué es un NP-complete en informática?
Pero en realidad, todo esto probablemente solo sea vago para usted; vale la pena tomarse el tiempo de leer, p. El libro de Sipser. Es una teoría hermosa.
Este es un comentario en la publicación de Charlie.
Un problema es NP-complete si puede probar que (1) está en NP, y (2) demuestre que es poli-tiempo reducible a un problema ya conocido por ser NP-complete.
Hay un error sutil con la segunda condición. En realidad, lo que necesita probar es que un problema NP-completo conocido (por ejemplo, Y ) es reducible en tiempo polinómico a este problema (llamémoslo problema X ).
El razonamiento detrás de esta forma de prueba es que si pudieras reducir un problema NP -Completo a este problema y de alguna manera lograr resolver este problema en tiempo polivinílico, entonces también has tenido éxito en encontrar una solución de tiempo múltiple para el problema completo de NP , que sería una cosa notable (si no imposible), desde entonces habrá logrado resolver el antiguo P = NP problema.
Otra forma de ver esta prueba es considerarla utilizando la técnica de prueba contra positiva, que esencialmente establece que si Y - > X , luego ~ X - > ~ Y . En otras palabras, no ser capaz de resolver Y en tiempo polinómico no es posible significa no resolver X en tiempo polivinílico tampoco. Por otro lado, si pudieras resolver X en poli-tiempo, entonces también podrías resolver Y en poli-tiempo. Además, también podría resolver todos los problemas que se reducen a Y en el tiempo polivinílico mediante transitividad.
Espero que mi explicación anterior sea lo suficientemente clara. Una buena fuente es el Capítulo 8 de Algorithm Design de Kleinberg y Tardos o el Capítulo 34 de Cormen et al.
Desafortunadamente, los dos mejores libros que conozco ( Garey y Johnson y Hopcroft y Ullman ) ambos comienzan en el nivel de graduados orientados a pruebas matemáticas. Esto es casi seguro necesario, ya que todo el problema es muy fácil de entender o caracterizar erróneamente. Jeff casi se mordió las orejas cuando intentó abordar el asunto también folk / jokey un tono.
Quizás la mejor manera es simplemente hacer mucho trabajo práctico con notación big-O usando muchos ejemplos y ejercicios . Consulte también esta respuesta . Sin embargo, tenga en cuenta que esto no es exactamente lo mismo: los algoritmos individuales pueden describirse mediante asíntotas, pero decir que un problema es de cierta complejidad es una declaración sobre cada algoritmo posible por ello. ¡Es por eso que las pruebas son tan complicadas!
Recuerdo "Complejidad computacional" de Papadimitriou (espero haber escrito bien el nombre) como un buen libro
muy simplificado: un problema es NP-hard si la única forma de resolverlo es enumerando todas las respuestas posibles y verificando cada una.
Aquí hay algunos enlaces sobre el tema:
Si está familiarizado con la idea de la cardinalidad de conjunto, es decir, el número de elementos en un conjunto, entonces se podría ver la pregunta como P que representa la cardinalidad de los números enteros, mientras que NP es un misterio: ¿es lo mismo o es ¿Es más grande como la cardinalidad de todos los números reales?
Mi respuesta simplificada sería: "La complejidad computacional es el análisis de cuánto más difícil se vuelve un problema cuando agrega más elementos".
En esa oración, la palabra "más difícil" es deliberadamente vago porque podría referirse al tiempo de procesamiento o al uso de memoria.
En informática no es suficiente para poder resolver un problema. Tiene que ser solucionable en un tiempo razonable. Entonces, mientras que en matemática pura se te ocurre una ecuación, en CS debes refinar esa ecuación para que puedas resolver un problema en un tiempo razonable.
Esa es la forma más simple que puedo pensar para decirlo, que puede ser demasiado simple para sus propósitos.
Dependiendo de cuánto tiempo tenga, quizás sería mejor comenzar en DFA, NDFA y luego demostrar que son equivalentes. Luego entienden ND frente a D, y comprenderán las expresiones regulares mucho mejor como un agradable efecto secundario.
