Explique el problema P = NP a 10 años.

54

Es mi primera pregunta en este sitio. Estoy tomando un curso de maestría en teoría de la computación. ¿Cómo explicarías el problema P = NP a un niño de 10 años y por qué tiene una recompensa monetaria?

Su toma?

Actualizaré la pregunta a medida que mi cabeza se aclare al respecto.

Mohsin Hijazee
fuente
11
Mi inclinación es cerrar esto ya que no es un nivel de investigación teórico en informática.
Dave Clarke
11
@Dave: Debería ser respondido por personas de investigación, entonces ¿tal vez sea adecuado preguntarle al lugar donde van las personas de investigación?
Jeremy
11
Creo que esto es razonable. Hay un famoso artículo llamado "Cómo explicar los protocolos de conocimiento cero a sus hijos", que creo que se consideraría a nivel de investigación. Es cierto que puede ser difícil seleccionar una "mejor respuesta", pero ese suele ser el caso con preguntas suaves. Además, esta pregunta podría terminar siendo una buena publicidad para el sitio si surgen respuestas suficientemente interesantes ... muchas personas podrían vincular a la respuesta dada aquí cuando se les pide una explicación de P vs. NP.
Philip White
77
pero realmente debería ser CW.
Suresh Venkat
55
Le pregunté la motivación porque la redacción de la pregunta me dio la impresión de que no está muy interesado en las respuestas a su propia pregunta (parecía una forma de iniciar una conversación en lugar de una pregunta real), no porque la pregunta sea tonta . Según su respuesta, parece haber hecho esta pregunta por el simple hecho de hacer una pregunta y, por lo tanto, no estoy interesado en responderla porque no le ayudará. Tenemos una cultura diferente de Stack Overflow, pero eso no es relevante ahora.
Tsuyoshi Ito

Respuestas:

33

Utilizo estas 3 diapositivas para mostrar por qué es tan difícil (¿imposible?) Encontrar un algoritmo rápido para un problema de NP:

Embalaje bin El embalaje del contenedor es NP completo 1 El embalaje del contenedor es NP completo 2

Geoffrey De Smet
fuente
Muy facil de entender.
toto
44
Creo que "no es fácil" necesita expandirse para incluir la escala a medida que aumenta el número de bloques
Ian Ringrose
3
Muy buen ejemplo, pero ¿no se llama el problema del Empaque rectangular en la literatura?
Mohammad Al-Turkistany
1
@ user54609 NP-complete no significa que podamos verificar que un empaque sea óptimo en el tiempo polinómico. NP-complete significa que podemos verificar que una solución sea factible en el tiempo polinomial (y no encontrarla consistentemente en el tiempo polinomial (a menos que P == NP)).
Geoffrey De Smet
1
Ah, entonces el problema de decisión es "¿hay una solución factible"? Veo.
ithisa
21

En esta charla, Scott Aaronson aborda la pregunta.

TEDxCaltech - Scott Aaronson - Física en el siglo XXI: Trabajando en la sombra de Feynman

Advertencia: Por favor, NO muestre esta charla directamente a su abuela / 10 años. ¿por qué? míralo y lo sabrás. ;-)

EDITAR:
Dale al niño 8 reinas rompecabezas para resolver. También dale tiempo límite.

Si "encuentra" una solución, entonces es un niño inteligente, puede comenzar a enseñarle CS de inmediato. :) De lo
contrario, le muestras la solución y le pides que "verifique" si es correcta.

ClassCheckFindExamplePEasyEasyMultiply numbersNPEasyHard8 queens

P es un conjunto de problemas para los cuales la computadora puede "encontrar" la solución fácilmente.

NP es un conjunto de problemas para los cuales la computadora no puede "encontrar" la solución fácilmente pero puede "verificar" la solución fácilmente.

Si podemos "verificar" una solución tan fácilmente, ¿por qué no podemos "encontrarla" fácilmente?

Lo que haces en CS es resolver el problema o demostrar que nadie puede hacerlo.

Si alguien inventa un algoritmo que facilite "encontrar" soluciones para problemas de NP, entonces la tabla se vería como y . P=NP

ClassCheckFindPEasyEasyNPEasyEasy
P=NP

