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.
cc.complexity-theory
soft-question
teaching
p-vs-np
Mohsin Hijazee
fuente
fuente
Respuestas:
Utilizo estas 3 diapositivas para mostrar por qué es tan difícil (¿imposible?) Encontrar un algoritmo rápido para un problema de NP:
fuente
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.
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
Y si alguien demuestra que nadie puede encontrar un algoritmo para "encontrar" soluciones para problemas , entonces la tabla sigue siendo la misma y .P ≠ N PNP P≠NP
fuente
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.
fuente
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:
Como puede ver, tomé la parte de "explicarle a un niño de diez años" un poco literalmente. :)
Espero que esto ayude.
fuente
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.
fuente
Michael Sipser explica el problema P vs NP de una manera muy intuitiva en este video .
fuente
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.
fuente
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
fuente
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.
fuente