¿Cómo se explica NP Complete y NP-hard a un niño?

Para comprender las clases NP Complete y NP Hard, 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 determinista de Turing. 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 es necesario que podamos 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 es necesario que podamos encontrar la respuesta en tiempo polinómico (solo verifique si la respuesta es correcta).

Un problema X está en NP-Completo si podemos demostrar que está en NP y que podemos reducir absolutamente cualquier problema de NP Y a X en tiempo polinómico, es decir, podemos resolver rápidamente Y si sabemos cómo resolver rápidamente X. Significa que si alguien descubre una solución de tiempo polinomial para cualquier problema NP-Complete, entonces cada problema NP puede resolverse en tiempo polinomial. Esto demostrará que P = NP. Por ejemplo: 3-SAT (conjunción de disyunciones de 3 cláusulas), problema del Buscaminas. Cada problema de NP puede reducirse a un problema de 3 SAT (Teorema de Cook)

Un problema está en NP-Hard si y solo si es “al menos tan” difícil como un problema de NP. La definición formal es que un problema X está en NP-Hard si hay un problema NP-Completo Y de tal manera que Y pueda reducirse a X en tiempo polinómico. Pero dado que cualquier problema NP-Completo puede reducirse a cualquier otro problema NP-Completo en tiempo polinómico, todos los problemas NP-Completo pueden reducirse a cualquier problema NP-Completo en tiempo polinomial. Entonces, si hay una solución para un problema NP-Hard en tiempo polinómico, hay una solución para todos los problemas NP en tiempo polinómico. Los problemas NP-completos también son NP difíciles. Además, los problemas NP-Hard pueden no estar en NP, lo que significa que pueden no tener soluciones que puedan verificarse en tiempo polinómico. Por ejemplo: problema de detención (dado un programa P y entrada I, ¿se detendrá? No está en NP), versión de optimización de TSP (necesitamos encontrar un cronograma real; más difícil que la versión de decisión de TSP). Los problemas NP-Hard pueden no ser un problema de decisión

Asunción: el niño conoce el Sudoku

(PAGS)

Tú: ¿Puedes ordenar estos cubos por color?
Kid: Claro, es muy fácil.

(NP-Hard)

Tú: resuelve este rompecabezas de Sudoku
Kid: Ok
Después de mucho tiempo ..
Lo resolví, pero fue difícil, me llevó mucho tiempo.

(NOTARIO PÚBLICO)

Usted: ¿Puede verificar si esta solución para el Sudoku es válida o correcta?
Kid: Sí, eso es fácil

Esta discusión es deliberadamente confusa, ya que se supone que debe dirigirse a un niño según la pregunta. Tienen años para aprender los detalles correctos.

Para simplificar las cosas, hablemos de los problemas con las respuestas “sí / no”.

Para algunos problemas, podemos describir un procedimiento paso a paso para resolverlos, y sabemos que si usamos ese procedimiento, no tomará tanto tiempo que no hay esperanza de éxito. Por ejemplo: ” ¿Hay al menos diez casas rojas en su vecindario ?” Podemos dar un paseo y contar cada casa roja que pasamos, y eventualmente contaremos hasta diez o caminaremos por todo el vecindario sin ver diez casas rojas.

La recopilación de todos estos problemas se denomina ” P “, y además de poder resolver cada uno de ellos con la suficiente facilidad, también podemos verificar con bastante facilidad la forma en que se respondió. Pero verificar no es lo mismo que encontrar una respuesta, a menudo parece más fácil, por lo que tenemos un nombre diferente para el grupo de “problemas que podemos verificar fácilmente”, y ese nombre es ” NP “.

Lo que no sabemos es si poder verificar la respuesta lo suficientemente rápido también significa que podemos encontrar una manera lo suficientemente rápida de resolverla . Algunos problemas parecen más difíciles. Por ejemplo: “Si solo tenemos diez colores para elegir, ¿podríamos pintar la casa de todos en el vecindario para que la casa de nadie sea del mismo color que las casas de sus amigos?” Parece mucho más complicado. El color que elijo para mi casa podría terminar decidiendo el color de alguien del otro lado de la ciudad a quien nunca he conocido. Después de que cincuenta personas hayan elegido sus colores, podríamos descubrir que hay dos amigos que tendrían que tener el mismo color debido a sus otros amigos; ¡entonces tendríamos que retroceder y comenzar de nuevo! Pero si alguien sugiere qué colores deberíamos pintar en las casas de todos, aún podemos verificar con facilidad para ver si su idea funciona: simplemente dale una vuelta y pregúntale a cada persona si su casa sería del mismo color que las casas de sus amigos.

Entonces tenemos estos problemas difíciles, y todavía no estamos seguros de si alguna vez encontraremos una manera de resolverlos lo suficientemente rápido. Este grupo de problemas difíciles se llama ” NP-hard “. Algunos son tan grandes y complicados que ni siquiera están en NP : si alguien le da una respuesta, aún no podría encontrar una forma lo suficientemente rápida como para verificarlo. Debido a que sabemos que son demasiado difíciles, usamos el nombre ” NP-complete ” para significar “NP-hard pero aún en NP”, cuando queremos hablar sobre problemas que parecen realmente difíciles, pero que no son tan complicados que no podríamos No verifique una respuesta si la tenemos.

