¿Qué es una explicación intuitiva de P = NP?

No estoy completamente satisfecho con las respuestas existentes, así que lo intentaré. Vea el final para notas técnicas.

P (significa “tiempo polinomial”) es, aproximadamente, la clase de problemas que una computadora puede resolver de manera eficiente. NP (sinónimo de “tiempo polinomial no determinista”) es, más o menos, la clase de problemas para los cuales una supuesta solución puede ser verificada eficientemente. Entonces, la pregunta P? = NP significa, aproximadamente, que si una computadora puede verificar fácilmente la solución a un problema, ¿también puede encontrar una solución eficiente? Por supuesto, cualquier problema en P está en NP: si puede resolver el problema usted mismo, simplemente haga eso y compare las respuestas. Entonces, algunos problemas de NP son fáciles.

Sudoku es un buen ejemplo de un problema de NP. Es fácil verificar la solución a un rompecabezas de Sudoku. Incluso si la cuadrícula fuera 100 × 100 o 10000 × 10000, una computadora podría verificar fácilmente que cada número esté entre 1 y 9/100/10000, y que cada número aparezca exactamente una vez en cada fila, columna y cuadro. ¿Pero es posible escribir un programa de computadora que resuelva cualquier problema de Sudoku, incluso para una grilla grande?

Puede decir algo acerca de la respuesta aquí usando algo llamado “dureza NP”. Si un problema es NP-hard, entonces, en cierto sentido, es al menos tan difícil como cualquier problema en NP. Esto es cierto para Sudoku, por ejemplo: es posible (para una computadora) convertir cualquier rompecabezas NP en un rompecabezas Sudoku (muy grande), por lo que si puede resolver Sudoku, puede resolver cualquier cosa. En otras palabras, si P! = NP, nadie puede escribir un programa que resuelva rápidamente cualquier gran rompecabezas de Sudoku. Un problema como Sudoku que está en NP y también es NP-hard se llama “NP-complete”.

Hay muchos ejemplos relevantes de problemas de NP. Planificar rutas de viaje, embalar cajas de envío, plegar proteínas, romper la criptografía, comprimir datos, casi todos los problemas de inteligencia artificial, la mayoría de los problemas de diseño … todos estos están en (alguna variante de) NP, y muchos de ellos están completos en NP.

Si P = NP, entonces las computadoras pueden resolver todos estos problemas de manera eficiente. P! = NP es decididamente menos emocionante: significa que no podemos esperar un programa general rápido de resolución de problemas. Este es el resultado esperado, y cambia el mundo menos que P = NP. Pero los informáticos esperan que las técnicas utilizadas para demostrar que P! = NP avanzarán en gran medida nuestra comprensión del campo. Además, los criptógrafos esperan demostrar eventualmente que ciertos algoritmos de cifrado son irrompibles.

OK, ahora algunas notas técnicas. Primero, la “P” y la “NP” que describí anteriormente están en realidad más cerca de las clases llamadas FP y FNP, pero FP? = FNP es más o menos equivalente a P? = NP. Además, “tiempo polinómico” no necesariamente significa “rápido” o incluso “factible”: un algoritmo que toma N ^ 100 pasos se vuelve imposible en N = 2. Sin embargo, “factible” requiere suposiciones mucho más (complicadas) sobre qué tan rápido es la computadora, cuánta memoria tiene, qué instrucciones puede llevar a cabo, etc., por lo que la mayoría de los informáticos piensan en el tiempo polinómico. Finalmente, tenga en cuenta que todo esto se aplica solo a algoritmos deterministas que resuelven todas las instancias de un problema en una computadora convencional. Puede ser (pero probablemente no) el caso de que incluso si P! = NP, podría resolver todos los problemas de NP utilizando un algoritmo aleatorio, un algoritmo que resuelve casi todas las instancias, y / o un algoritmo que utiliza computadoras cuánticas.

Por alguna razón, esta vieja pregunta apareció en mi feed.

Diría que las respuestas hasta ahora no son del todo correctas y demasiado simplistas. La imagen real es un poco más compleja y matizada.

Me gustaría aclarar algunas cosas, de una vez por todas: la verdad es que no sabemos si el problema P vs. NP es significativo para el mundo de manera directa o práctica. Una resolución del problema podría ser en términos prácticos muy significativa, pero también podría ser en términos prácticos muy insignificante. La palabra clave es podría . Permíteme elaborar …

Un algoritmo de tiempo polinómico para un problema NP-difícil

Supongamos que se descubre un algoritmo de tiempo polinómico para un problema NP-duro. Esto probaría que P = NP. Si este algoritmo hipotético es rápido, esto podría tener enormes ramificaciones prácticas, y podría significar que muchos problemas interesantes de NP-hard pueden resolverse rápidamente.