Y si alguien demuestra que nadie puede encontrar un algoritmo para "encontrar" soluciones para problemas , entonces la tabla sigue siendo la misma y .PN PNPPNP

Pratik Deoghare
fuente
3
Quizás podrías resumir la esencia de la explicación de Scott.
Dave Clarke
2
Siempre he tenido curiosidad de qué se trata todo el alboroto P = NP, ¡ahora lo hago!
Lee Kowalkowski
Desde P ∈ NP, quizás aclare que está hablando de la parte no NP de NP aquí.
David
+1 ¡Muchas respuestas geniales en este hilo, pero esta es la única que incluso intenta definir qué significan P y NP!
Mark E. Haase
"Si podemos" verificar "una solución tan fácilmente, ¿por qué no podemos" encontrarla "fácilmente?" --- esta pregunta no ha sido respondida todavía! De lo contrario, es la mejor respuesta para mí.
19

Una de las cosas principales por las que las personas usan las computadoras es la búsqueda. Los programas como Google incluso se llaman "motores de búsqueda" y se usan millones de veces al día. Una computadora recientemente venció a los humanos en Jeopardy porque fue capaz de buscar toneladas de datos, súper rápido.

Pero algunas cosas son difíciles de buscar incluso para las computadoras. Suena raro, ¿no? Un ejemplo es la multiplicación inversa. Por supuesto si digo "¿Qué es 5 veces 3?" puedes decir "15" en un nanosegundo, ¡whooosh! Pero, ¿cuál es la respuesta a: "¿Qué dos números mutilados juntos equivalen a 21?" (Espere la respuesta, 7 x 3.) ¡Correcto! Ahora, ¿qué dos números multiplicados juntos son 23? (Espere la respuesta o la frustración).

Los únicos dos números multiplicados que equivalen a 23 son 1 y 23 en sí. Eso tomó un poco de pensamiento, ¿no? Y 23 es un número pequeño. Piensa si el número tuviera cientos de dígitos. Y la cuestión es que los mejores programas del mundo no pueden revertir la multiplicación mucho mejor de lo que un niño de 7 años podría intentar, simplemente probando un número, y luego el siguiente, y luego el siguiente. Las computadoras pueden hacerlo más rápido , pero realmente no sabemos cómo decirle a una computadora que lo haga de manera más inteligente . Las personas obtienen doctorados en estas cosas, y solo saben cómo decirle a las computadoras que hagan una multiplicación inversa un poco más inteligente.

Entonces, tal vez no haya una forma más inteligente. Pero tal vez sí, y todavía no lo hemos encontrado. En pocas palabras, ese es el problema de P / NP: si puedo reconocer una respuesta de inmediato, 1 por 23 es 23, duh, ¿eso me ayuda a buscar la respuesta más rápido? La gente piensa que es tan importante que la persona que encuentre la respuesta, sí o no, gane un millón de dólares.

Aaron Sterling
fuente
44
Bueno Probablemente no importa que el factoring sea un mal ejemplo (¿o sí?).
Raphael
44
El factoring fue el ejemplo que usó Mike Sipser en su video "explicar P / NP al público" para el Clay Mathematics Institute. Me imagino si es lo suficientemente bueno para él .....
Aaron Sterling
3
¡El problema de la suma de subconjuntos se puede explicar a los alumnos que aún no estudiaron la multiplicación!
Tegiri Nenashi
16

Creo que el problema P vs. NP podría explicarse muy suavemente en términos de Sudoku. Supongo que el niño de diez años en cuestión está familiarizado con Sudoku. Intentaré favorecer la simplicidad sobre el rigor en mi explicación.

Aquí está mi intento de explicar P = NP a un hipotético niño de diez años:

Si tienes un rompecabezas de Sudoku que no se ha terminado y quieres terminarlo, puede ser realmente difícil de hacer. Por otro lado, si su amigo resuelve el problema y usted es bueno en aritmética, no es muy difícil verificar si la solución de su amigo al acertijo es correcta.

