algorithm - tiempo - Explicando la teoría de la complejidad computacional
tiempo polinomial (10)
Aquí hay algunos enlaces sobre el tema:
Si está familiarizado con la idea de establecer la cardinalidad, es decir, la cantidad de elementos en un conjunto, entonces podría verse la pregunta como P, que representa la cardinalidad de los números enteros, mientras que NP es un misterio: ¿es igual o más grande? la cardinalidad de todos los números reales?
Se dice que el verdadero dominio de un tema se logra cuando puedes explicarlo simplemente. Desafortunadamente, como Ingeniero Electrónico, carezco de algunos de los aspectos más formales de la informática.
Teniendo en cuenta que hay algunos antecedentes en matemáticas, ¿cómo explicarías la teoría de la complejidad computacional a los ingenuos? ¿Dónde empezar a entrar en este tema tan importante de CS? Entiendo algunos de los conceptos involucrados, pero me falta una visión general que me permita entrar en detalles.
Editar: la notación de Big O es clara para mí. Lo que estoy buscando más es una explicación de lo que es esta pregunta P = NP. ¿Qué es un problema P? ¿Qué es NP? ¿Qué es un NP-Hard?
Edición 2: ¡Algunas respuestas realmente geniales! ahora muchas cosas tienen más sentido. El problema es que a veces wikipedia se escribe como si el lector ya entendiera todos los conceptos involucrados. Ahora, con esta rápida visión general, muchos de estos artículos tienen mucho más sentido
Dependiendo de cuánto tiempo tenga, tal vez sería mejor comenzar en DFA, NDFA, y luego demostrar que son equivalentes. Luego entienden ND vs. D, y entenderán las expresiones regulares mucho mejor como un buen efecto secundario.
En informática no es suficiente para poder resolver un problema. Tiene que ser solucionable en un tiempo razonable. Entonces, mientras que en matemáticas puras se obtiene una ecuación, en CS debe refinar esa ecuación para que pueda resolver un problema en un tiempo razonable.
Esa es la forma más simple en que puedo pensar ponerlo, que puede ser demasiado simple para tus propósitos.
Hoooo, flashback doctoral comp. De acuerdo, 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, realmente): determinista y no determinista. Una computadora determinista es la computadora regular en la que siempre estamos pensando; una computadora no determinista es tal como estamos acostumbrados, excepto que tiene un paralelismo ilimitado, de modo que cada vez que se llega a una sucursal, se genera un nuevo "proceso" y se examinan 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 polinomial conocido para obtener esa respuesta. Un problema de decisión está en NP si hay un algoritmo conocido de tiempo polinomial 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 simplemente no se da el trabajo de bifurcar otro proceso, y actúa igual que 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 nodeterminista puede llegar a una respuesta en tiempo de polietileno, y una máquina determinista puede verificar que la solución es correcta en tiempo de polis).
Pero hay algunos problemas que se sabe que están en NP para los cuales no se conoce ningún algoritmo determinista de tiempo de polietileno; en otras palabras, sabemos que están en NP, pero no saben si están en P. El ejemplo tradicional es la versión de problema de decisión del Problema de 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, él lo toma: sus clones van a la siguiente ciudad que no han visitado, y al final comparan notas y verifican si cualquiera de los clones tomó menos de x distancia.
(Entonces, los clones exponencialmente numerosos pelean por cuáles deben ser asesinados).
No se sabe si la decisión-TSP está en P: no hay una solución conocida de tiempo de espera, 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 polinomial, se dice que Q es polietápico reducible (o simplemente reducible) a P.
Un problema es NP-complete si puede probar que (1) está en NP, y (2) muestra que es polietápico reducible a un problema que ya se conoce como NP-completo. (La parte más difícil de eso fue el primer ejemplo de un problema NP-completo: eso fue hecho por Steve Cook en el Teorema de Cook ).
Entonces, realmente, lo que dice es que si alguien alguna vez encuentra una solución de tiempo de polietileno para un problema NP-completo, automáticamente obtiene uno para todos los problemas NP-completos; eso también significará que P = NP.
Un problema es NP-hard si y solo si es "al menos tan" difícil como un problema NP-completo. El problema más común de los Viajeros Viajeros al encontrar la ruta más corta es NP-hard, no estrictamente NP-complete.
Mi respuesta simplificada sería: "La complejidad computacional es el análisis de cuánto más difícil se vuelve un problema cuando se agregan más elementos".
En esa oración, la palabra "más difícil" es deliberadamente vaga porque podría referirse al tiempo de procesamiento o al uso de la memoria.
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 comprobando cada una.
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) muestra que es polietápico reducible a un problema que ya se conoce como NP-completo.
Hay un error sutil con la segunda condición. En realidad, lo que necesita probar es que un problema conocido de NP-complete (por ejemplo, Y ) es el tiempo polinomial reducible a este problema (llamémoslo problema X ).
El razonamiento detrás de esta forma de prueba es que si pudiera reducir un problema NP -Complete a este problema y de alguna manera lograra resolver este problema en tiempo de polietileno, entonces también ha logrado encontrar una solución de tiempo de polietileno para el NP - Completar el problema, que sería una cosa notable (si no imposible), desde entonces habrá logrado resolver el problema de P = NP de larga data.
Otra forma de ver esta prueba es considerarla usando la técnica de prueba contra-positiva, que esencialmente establece que si Y -> X , entonces ~ X -> ~ Y. En otras palabras, no poder resolver Y en tiempo polinomial no es posible significa que tampoco se debe resolver X en tiempo de polisemia. Por otro lado, si pudieras resolver X en tiempo de polietileno, entonces podrías resolver Y en tiempo de polietileno también. Además, puede resolver todos los problemas que se reducen a Y en tiempo de polietileno y por transitividad.
Espero que mi explicación anterior sea lo suficientemente clara. Una buena fuente es el Capítulo 8 del Diseño de Algoritmos de Kleinberg y Tardos o el Capítulo 34 de Cormen et al.
Desafortunadamente, los mejores dos libros que conozco ( Garey y Johnson y Hopcroft y Ullman ) ambos comienzan en el nivel de las matemáticas orientadas a la prueba de postgrado. Esto es casi seguro necesario, ya que todo el tema es muy fácil de malinterpretar o caracterizar erróneamente. Jeff casi se muerde las orejas cuando intenta acercarse al asunto en un tono demasiado jovial.
Quizás la mejor manera es simplemente hacer un montón de trabajo práctico con notación de gran O usando muchos ejemplos y ejercicios . Ver también esta respuesta . Sin embargo, tenga en cuenta que esto no es exactamente lo mismo: algoritmos individuales pueden ser descritos por asíntotas, pero decir que un problema es de cierta complejidad es una afirmación sobre cada algoritmo posible para ello. ¡Por eso las pruebas son tan complicadas!
La Introducción a la Teoría de la Computación de Michael Sipser es un gran libro, y es muy legible. Otro gran recurso es el curso Great Ideas in Theoretical Computer Science de Scott Aaronson.
El formalismo que se usa 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 de caracteres - cuya respuesta es Sí. Hay una noción formal de lo que es una "computadora" (máquina de Turing), y un problema está en P si hay un algoritmo de tiempo polinomial para decidir ese problema (dada una cadena de entrada, digamos Sí o No) en una máquina de Turing.
Un problema está en NP si es seleccionable en tiempo polinomial, es decir, si para las entradas donde la respuesta es Sí, hay un certificado (de tamaño de polinomio) que permite verificar que la respuesta es Sí en tiempo polinomial. [Por ejemplo, dado un ciclo de Hamilton como certificado, obviamente puede verificar que sea uno).
No dice nada sobre cómo encontrar ese certificado. Obviamente, puedes probar "todos los certificados posibles" pero eso puede tomar un tiempo exponencial; no está claro si siempre tendrá que tomar más tiempo de 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 completo en informática?
Pero en realidad, todo esto probablemente sea vago para usted; vale la pena tomarse el tiempo para leer, por ejemplo, el libro de Sipser. Es una hermosa teoría.