Sin embargo, una cosa importante a tener en cuenta, y algo que a menudo se pasa por alto, es que si bien se usa como un proxy para “rápido” en la teoría de la complejidad, el tiempo polinomial no necesariamente corresponde a algo que un humano consideraría eficiente o rápido o rápido

En primer lugar, existe una gran diferencia práctica entre [matemática] n \ log n [/ matemática] y [matemática] n ^ {100} [/ matemática], y sin embargo, ambos se consideran polinómicos y se consideran ” igualmente rápido “. Intente ordenar una matriz de mil millones de números aleatorios utilizando un algoritmo de tiempo [matemático] O (n \ log n) [/ matemático] y luego con un algoritmo de tiempo [matemático] O (n ^ 2) [/ matemático], y vea por usted mismo la diferencia significativa. Luego pregúntese si [math] O (n ^ 2) [/ math] es “rápido”. Ahora imagine aumentar ese exponente …

En segundo lugar, la notación big-O y, de hecho, el término “tiempo polinomial” tratan todas las constantes como “iguales”: existe una gran diferencia entre [matemáticas] n ^ 2 [/ matemáticas] y [matemáticas] 10 ^ {10 ^ { 10}} n ^ 2 [/ math], y sin embargo [math] O (n ^ 2) = O (10 ^ {10 ^ {10}} n ^ 2) [/ math], entonces desde la perspectiva de la complejidad computacional en teoría son nuevamente “igualmente rápidos”, mientras que en términos prácticos definitivamente no lo son.

Otro problema es que el problema P vs. NP solo aborda la complejidad del tiempo y no, digamos, la complejidad del espacio. Suponga que hay un algoritmo de tiempo polinómico para un problema NP-duro que desafortunadamente requiere más espacio que la cantidad de átomos en el universo. Entonces este algoritmo sería inútil, a pesar de ser polinomial.

Una prueba de existencia no constructiva

Podría muy bien demostrarse que P = NP, pero la prueba puede no exhibir explícitamente ningún algoritmo de tiempo polinómico para ningún problema NP-difícil. En este caso no habría ramificaciones prácticas inmediatas.

Una prueba de que P ≠ NP

Por otro lado, supongamos que se demuestra que P ≠ NP. ¿Significa esto necesariamente que todos los problemas NP-difíciles que surgen en la práctica son definitivamente imposiblemente difíciles al menos en términos prácticos? ¿Esto significa que deberíamos rendirnos cada vez que vemos un problema NP-difícil en la práctica?

¡No!

Por ejemplo, hay algunos algoritmos de aproximación que tienen un tiempo de ejecución polinómico y que en algunos casos dan buenas soluciones aproximadas a problemas NP-duros (como el problema del vendedor ambulante euclidiano).

¡Otro punto clave a mencionar es que el hecho de que un algoritmo tenga un tiempo de ejecución superpolinomial o exponencial en el peor de los casos no significa que sea un algoritmo malo o lento en la práctica! Considere, por ejemplo, el algoritmo simplex, que es un algoritmo importante y de uso común para la programación lineal. Simplex definitivamente no es un algoritmo de tiempo polinómico, es exponencial en el peor de los casos. Sin embargo, es ampliamente utilizado, y la mayoría de las veces en la práctica, es muy rápido. ¡A menudo es incluso preferible a los algoritmos de tiempo polinómico!

Nuevamente, vemos que la dicotomía rápido / lento no siempre corresponde en la práctica a la dicotomía de tiempo polinómico / tiempo exponencial. El primero se usa como proxy para el segundo, pero es solo eso: un proxy. No deben considerarse literalmente equivalentes.

¿Podría haber un algoritmo como simplex, que es tiempo exponencial, y aún así resuelve problemas NP-duros muy “rápidamente”, al menos en “la mayoría” de las situaciones prácticas? ¡Tal vez! No lo sabemos todavia!

En cuanto a la criptografía RSA

Existe la idea errónea de que P ≠ NP demuestra que RSA es seguro. Esto no es necesariamente cierto, porque no se sabe si el factoring es NP-hard. Por otro lado, si P = NP, entonces RSA es “inseguro” en el sentido de que puede romperse en el tiempo polinómico. Pero, una vez más, mientras que el “tiempo polinomial” se usa como un proxy para “rápido”, esto no necesariamente corresponde a algo que un humano consideraría realmente rápido.

Ok, Sr. Smartypants, entonces ¿por qué P vs. NP es tan importante?

Hay varias razones por las que es un gran problema. La razón obvia inmediata de que sí, podría tener ramificaciones prácticas muy grandes en el mundo.

Pero la razón más importante en mi opinión de por qué es un problema significativo es porque simplemente porque, desde una perspectiva teórica o académica, es un problema fundamental muy interesante, profundo, hermoso, rico y difícil que ha conducido y tiene el potencial de conducir a mucha investigación y progreso en el estado del conocimiento de la humanidad. La historia ha demostrado que, a largo plazo, la investigación y el trabajo en problemas tan difíciles y fundamentales como P vs. NP a menudo conducen a grandes avances y avances, tanto prácticos como teóricos. No podemos predecir cómo serán esos avances: la ciencia es un viaje hacia lo desconocido, pero no es imprudente hacer la “apuesta”. (Se pueden hacer declaraciones similares sobre otros temas en CS como Quantum Computing).