La pregunta P = NP pregunta si existe o no un proceso muy rápido, paso a paso, para resolver un rompecabezas de Sudoku que aún no se ha terminado. El proceso paso a paso tiene que ser tan claro y fácil de entender que incluso una computadora puede entenderlo y usarlo para resolver acertijos de Sudoku de forma automática y muy rápida. Si hay un proceso tan rápido paso a paso, eso sería lo que los matemáticos llaman un "algoritmo de tiempo polinómico" (explicaré lo que eso significa cuando seas mayor).

De hecho, los informáticos y los programadores informáticos han identificado muchos otros acertijos y problemas muy importantes que son tan difíciles de resolver como el Sudoku. Es realmente importante saber si estos problemas se pueden resolver, porque las computadoras podrían ayudarnos a hacer muchas cosas más rápidamente si pudieran. Por ejemplo, podrían ayudarnos a programar trenes de manera más eficiente, descifrar códigos secretos y tal vez incluso ayudar a construir computadoras realmente inteligentes que sean capaces de inteligencia artificial.

Habría muchas cosas muy buenas que sucederían si las personas pudieran resolver P = NP. Por supuesto, también habría algunos problemas, porque sería más difícil usar códigos secretos para mantener en secreto los mensajes privados.

La mayoría de los matemáticos inteligentes piensan que P = NP no es cierto. En otras palabras, la mayoría de la gente piensa que nadie podrá resolver acertijos de Sudoku realmente difíciles rápidamente. Sin embargo, nadie ha podido demostrar que P no sea igual a NP antes, por lo que una organización llamada Clay Mathematics Institute está ofreciendo un premio de un millón de dólares por la primera prueba de que P = NP es verdadera, o por primera vez prueba de que es falso

Como puede ver, tomé la parte de "explicarle a un niño de diez años" un poco literalmente. :)

Espero que esto ayude.

Philip White
fuente
Un intento muy bueno, aunque no sé si un niño de 10 años sabrá qué es un rompecabezas de sudoku.
chazisop
2
@chazisop Por experiencia, puedo decir que las versiones básicas de los rompecabezas de sudoku (es decir, en una cuadrícula de 4x4) se han dado a los niños en los grados 3 y 4 como ejercicios, por lo que no es una suposición irrazonable.
Bob Fraser
Buena toma, pero: 1) Descarte P y NP de la explicación. No tienen sentido. 2) "muy rápido" crea exactamente la intuición incorrecta. es, por intuición razonable, "muy rápido", sino polinomial. n1000
Raphael
1
@Mohsin, de nada. @ Raphael, no creo que necesite soltar P y NP; un niño de diez años podría aceptar mi definición del problema sin necesidad de saber qué significan P y NP, y no estoy seguro de cómo podría explicar el problema sin referirme a él :). Además, dije que estaba favoreciendo la claridad sobre la precisión completa ... por lo tanto, no creo que sea injusto usar "muy rápido" y "tiempo polinómico" indistintamente.
Philip White
Mi punto es que el uso de "rápido" no crea claridad. Suponiendo que P = NP, tal vez el "único" problema es que estamos buscando algoritmos "rápidos" para problemas que no pueden resolverse "rápidamente", sino solo polinómicamente con altos grados.
Raphael
8

Así es como se lo expliqué a mi madre, espero que te sirva :)

Hay problemas para los que es fácil encontrar una solución (P, pero menos llamarlos "fácilmente solucionables"), problemas para los cuales es fácil verificar si una solución dada es correcta (NP, pero vamos a llamarlos "fácilmente verificables" ), y problemas que no son fácilmente solucionables ni fácilmente verificables. Por simplicidad, suponga que "Fácil" está formalmente definido y que cada problema tiene una solución única.

Ahora, las personas han podido probar (usando las matemáticas) relaciones interesantes entre esas dos nociones de "fácilmente solucionable" y "fácilmente verificable", de modo que algunos problemas no son fáciles de resolver y otros no son fácilmente verificables. Un ejemplo básico de tal resultado es que un problema que es fácilmente solucionable también es fácilmente comprobable: simplemente encuentre su solución y compárela con la solución dada.