Y la gran pregunta que nadie ha resuelto todavía es: “¿Todos los problemas NP-completos son realmente tan difíciles como los problemas P?” (Creemos que son más difíciles, pero no estamos seguros). Si puede encontrar una forma suficientemente buena de resolver uno de esos problemas de NP completo, los que solo sabemos cómo verificar lo suficientemente rápido, entonces usted ‘ se hizo muy famoso por eso!

Bueno, a los niños les gustan los cómics, cierto …

Y en la mayoría de las historias cómicas, generalmente hay un tropo multiverso. Por lo tanto, enmarcaría la discusión en términos de una supercomputadora hipotética que existe en la intersección del continuo espacio-tiempo donde todos los universos de realidad alternativos paralelos colisionan, así como fuera del Multiverso mismo.

Esta supercomputadora se llama la gran máquina de Turing no determinista. Cuando le da un problema para resolver, su cálculo toma decisiones diferentes en cada universo paralelo simultáneamente, y si alguna de las infinitas versiones diferentes del universo paralelo de sí mismo (digamos la versión Earth-49) encuentra la respuesta correcta, entonces el GNDTM tiene la respuesta también

Luego daría un ejemplo de cómo GNDTM podría resolver un problema en particular. Digamos que tienes una Girl Scout Intergaláctica que quiere viajar a cada planeta en su galaxia para vender Cookies de Girl Scout Intergalácticas. Ella quiere vencer a todas las otras Girl Scouts Intergalácticas en su vecindario, para poder ganar una insignia de mérito. Para hacerlo, necesita la ruta más rápida que viajará a todos los planetas de la galaxia y volverá a casa. Ya sabemos que en algún universo paralelo ella encuentra la ruta óptima y gana su insignia de mérito. El GNDTM puede determinar la ruta que tomaría en ese universo, y así puede descubrir la ruta óptima, ¡y puede producir la respuesta muy rápidamente ya que tiene acceso a la versión de sí mismo desde ese universo!

A continuación, señalaría que incluso esta supercomputadora extremadamente poderosa, como todas las computadoras, tiene sus límites. Hay algunos problemas o tareas que tomarían demasiado tiempo incluso para que GNDTM los resuelva, por lo que debemos dar un nombre a los tipos de problemas que GNDTM puede resolver de manera eficiente. Los llamaremos problemas NP, y los programas escritos para GNDTM para resolverlos los llamaremos programas NP.

Dado que el GNDTM obviamente puede hacer cualquier cosa que una computadora normal pueda hacer, cualquier problema que una computadora normal pueda resolver, el GNDTM también puede resolverlo. Por lo tanto, algunos problemas de NP pueden resolverse fácil y eficientemente con solo un programa de computadora normal en una computadora Earth-1 normal.

Pero, ¿necesitamos siquiera el GNDTM? ¿Podría un programador increíblemente genio haber escrito un programa para resolver el problema de Intergalactic Girl Scout que se ejecutará de manera eficiente incluso en un teléfono inteligente común? Esto no lo sabemos. Nadie lo ha hecho aún, pero nadie ha demostrado que no se puede hacer. Si alguien pudiera escribir un programa informático ordinario que resolviera eficientemente cualquier problema de NP sin el GNDTM, entonces nuestro mundo de cómputo multiverso esencialmente colapsaría en un universo, también conocido como Crisis en Tierras Infinitas .

Luego explicaría que, si bien eso aún no ha sucedido (y nadie puede prever que realmente suceda), hemos descubierto que hay ciertos programas de NP que son más universales que otros programas de NP, llamados programas NP-Complete. Lo que hace que los programas NP-Complete sean geniales, es que si usted fuera demasiado interfaz de una computadora ordinaria con GNDTM, y GNDTM ejecutara uno de estos programas NP-Complete, entonces podría programar la computadora ordinaria para resolver eficientemente cualquier problema NP comunicándose con el programa NP-Complete en GNDTM.

Bueno, así es esencialmente cómo explicaría la historia. Combina un poco los programas y problemas, no habla realmente de problemas de decisión versus no decisión, no explica la diferencia entre NP-Hard y NP-Complete, y ni siquiera explica lo que significa para un programa ser eficiente … pero transmite la idea principal.

No puedes explicar eso a un quinto grado y no debes gritar. Algunas cosas requieren un mayor orden de conocimiento sobre el tema. Las clases de complejidad como tales son incluso difíciles de entender para un estudiante universitario. En su lugar, debe tratar de explicarle al niño que ciertos problemas son más difíciles que otros y que algunos son inherentemente difíciles.

Ni siquiera se puede explicar eso a más que a los estudiantes de secundaria, por lo que no hay posibilidad para el quinto grado.