Para más reflexiones sobre tales preguntas, vea la respuesta de Kevin Lin a ¿Qué beneficios tangibles del mundo real hay detrás de probar el último teorema de Fermat?

Haré todo lo posible para explicar (comentar si me sale algo mal). También tenga en cuenta que cubriré los antecedentes generales de la pregunta P = NP vs P! = NP en aras de la exhaustividad, y porque creo que es necesario comprender la respuesta a la pregunta:

Básicamente, hay una clase de problemas, la clase P, que se puede resolver computacionalmente en tiempo polinómico. Esto significa que a medida que aumenta el tamaño de entrada N, el tiempo de ejecución del algoritmo es algo de la forma N ^ X, donde X es un número. Los ejemplos incluyen N ^ 2, N ^ 50 e incluso N ^ 1000. Estos se consideran polinomios en tiempo de ejecución. Una mejor discusión, ya que esto se abrevia bastante, se puede encontrar aquí: http://en.wikipedia.org/wiki/P_ ( … En términos menos sofisticados, puede pensar que los problemas de P pueden resolverse “rápidamente”, donde rápido es un término relativo (lo que significa que no siempre se pueden resolver RÁPIDAMENTE, pero en comparación con otros tipos de problemas de tamaño similar, la solución es rápida).

Hay otro conjunto de problemas, NP, que incluye los problemas de P, pero también incluye otros problemas que no tienen una solución de tiempo polinomial que conozcamos. Dicho de otra manera, la clase NP contiene nuestros problemas P rápidamente solucionables, pero también problemas que no podemos resolver rápidamente hasta donde podemos ver. El sello distintivo de todos los problemas de NP (ambos tipos) es que las soluciones a los problemas de NP pueden verificarse en tiempo polinómico. Un ejemplo de un problema de NP que no tiene una solución de poli-tiempo es el problema de la suma de subconjuntos ( http://en.wikipedia.org/wiki/NP_ … En este ejemplo, la solución no se puede calcular en poli-tiempo, pero la solución puede verificarse en tiempo polivinílico. Por lo tanto, podemos verificar una respuesta rápidamente, pero no podemos resolverla rápidamente (o al menos no sabemos cómo resolverla rápidamente) para los problemas que no son P NP Sin embargo, debido a que la respuesta a estos problemas puede verificarse en tiempo polinómico, como los problemas P, existe la esperanza de que efectivamente existan soluciones de tiempo polinomial para los problemas NP restantes (simplemente no los hemos descubierto todavía). de eso: NP incluye la clase P de problemas, así como “otros” problemas, y estos “otros” problemas actualmente no tienen una solución rápida como los problemas P, sino que tardan más en resolverse. Pero tenemos la esperanza de que soluciones rápidas a Estos otros problemas existen, porque al igual que los problemas de P, las soluciones a estos otros problemas son verificables rápidamente.

En este punto, me gusta este gráfico de Wikipedia que describe los conjuntos / subconjuntos de complejidad: http://en.wikipedia.org/wiki/Fil… .

Esto nos lleva a la pregunta: ¿existen soluciones de tiempo polinomiales para los problemas NP que no son P? Muchos problemas que queremos resolver computacionalmente son NP (lo que significa que tardan mucho tiempo en resolverse, y nuevamente en algunos casos demasiado tiempo para que podamos resolverlo incluso para intentarlo). A partir de ahora, nos vemos obligados a usar algoritmos de aproximación para reducir los posibles espacios de tales problemas, para hacerlos manejables (solucionables). Sería bueno para todos si P = NP, lo que significaría que, en realidad, existe una solución de tiempo polinomial para los problemas de NP, y aún no la hemos descubierto. Entonces, los “otros” problemas de NP serán computacionalmente solucionables si P = NP.

Si P! = NP, entonces, francamente, hay algunos problemas cuyas soluciones se pueden verificar en tiempo polinómico, pero no se pueden resolver en tiempo polinómico (estos son los “otros” problemas NP). Eso significaría que estamos básicamente atrapados donde estamos hoy: una cierta clase de problemas no tiene una solución rápida, y estamos atrapados resolviéndolos extremadamente lentamente o obligados a usar aproximaciones para resolverlos (lo que significa que nuestras respuestas no son óptimas) . Dicho de otra manera, si P! = NP, entonces todos los problemas NP útiles que existen (¡hay muchos!) Nos tomarán mucho tiempo resolver si queremos resolverlos por completo, porque a diferencia de los problemas P, hay No es una solución de tiempo polinomial. Y por lo que puedo decir, incluso los algoritmos de aproximación también llevan bastante tiempo, dependiendo de cuán preciso desee ser / la naturaleza del problema. Supongo (se agradecerían los comentarios) que incluso las buenas aproximaciones llevan mucho tiempo para la mayoría de los problemas de NP (aunque, como dije, es una suposición educada).

Básicamente, si P! = NP, muchos problemas que queremos resolver computacionalmente no pueden resolverse rápidamente a medida que los problemas crecen. Un ejemplo de wikipedia es la predicción de la estructura de la proteína, que se sabe que es NP ( http://en.wikipedia.org/wiki/P_v …).

PD. Mira esta respuesta, que define aún más el vocabulario que utilicé aquí: ¿Qué son P, NP, NP-complete y NP-hard?

P representa la clase de problemas que se pueden resolver en tiempo polinómico
NP representa la clase de problemas cuyas soluciones pueden verificarse en tiempo polinómico

(resumido de la conferencia del premio Turing de Karp)

En otras palabras, adivine de manera no determinista la solución y verifíquela en tiempo polinómico. La suposición no es determinista y la verificación es polinómica. Por lo tanto, el tiempo polinomial (NP) no determinista

Si P fuera igual a NP, habría consecuencias asombrosas. Significa que cada problema verificable en tiempo polinómico también podría resolverse en tiempo polinómico, todas las optimizaciones combinatorias podrían resolverse en tiempo polinómico. La maldición de las explosiones combinatorias se habría ido. Parece poco probable que sea cierto … sin embargo, NO se ha encontrado una contra prueba (es decir, P! = NP).

Problema SAT (presentado por el científico Cook)
El logro más importante de Cook es mostrar que P = NP si un problema computacional particular llamado SAT está en P.
Cook demostró que cualquier problema en NP puede transformarse en una instancia correspondiente del problema SAT de tal manera que el original tenga una solución si la instancia de satisfacción lo tiene. Además, esta traducción se puede hacer en tiempo polinómico. En otras palabras, el problema SAT es lo suficientemente general como para capturar la estructura de cualquier problema en NP. De esto se deduce que si podemos resolver el problema SAT en tiempo polinómico, entonces podríamos construir un algoritmo de tiempo polinómico para resolver cualquier problema en NP.
El problema SAT es un problema arquetípico. En el campo de la optimización combinatoria, hay un problema arquetípico (programación lineal de enteros) y muchos problemas combinatorios pueden expresarse en términos de ILP.

NP Completeness (presentado por el Prof. Karp)
Karp decidió investigar si ciertos problemas combinatorios clásicos que durante mucho tiempo se creían intratables también eran arquetípicos en el sentido de Cook. Karp los llamó “polinomio completo” (más tarde conocido como NP completo ”
Se dice que un problema es NP completo si se encuentra en la clase NP y cada problema en NP es polinomialmente reducible a él. Así, según el teorema de Cook, el problema SAT es NP completo. Para mostrar un problema dado en NP es NP completo si es suficiente para mostrar que algún problema que ya se sabe que NP completo es polinomial reducible en tiempo. Al construir una serie de reducciones polinómicas, Karp demostró que la mayoría de los problemas eran NP completos

Para comprender P ≠ NP, debe tener una comprensión básica de un par de cosas.

Un problema de decisión es un problema que siempre puede responder “sí” o “no”. Por ejemplo, “¿Tienes un hermano?”. Siempre puede responder “sí” o “no” para tales preguntas. Tales problemas son lo que llamamos problemas de decisión.

Una máquina determinista de Turing es la máquina a la que estamos acostumbrados normalmente. Una computadora es una máquina de Turing determinista. Una máquina de Turing no determinista es una máquina que viene con paralelismo ilimitado. Por ejemplo, si llega a una bifurcación en una carretera, puede tomar la carretera izquierda o la carretera derecha. Así es como funciona la máquina determinista de Turing. Pero como la máquina de Turing no determinista tiene un paralelismo ilimitado, puede tomar ambos caminos. Es similar a ejecutar múltiples subprocesos en una computadora. Las máquinas de Turing no deterministas no pueden realizarse en la práctica.

Un problema de decisión está en la clase P, si podemos resolver el problema en tiempo polinómico usando una máquina de Turing determinista. Significa que podemos resolver el problema muy rápidamente. Terminará el problema en algún momento n ^ k, donde k es alguna constante. Por ejemplo, encontrar el elemento max en una matriz, verificar si una cadena es palíndromo o no, verificar si un número es primo o no, y así sucesivamente.

Un problema de decisión está en la clase NP, si podemos resolverlo en tiempo polinómico usando una máquina de Turing no determinista para obtener la respuesta “sí” a su problema. (La respuesta “no” se considera en clase co-NP). Eso significa que no podemos resolver el problema en tiempo polinómico usando una máquina de Turing determinista. Pero siempre podemos verificar si nuestra solución es correcta en el tiempo polinómico. Entonces, si alguien le da un problema NP y la respuesta es “sí”, podemos verificar si la respuesta es correcta o no en el tiempo polinómico. Pero tenga en cuenta que no podemos encontrar la respuesta en el tiempo polinómico (solo verifique si la respuesta es correcta).

También un problema de clase P también debe residir en la clase NP, ya que cualquier problema que pueda ser resuelto por una máquina de Turing determinista en tiempo polinómico, también puede ser resuelto por una máquina de Turing no determinista en tiempo polinómico. Pero tenga en cuenta que lo contrario puede no ser cierto. Esa es la carne de la famosa declaración P = NP . En caso de que resulte ser cierto, tendrá profundas implicaciones en campos como la criptografía. Podemos descifrar un cifrado usando solo su clave pública. Pero la mayoría de los científicos opinan que P ≠ NP . ¡En caso de que resuelva el problema anterior, puede ganar $ 1 millón!

“Si P = NP, entonces el mundo sería un lugar profundamente diferente de lo que generalmente suponemos. No habría ningún valor especial en ‘saltos creativos’, no habría una brecha fundamental entre resolver un problema y reconocer la solución una vez que se encuentra. Todos los que podrían apreciar una sinfonía serían Mozart; todos los que pudieran seguir un argumento paso a paso serían Gauss … “ – Scott Aaronson

P vs. NP

P versus NP es la brecha entre poder resolver un problema difícil rápidamente y poder verificar la corrección de cualquier respuesta dada a ese problema.
P y NP son dos tipos diferentes de problemas. Los problemas de P son fáciles de resolver para las computadoras, y los problemas de NP son fáciles de verificar para las computadoras, pero extremadamente difíciles de resolver para las computadoras.
Todos los problemas de P son problemas de NP; es decir, si es fácil de resolver para la computadora, es fácil verificar la solución. El problema P vs NP pregunta: dentro de la clase de problemas NP, ¿hay problemas que no sean P, es decir, que no sean fáciles de resolver para las computadoras?
El problema es que la mayoría de los desafíos del mundo real son problemas de NP, no problemas de P. Veamos algunos ejemplos:

• Un vendedor ambulante quiere visitar 100 ciudades diferentes manejando, comenzando y terminando su viaje en casa. Tiene un suministro limitado de gasolina, por lo que solo puede conducir un total de 10,000 kilómetros. Quiere saber si puede visitar todas las ciudades sin quedarse sin gasolina.
• Un agricultor quiere llevar al mercado 100 sandías de diferentes masas. Ella necesita empacar las sandías en cajas. Cada caja solo puede contener 20 kilogramos sin romperse. El agricultor necesita saber si 10 cajas serán suficientes para llevar las 100 sandías al mercado.

Todos estos problemas comparten una característica común que es la clave para comprender la naturaleza de P frente a NP: para resolver problemas difíciles (NP), debe probar todas las combinaciones .

Es por eso que el problema P versus NP es tan interesante para las personas. Si alguien lo resolviera, potencialmente haría que los problemas muy difíciles fueran muy fáciles de resolver para las computadoras. Entonces, la pregunta que todos intentan responder es la siguiente: ¿es posible encontrar un algoritmo para los problemas difíciles (problemas NP) que sea más rápido que verificar todas las posibilidades?

1. P vs. NP se ocupa de la brecha entre las computadoras que pueden resolver rápidamente los problemas frente a la posibilidad de probar las soluciones propuestas para su corrección.
2. Como tal, el problema P vs. NP es la búsqueda de una forma de resolver problemas que requieren probar millones, billones o billones de combinaciones sin tener que probar cada una.
3. Resolver este problema tendría profundos efectos en la informática y, por lo tanto, en nuestra sociedad.
   .

Será mejor que consultes la página de wikipedia: problema P versus NP, pero lo intentaré.

Intuitivamente, la pregunta P vs NP pregunta si un problema computacional es factible de resolver (técnicamente, pertenece a la clase P ) si su solución es factible de verificar (técnicamente, pertenece a la clase NP ) . Aquí, la viabilidad es con respecto al tiempo que lleva completar una tarea computacional: para algunas tareas, existen algoritmos rápidos que se adaptan bien al tamaño del problema, mientras que para otros se puede demostrar que, esencialmente, no se puede hacer mucho mejor que buscar sin pensar todas las posibilidades. En la práctica, tales diferencias en la factibilidad a menudo se manifiestan como la diferencia entre varios minutos y, bueno, para siempre (léase: muchos órdenes de magnitud más que la edad del universo, en cualquier supercomputadora que podamos construir). Todos los problemas en la clase P pertenecen a la clase NP , pero no sabemos si eso es todo lo que hay en NP , por lo tanto, tiene sentido preguntar “¿P = NP?” La cuestión es que, aunque la mayoría de los informáticos creen que hay problemas inviables en NP, no han podido probarlo durante mucho tiempo.

Ahora, poder verificar las soluciones puede no parecer una cosa muy fundamental. Para algunos problemas de ejemplo, piense en probar enunciados matemáticos: es fácil verificar la corrección de una prueba, verificar cada parte individualmente y asegurarse de que la siguiente siga a la anterior, pero parece mucho más difícil obtener la prueba completa desde cero. Estirando la analogía, piense en el arte: puede decir fácilmente una canción, un libro o una pintura genuinamente buena, simplemente escuchándola / leyendo / mirándola, pero ¿qué tal hacerla? Más técnicamente, los problemas computacionales en la clase NP abundan en las aplicaciones del mundo real, desde problemas de optimización en inteligencia artificial hasta pruebas básicas de propiedad en gráficos y pruebas de teoremas. Y para muchos de estos problemas, no tenemos algoritmos factibles para encontrar una solución, de ahí la importancia práctica de la pregunta. Lo que es más interesante, si se nos ocurre un algoritmo rápido para uno de estos problemas difíciles, ¡obtenemos algoritmos explícitos para todos de forma gratuita (no se necesita más pensamiento creativo)! Esto se debe a que todos los problemas en la clase NP pueden reducirse entre sí. Esta es una de las grandes ideas de la teoría de la complejidad: que aunque existen muchos problemas aparentemente diferentes, una vez que los miramos a través del lente de la factibilidad, se vuelven lo mismo.

En términos más generales, la pregunta P vs NP ha impulsado una gran cantidad de investigaciones relacionadas en la teoría de la complejidad (madre del problema), la informática en general, e incluso algunas áreas más remotas (¿o son?) Como la filosofía: la página sobre los ias. edu

Ya hay algunas buenas respuestas aquí, permítanme agregar algo para ir más allá de la respuesta habitual a la pregunta de P = NP.

El problema es que una prueba de P = NP puede no proporcionar ninguna pista sobre cómo construir o encontrar los algoritmos para realmente colapsar NP en P no tendrá ningún impacto práctico. De hecho, para mí solo hay 2 posibilidades más probables para la pregunta P =? NP. O no es cierto, o es cierto, pero en la práctica no hay forma de encontrar los algoritmos para hacer P = NP. Esto es realmente por qué algunos de nosotros pensamos que la pregunta puede estar mal planteada porque la suposición subyacente es que P =? NP es muy relevante en la práctica, pero en realidad es muy probable que sea irrelevante en la práctica.

Por ejemplo, una prueba teórica no constructiva puede colapsar todas las clases de complejidad, pero en la práctica pueden sostenerse porque el algoritmo en P es demasiado difícil en la práctica (como en teoría también debería estar en P si P = NP) para encontrar, si no es imposible, o en última instancia, existen restricciones físicas (por ejemplo, un argumento termodinámico) a lo que realmente puede hacer, especialmente si una prueba no constructiva no proporciona los medios para producir el algoritmo en P para uno previamente conocido en NP. Por el contrario, si es poco probable como lo creo, no solo P = NP, sino que encontramos una manera de encontrar el algoritmo en P para cualquier problema que se crea en NP, entonces el impacto será enorme para todas las áreas de la ciencia y la tecnología.

En realidad, es bastante simple ver cómo una prueba para P = NP puede no implicar nada. Esto es cambiando el marco estándar de cálculo. Ha habido, por ejemplo, sugerencias que tiene P = NP. Sin embargo, las pruebas que muestran esto hacen uso de formas de cómputo no estándar que están etiquetadas con el nombre místico de ‘hipercomputación’, es decir, el uso de cierto tipo de computadoras con capacidades extraordinarias, como ser arrojado a un agujero negro y a la computadora aún funciona y le devuelve los resultados de un cálculo, o una computadora que puede calcular más rápido de lo que permite la termodinámica, y así sucesivamente. Puede pensar entonces que tales modelos ‘divertidos’ obviamente deberían estar prohibidos, sin embargo, si se acerca a P = NP desde el punto de vista puramente matemático, los matemáticos cambian sus marcos todo el tiempo (especialmente cuando buscan probar teoremas a toda costa , por ejemplo, forzar), incluso haciendo uso común de sistemas axiomáticos no constructivos / no compatibles (o se sospecha que lo es si no tiene una computadora con propiedades extraordinarias como las que acabo de describir), como Set Theory con el Axioma de elección (un axioma que te permite elegir un elemento de un número infinito de conjuntos, algo, en la práctica, imposible) llamado ZFC.

Por lo tanto, las teorías matemáticas que requieren este tipo de poder ‘infinito’ también son no construibles / no computables y son muy comunes hasta el punto de que los matemáticos rara vez preguntan el marco en el que se ha demostrado un teorema cuando quieren reutilizarlo para algo más. Tampoco siempre está claro qué otros sistemas de axiomas matemáticos, por ejemplo, algunas formas de cálculo (análisis matemático), necesitan toda la potencia de ZFC (la mayoría de las teorías matemáticas lo hacen), por lo que en la práctica, incluso algunos teoremas que se consideran ‘ se demostró que ‘puede estar usando este tipo de’ truco ‘que en teorías construibles / computables, como las sugeridas para P = NP, uno diría inmediatamente que no deberían permitirse. Sin embargo, al final, incluso ese tipo de matemática resulta ser extremadamente útil, incluso en tareas muy constructivas como la práctica de la ingeniería y la tecnología, incluso si las teorías en sí mismas no son construibles.

Entonces, ahora puede ver el problema, si la pregunta de P = NP no siempre viene con el marco esperado en el que desea que sea cierto o no, o las condiciones para las que desea que se demuestre o refute. Y es el caso de que el marco implícito de la pregunta es el modelo de cálculo de Turing, pero parece que el marco está incompleto si no incluye el tipo de condiciones más precisas que cuantifican si la respuesta realmente puede producir los algoritmos en P para todos los problemas previos en NP, o si se puede permitir una prueba puramente no constructiva, por ejemplo, utilizando sistemas de axiomas generales, empujando la pregunta P =? NP a la irrelevancia en la práctica, ya que estaría desconectada del sentido mismo (de factibilidad) en que se hizo la pregunta.

P vs. NP:

P es el conjunto de problemas de decisión que se pueden resolver en tiempo polinómico determinista. Es decir, hay un algoritmo de tiempo polinómico (con respecto al tamaño de entrada) que resuelve cualquier problema en P.

NP es el conjunto de problemas de decisión que se pueden resolver en un tiempo polinomial no determinista. ¿Como funciona esto? Dada una solución (o “certificado” como dirían algunos) de cualquier instancia dada de un problema de decisión, ¿puede verificar si es una instancia SÍ o NO en tiempo polinómico (con respecto al tamaño de entrada)? Si es así, entonces este problema de decisión pertenece a NP.

Por ejemplo, considere la variante de decisión del problema del árbol de expansión mínimo. Es decir, ¿hay un árbol de expansión mínimo con un peso máximo de k? Esto se puede responder en tiempo polinómico aplicando el algoritmo de Prim a una instancia (no puede haber un MST con un peso menor que el árbol de expansión mínimo). Por lo tanto, pertenece a P. Además, puede verificar una solución del problema MST si es realmente un MST con un peso máximo de k. ¿Cómo haces esto? Primero verifique si es un árbol o no (solo verifique los ciclos), vea si contiene todos los vértices (es un árbol de expansión si es un árbol), luego agregue los pesos y vea si esta suma es como máximo k. Diga SÍ si es así, diga NO de lo contrario. Por lo tanto, el problema MST también está en NP. Por supuesto, esto no implica P = NP, ya que hay muchos problemas de decisión en NP que no sabemos si pertenecen a P o no.

P vs. NP es la siguiente pregunta. ¿Son iguales los conjuntos P y NP (es decir, P = NP) o son diferentes (es decir, P! = NP). ¿Puedes verificar una respuesta tan eficientemente como puedes construirla?

P = NP es el problema P versus NP .

Es un gran problema sin resolver en informática. Pregunta si cada problema cuya solución puede ser verificada rápidamente por una computadora también puede resolverse rápidamente por una computadora.

Una respuesta a la pregunta P = NP determinaría si los problemas que pueden verificarse en el tiempo polinómico, como el problema de la suma de subconjuntos, también pueden resolverse en el tiempo polinómico. Si resultó que P ≠ NP , significaría que hay problemas en NP que son más difíciles de calcular que verificar (que se denominan problemas NP completos): no se podrían resolver en tiempo polinómico, pero la respuesta podría verificarse en tiempo polinomial.

Además de ser un problema importante en la teoría computacional, una prueba de cualquier manera tendría profundas implicaciones para las matemáticas, la criptografía, la investigación de algoritmos, la inteligencia artificial, la teoría de juegos, el procesamiento multimedia, la filosofía, la economía y muchos otros campos.

Imagine que se enfrenta a un problema con un número exponencial de posibles soluciones, por ejemplo “¿Hay un camino de menos de XXX kilómetros que me permita comenzar desde mi casa y visitar Nueva York, Boston, Chicago, Miami y San Francisco (en cualquier orden) y luego volver a casa? ”

Si cree que hay una manera fácil de averiguar si existe ese camino, está en el lado P = NP.
Si crees que tienes que atravesar la mayoría de los caminos y no puedes “adivinar” en base a algunas pistas fáciles de calcular, estás en el lado P! = NP.

Tenga en cuenta que no tiene que exhibir una solución real, solo tiene que decir si existe.

Aquí, toma estas escalas,

y un montón de cosas al azar:

¿Puedes equilibrar las escalas usando todas las cosas?

Si P = NP, entonces esa pregunta puede responderse para cualquier pila de cosas sin recurrir a prueba y error; de lo contrario no puede. Debemos evitar la prueba y el error si tratamos con grandes pilas de cosas, porque el tiempo requerido para verificar cada combinación de elementos crece muy rápidamente a medida que agregamos más a la pila.

Lo mismo es cierto para cientos de preguntas diferentes, y una resolución general para cualquiera de ellas también resolvería el asunto para todos los demás.

Esta descripción breve e informal no es lo suficientemente precisa para atacar la pregunta P vs. NP ( por ejemplo, ¿qué cuenta exactamente como “prueba y error” o “cosas”?), Pero es lo más cerca que puedo llegar sin ningún tecnicismo. Estudie los tecnicismos para una explicación adecuada, el problema está notoriamente lleno de dificultades contrarias a la intuición.

Esencialmente, los problemas que pueden resolverse, es decir, los problemas para los que puede buscar rápidamente la solución, están en P. Los problemas para los que no puede buscar rápidamente la solución, pero podrían identificar la solución si se la dan, están en NP.

Una buena manera de entender algunos de los problemas es en comparación con la música. Si P [math] \ ne [/ math] NP, entonces crear buena música es significativamente más difícil que identificar buena música. Si P [math] = [/ math] NP, crear buena música no es más difícil que identificarlo.

Ahora, para decir esto realmente, tendrías que reducir la “creación musical” a un problema NP-completo y viceversa, lo que no tiene sentido, pero con suerte da algo de conocimiento.

[robado de un tweet]

P es un conjunto de todos los problemas de decisión que se pueden resolver mediante un algoritmo determinista en tiempo polinómico (donde los medios deterministas son posibles tanto en teoría como en la práctica. Y los medios no deterministas posibles en teoría no en la práctica). , logn, nlogn, n ^ 2 … ..)

NP es el conjunto de todos los problemas de decisión que se pueden resolver mediante un algoritmo no determinista en tiempo polinómico.

AHORA P = NP? es la pregunta más grande que aún no se ha resuelto. Para resolver esto, debe probar cualquiera de las dos formas que se indican a continuación

1.si P = NP, entonces, dar solución para el algoritmo en NP resuelto por algoritmo determinista en tiempo polinómico

2.si no se demuestra que el algoritmo en NP tomará un tiempo exponencial mínimo para resolverlo y no se puede resolver en tiempo polinómico usando un algoritmo determinista.

Para agregar a lo que ya está en la wiki, la imagen de arriba resume sucintamente dónde estamos actualmente con respecto al problema P = NP. Si P = NP fuera cierto, significaría que una gran clase de problemas que sabemos son fáciles de verificar para las soluciones pero que actualmente son difíciles de resolver también serían fáciles de resolver.

Hay ciertos problemas que no se pueden resolver fácilmente, pero una solución dada de los mismos se puede verificar fácilmente. Llamemos al conjunto de tales problemas ser Np.

Ejemplo: problema SAT.

Ahora, después de comprender completamente el significado de np, surge una pregunta: ¿pueden resolverse estos problemas tan fácilmente como son verificables con una solución dada?

Si la respuesta es sí, entonces P = NP

ahora hay miles de explicaciones “intuitivas” one .. una para cada problema NP completo. El que más me gusta es el siguiente: ¿Podemos idear un algoritmo que comprenda el significado de una oración en, por ejemplo, el idioma árabe clásico simplemente mirando la estructura de la frase sin “probar” todas las posibilidades de significado? Si existe dicho algoritmo (¡y de hecho existe!), También podemos observar la estructura de una oración lógica y determinar su valor de verdad, es decir, mostrar P = NP.

No sé por qué eso no se puede buscar.

Pero, básicamente, los problemas que se sabe que tienen una solución que se ejecuta en tiempo polinómico son P.

Los problemas de V que no tienen soluciones de tiempo polinomiales y, en cambio, los de tiempo exponencial se llaman NP.

Ahora ha habido mucha investigación en la línea de probar si P = NP o probar lo contrario. Tampoco ha sucedido todavía.

Y si alguien puede traer un paso más nuevo en esta área, tendría un impacto notable en el mundo actual de los problemas de matemáticas e informática.

Para dar una idea, es uno de los problemas del Premio del Milenio

Es como Ingeniero = Doctor, no podemos decir exactamente si cualquiera de los ingenieros es igual a médico o no. Si decimos ingeniero! = Doctor, entonces el médico no necesita usar instrumentos de ingeniería. Pero definitivamente decimos que uno de esos ingenieros es un subconjunto de médicos O los médicos son un subconjunto de ingenieros: p, entonces usamos el término INGENIERO CONTRA DOCTORES (P Vs NP).

Ps: – solo para crear diversión ..