Lo suficientemente tentador, para muchos problemas prácticos (como decidir si existe una posible asignación de estudiantes a profesores y aulas, cuando hay muy poco margen) no se sabe si hay una forma "fácil" de resolverlo, pero Se sabe cómo comprobar fácilmente si una solución es correcta o no. La gente intentó mucho y fracasó, luego trató de demostrar que no era posible y también fracasó: simplemente no lo saben. Algunos piensan que todos los problemas que son fácilmente verificables son fácilmente solucionables (solo deberíamos pensarlo más), algunos piensan lo contrario, que no debemos perder el tiempo tratando de encontrar soluciones fáciles a estos problemas.

Lo que descubrimos es cómo mostrar los vínculos entre los problemas (por ejemplo, si sabe cómo ir a la escuela, sabe cómo ir a la panadería que está justo en frente) y los problemas fácilmente verificables que están relacionados con todos los demás problemas fácilmente verificables ( NP-complete, pero llamémosles "problemas clave") de modo que si alguien, un día, muestra que uno de los problemas clave se resuelve fácilmente, entonces todos los problemas que son fácilmente verificables también se pueden resolver fácilmente (es decir, P = NP). Por otro lado, si alguien muestra que uno de los problemas clave no puede resolverse fácilmente, ninguno de los otros puede resolverse fácilmente (es decir, P <> NP).

Por lo tanto, la pregunta es tentadora y relativamente importante en la práctica (aunque algunos sostienen que deberíamos centrarnos en definiciones alternativas de "fácil"), y las personas están invirtiendo bastante dinero y tiempo en el debate.

Jeremy
fuente
5

Michael Sipser explica el problema P vs NP de una manera muy intuitiva en este video .

Shitikanth
fuente
1

Soy un poco escéptico acerca de la posibilidad de explicar ese problema a un niño de 10 años, o incluso a un laico, sin incurrir en tergiversación de los conceptos clave.

Todas las explicaciones formuladas en términos de "facilidad" frente a "dureza" de encontrar frente a verificar soluciones suponen la tesis de Cobham, que podría decirse que es falsa en el caso general, y en el mejor de los casos se puede considerar poco más que una regla general.

Antonio Valerio Miceli-Barone
fuente
Esta no es una respuesta a la pregunta.
Dave Clarke
Por qué no? La pregunta era "Cómo explicaría el problema P = NP a un niño de 10 años" y mi respuesta es que probablemente no exista una explicación adecuada que no tergiverse el problema. Puede estar en desacuerdo con mi respuesta, por supuesto, pero ¿por qué afirma que no responde a la pregunta?
Antonio Valerio Miceli-Barone
3
En mi opinión, esta es una respuesta posible, aunque no estoy de acuerdo. Es cierto que no podemos identificar P sin pensar en algo como el "conjunto de problemas que pueden resolverse eficientemente en el mundo real". Sin embargo, no creo que esto descarte la posibilidad de explicar el problema P =? NP a un niño de diez años a un nivel intuitivo. Por ejemplo, los niños de aproximadamente diez años aprenden el área de un círculo. Cualquier tratamiento riguroso del área requiere mucho cuidado, pero eso no descarta la posibilidad de enseñar el concepto de área a un nivel intuitivo de una manera útil.
Tsuyoshi Ito
Identificar la clase de complejidad con problemas factibles es una simplificación / idealización similar a las utilizadas en otras ciencias como la física, se puede decir que incluso el análisis asintótico es engañoso ya que las constantes pueden ser muy grandes y el algoritmo sería inviable para ejecutar, ese podría ser el caso, pero estos conceptos son una aproximación suficientemente buena para muchas tareas y son útiles en la práctica. La pregunta es dar una intuición sobre estos conceptos a los no expertos, no estoy seguro de si una primera explicación introductoria de ellos a un no experto debe ser completamente precisa oP
Kaveh
1
[continúa] entre en detalles y mencione las deficiencias del modelo. Es solo un modelo matemático simplificado abstracto que intenta capturar algunos aspectos de una noción intuitiva. Según los físicos actuales, la física newtoniana es fundamentalmente incorrecta y no establece predicciones correctas sobre la realidad en algunos dominios, pero funciona bastante bien para la mayoría de las tareas de ingeniería. Cualquier modelo matemático abstracto de un concepto intuitivo / real es solo un modelo, la tesis de Cobham sobre la identificación de algoritmos de decisión factibles con no es diferente. P
Kaveh
1

