Para explicar P vs NP a un niño, intentemos usar los problemas que encontrarían en un libro de texto de matemáticas para explicar la diferencia. Cuando era niño, recuerdo amar los rompecabezas de geometría mientras odiaba los aburridos ejercicios aritméticos. Por lo tanto, tratar de clasificar explícitamente estos problemas específicos en P y NP podría ser un ejercicio interesante para el niño.
Problemas aritméticos
Primero presente al niño con un problema de suma simple.
- ¿Cómo prueba un algoritmo de tiempo polinómico a un problema NP-Hard conocido que P = NP? ¿No podría haber otros problemas en NP que no hayamos concebido?
- ¿Cuáles son las estrategias de vanguardia para el reconocimiento de intención (plan) relacionadas con la comprensión del lenguaje natural?
- ¿Cómo es estudiar informática en Princeton?
- ¿Hay científicos trabajando para unir las diversas disciplinas de la ciencia en un solo campo?
- ¿Cuál es la mayor influencia que ha tenido la neurociencia en la visión por computadora y viceversa?
Él / ella lo atravesará y lo resolverá de la siguiente manera:
Ahora, moleste un poco al niño presentando otro problema de suma con números mucho mayores.
Su hijo comenzará a sumar a regañadientes los números, pero eventualmente escuchará una de las siguientes quejas:
- Esto es muy repetitivo.
- Sé cómo resolver esto, solo tomará un tiempo.
- ¿Puedo usar una calculadora?
Esta es una intuición útil, por lo que puede detenerlo allí. Luego pasas a otro conjunto de problemas.
Problemas de geometría
Ahora presente al niño un problema simple de prueba de geometría como:
De nuevo, el niño probablemente superará esto con:
[matemática] x + 80 ° = 180 ° (Axioma de par lineal) => x = 100 ° [/ matemática]
Ahora presente a su hijo un problema un poco más desafiante:
Su hijo puede resolverlo o no, pero pídale que preste atención a cómo esto es diferente de resolver el problema aritmético difícil.
[matemáticas] ⦟A + ⦟B + ⦟C = 180 ° => ⦟B + ⦟C = 180 ° -⦟A [/ matemáticas]
(Ángulos en un triángulo)
[matemática] ⦟B / 2 + ⦟C / 2 = 90 ° -⦟A / 2 (1) [/ matemática]
(Dividiendo por dos en ambos lados)
[matemática] ⦟OBC + ⦟OCB + ⦟BOC = 180 ° => ⦟OBC + ⦟OCB = 180 ° -⦟BOC (2) [/ matemática]
(Ángulos en un triángulo)
Sustituyendo B / 2 + C / 2 en (1) y (2)
[matemáticas] 180 ° -⦟BOC = 90 ° -⦟A / 2 => ⦟BOC = 90 ° + ⦟A / 2 [/ matemáticas]
En este punto, puedes hablar sobre P vs NP.
PAGS
Indique al niño cómo el problema aritmético difícil fue un trabajo más tedioso que resolver el problema aritmético fácil. El niño intuitivamente sabía que el problema podría resolverse, pero solo tomaría más tiempo con grandes números. El niño también sabría que podría sumar los números usando una calculadora y verificar su trabajo con el resultado de la calculadora para verificar su respuesta.
Dirija su atención al hecho de que verificar una respuesta dada como correcta (sin una calculadora) y producir la respuesta requiere aproximadamente la misma cantidad de esfuerzo repetitivo.
Dígale que estos problemas aritméticos pertenecen a una bolsa llamada P.
notario público
Señale al niño cómo el problema de la geometría difícil requería más creatividad que el problema aritmético. Si bien la solución es bastante corta, no existe un ‘método’ directo para resolver un problema de geometría difícil. El niño tiene que confiar en la intuición para producir la prueba.
Además, una vez que se entregue la prueba al niño. El niño puede ejecutar fácilmente los pasos y comprender que es correcto. Señale al niño que inventar la prueba es significativamente más desafiante que verificar la corrección de una prueba dada (lo cual es fácil).
Dígale que estos problemas de geometría pertenecen a una bolsa llamada NP.
Resumen
Dígale que se puede enseñar a las computadoras a resolver y verificar rápidamente los problemas de la bolsa P. Sin embargo, nadie sabe cómo enseñar a las computadoras a resolver los problemas de forma rápida y correcta de la bolsa NP. Sin embargo, dada una solución para una instancia de un problema de NP, las computadoras pueden verificar rápidamente su corrección. Si le interesa, puede contarle acerca de más problemas relacionados con la bolsa P y la bolsa NP.
Descargo de responsabilidad: técnicamente, la bolsa P se puede colocar en la bolsa NP y no sé si los problemas de geometría están estrictamente en NP, pero eso es demasiado detalle para un niño.
