Pregunta P! = NP

Question

No es una pregunta de programación 'pura', pero como está profundamente involucrada en la teoría de la programación, pensé que sería mejor preguntar aquí.

En relación con el problema P NP, este extracto de http://en.wikipedia.org/wiki/P_versus_NP_problem: "En esencia, la pregunta P = NP? Pregunta: Supongamos que las respuestas afirmativas a sí o no se pueden verificar rápidamente. calculado rápidamente? "

Me pregunto, ¿cómo es la velocidad de verificar una respuesta relacionada con la velocidad de generación de una solución?

Answer 1

Básicamente, en el conjunto de NP, o tiempo polinomio no determinista, problemas, la respuesta se puede verificar en tiempo polinomial. La pregunta es si todos estos problemas pueden ser determinado en tiempo polinomial.

Si P = NP es verdadero, y tales algoritmos se descubren muchos problemas que son difíciles de resolver pero fáciles de verificar, la solución, como las pruebas, se vuelve tan fácil de resolver como de verificar.

Answer 2

Puede o no estar relacionado.

Las personas se preocupan por los problemas de NP porque queremos solucionarlas de forma rápida y constante, pero hasta ahora no hemos encontrado la forma de solucionarlas de manera rápida. Queremos saber si hay una forma rápida de resolverlos o si debemos dejar de intentarlo.

Answer 3

Supongamos que el mago me ofrece una solución a un problema "difícil", y puedo verificar fácilmente si esta solución es correcta o no. PERO, ¿puedo calcular esta solución yo mismo fácilmente? (tiempo de polinomio)

Esta es exactamente la pregunta.

Answer 4

Supongamos que tiene un tremendo paralelismo, por mucho que desee. Luego, podría generar simultáneamente todas las soluciones posibles, verificar cuáles de ellas eran correctas y generar una solución correcta. En presencia de un paralelismo infinito, este es un método para generar una solución. El conjunto de problemas en NP son aquellos para los que este procedimiento funcionaría rápidamente, porque el único paso computacional interesante que está realizando es verificar si las soluciones son correctas, y esto se puede hacer de manera eficiente ante problemas en NP. Tenga en cuenta que para algunos otros problemas, incluso este paralelismo no nos permitirá encontrar soluciones rápidamente, ya que requiere que las soluciones de verificación sean fáciles.

Pero no tenemos un paralelismo infinito. ¿Podemos de alguna manera simularlo, con solo una cantidad polinómica de sobrecarga? Si es así, podríamos imaginarnos ejecutando el procedimiento anterior y encontrando soluciones de manera eficiente para cada problema para el cual la verificación fue fácil. Esta es la pregunta P vs. NP.

Intuitivamente, parece claro que la respuesta es "no" (es decir, P! = NP). ¿Cómo podríamos simular un paralelismo infinito? Esto es lo que casi todos los expertos creen. Pero es un misterio cómo probarlo, y uno que vale $ 1,000,000 en premios en efectivo.

Answer 5

This problem has been solved today!

(Posiblemente).

Answer 6

Ya sea que estén relacionados o no, es una de "Problemas del Milenio" de la Fundación Claypool, y que van a dar un millón de dólares a alguien que proporciona una prueba adecuada que aguantar bajo unos años de intenso examen.

Los tipos de preguntas están más relacionados de lo que parecen, ya que otra definición de problema de NP es aquella que se puede resolver de manera eficiente con una computadora arbitrariamente paralela.

Una cosa que realmente le interesa a la gente es la falta de una prueba. Hay pruebas para preguntas similares, pero no esta. Eso intriga a la gente, especialmente a los matemáticos, ya que una prueba es probable que brinde mucha información sobre otras cosas. Ese es aparentemente el caso de la prueba de Perelman de la conjetura de Poincaré, otro de los problemas del milenio.

Otro problema es el impacto que esto podría tener. En este momento, pocas personas creen que hay un método eficiente para resolver problemas NP-completos, por lo que un descubrimiento de que P! = NP tendría poco impacto práctico. Un descubrimiento de una forma eficiente de resolver problemas NP-completos revolucionaría una gran cantidad de ciencias de la computación. Haría mucho más fácil y destruiría la criptografía tal como la conocemos haciendo que el descifrado sea fácil.

Answer 7

P es la clase de todos los idiomas que se pueden calcular en tiempo polinomial por una máquina determinante de Turing. Una computadora moderna es muy parecida a una máquina determinante de Turing, excepto que una máquina de Turing esencialmente tiene memoria infinita. Esta distinción generalmente se ignora para propósitos prácticos.

NP es la clase de todos los idiomas que se pueden calcular en tiempo polinomial mediante un no-Turbina determinista. Una máquina de Turing no determinista no se corresponde con ningún dispositivo del mundo real.

Es un hecho básico de complejidad computacional que NP es equivalente a la clase de idiomas cuyos problemas de verificación están en P. De hecho, NP se define a veces como esta clase; las dos definiciones son intercambiables, y la definición de verificación tiene el beneficio de una relevancia directa para las computadoras deterministas de tipo máquina de Turing en el mundo real.

Así NP es la clase de problemas que son verificables en tiempo polisemático en una máquina "real" y se pueden resolver en tiempo de polietización en una máquina teórica muy similar. Por lo tanto, las cuestiones de solvencia y verificabilidad están relacionadas.

Ahora, la mayoría de los informáticos creen que P y NP son no equivalente; es decir, que existen lenguajes computables en tiempo de polietización por una máquina de Turing no determinista pero no por una máquina de Turing determinista, o equivalentemente que no son solucionables en tiempo de tiempo por una máquina de Turing determinista pero cuyas soluciones se pueden verificar en tiempo de polietileno por una máquina determinista de Turing.

Answer 8

Sin embargo, aquí no hay una relación directa. Puede haber una sensación intuitiva de que verificar una respuesta es más fácil que generar una respuesta como parte de cualquier generación para asegurar que la respuesta sea correcta. Por lo tanto, uno podría adoptar un enfoque de fuerza bruta para probar diferentes soluciones, pero esto tiende a llevar a complejidades exponenciales que están más allá de P, o eso es lo que recuerdo de la clase de Complejidad hace años.