Las estrategias ganadoras para varios juegos de mesa clásicos, por ejemplo, acorazados o (más recientemente) videojuegos, han demostrado ser NP completos y esta es una excelente forma / ángulo para presentar / describir algo de la teoría central a los novatos.

acorazado como un problema de decisión completa de NP Merlijn Sevenster ICGA journal sep 2004

Buscaminas es NP preguntas frecuentes completas por el matemático RW Kaye. Edición de primavera de 2000 del Mathematical Intelligencer (volumen 22 número 2, páginas 9-15)

¡Jugar es un trabajo difícil, pero alguien tiene que hacerlo! papel arxiv de Giovanni Viglietta. analiza la complejidad computacional de Pac-Man, Tron, Lode Runner, Boulder Dash, Deflektor, Mindbender, Pipe Mania, Skweek, Prince of Persia, Lemmings, Doom, Puzzle Bobble 3 y Starcraft.

Pacman es un artículo de tecnología extrema extrema en el documento anterior

vzn
fuente
ver también UNA ENCUESTA DE ROMPECABEZAS NP-COMPLETO por Kendall, Parkes, Spoerer y Jugar juegos con algoritmos: Algorithmic Combinatorial Game Theory por Demaine and Hearn
vzn
0

Y aquí está mi opinión sobre el problema.

Kido!

Sabes que enfrentamos muchos problemas en nuestra vida. Puedes decir desafíos. Algunos son difíciles, algunos son más fáciles. Por ejemplo, a menudo necesita sumar dos números. Y anoche, estábamos en el tablero de ajedrez y tuvimos que ganarle a nuestro vecino. Bueno, sumar dos números es un problema simple y directo con pasos limitados involucrados. Tales problemas se denominan problemas de clase P porque hay muchos problemas que son bastante sencillos con pasos discretos que se deben repetir una y otra vez para obtener una solución.

Por otro lado, anoche en nuestro juego de cofres, ¿cuál sería la mejor estrategia para ganar el juego? Podríamos mover el primer peón un paso, o el segundo peón un paso, o podríamos mover el segundo peón dos pasos y el primer peón un paso para que veas que hay muchas posibilidades. Pero, ¿hay alguna forma para nosotros o un receptor que nos brinde un conjunto completo de movimientos ordenados que produzcan lo mejor y un jaque mate? Como puede ver, es bastante difícil porque hay muchas posibilidades en cada paso. Miles de millones y miles de millones como dice Carl Sagan.

Pero querida, ¿qué pasa si te digo todas las posiciones de la junta y te pregunto si es un jaque mate? Seguramente podrá decir rápidamente dentro de unos pocos exámenes si quedan movimientos legales para el rey.

Por lo tanto, estos problemas son difíciles de resolver pero si su solución es fácilmente verificable en unos pocos pasos simples, se denominan problemas NP.

¿Ahora preguntas qué significa P = NP? En realidad, esta pregunta significa que ¿hay alguna manera de que podamos encontrar una solución más simple para encontrar la mejor estrategia o la lista ordenada de movimientos para un juego de ajedrez sin pasar por todos los miles de millones de posibilidades al igual que lo hacemos para una simple adición? Esta simple pregunta aún no tiene respuesta. No tenemos ninguna prueba de su verdad o rechazo, pero si lo hacemos, será un gran avance. Si resulta ser cierto, nuestra civilización podría resolver problemas muy complejos convirtiéndolos en problemas de clase P. Las personas podrán descifrar contraseñas en segundos, los mensajes se descifrarán y mucho más y es por eso que este problema se considera uno de los problemas más importantes del milenio.

Mohsin Hijazee
fuente
Puede valer la pena apretar el texto. ¿Has intentado leer esto en voz alta?
András Salamon
Todo no debería ser más estricto que las definiciones matemáticas, creo.
Mohsin Hijazee
Si aprieta demasiado el texto, la gente normal no tendrá suficiente "espacio" para comprender un concepto antes de pasar al siguiente.
Ian Ringrose
n×n
Este enlace es quizás más claro que el anterior: cstheory.stackexchange.com/questions/6563/…
Juan Bermejo Vega