Veamos un subconjunto específico de problemas para desarrollar cierta intuición. Considere un problema de decisión, también conocido como una pregunta SÍ / NO. Un ejemplo simple podría ser: “En mi mochila escolar, ¿hay un artículo más valioso?” Una más interesante podría ser: “En mi mochila escolar, ¿hay un subconjunto de artículos cuyo peso combinado sea como máximo de 10 libras? y un valor combinado de al menos $ 100? ”(Este problema en general: problema de mochila – Wikipedia)
En el segundo ejemplo, una forma en que podría abordar la pregunta es probar cada posible subconjunto de elementos. Entonces, si tuviera 5 cosas en mi bolso, tendría que probar [matemáticas] 2 ^ 5 [/ matemáticas] diferentes subconjuntos posibles de elementos y calcular su peso y valor combinados. En general, si tuviera [math] n [/ math] artículos en mi bolsa, tendría que probar [math] 2 ^ n [/ math] diferentes subconjuntos. Entonces, hay un aumento exponencial de la cantidad de soluciones que tengo que verificar a medida que aumenta la cantidad de artículos en mi bolsa. (Observación: hay formas más rápidas y menos ingenuas de resolver este problema, pero son más complejas y, en mi opinión, proporcionan menos intuición)
Por otro lado, supongamos que un amigo afirmó que yo tenía un subconjunto de artículos cuyo peso combinado es como máximo de 10 libras. y un valor combinado de al menos $ 100. Una cosa razonable que podría preguntar es: “OK, pruébelo: qué subconjunto de artículos pesan colectivamente como máximo 10 libras. ¿y tiene un valor colectivo de al menos $ 100? ”. Mi amigo podría responder:“ Su libro de texto, notas y bolígrafos ”. Ahora todo lo que tengo que hacer es verificar estos tres elementos y verificar que colectivamente pesen menos de 10 libras. y valen más de $ 100.
- En informática y lógica matemática, ¿qué es la capacidad de decisión y en qué se diferencia de la capacidad de computación?
- ¿Cuál es el significado del Lema Hardcore de Impagliazzo?
- ¿Cuáles son algunas de las aplicaciones más elegantes de la teoría de grafos?
- ¿Qué es el punto de secuencia en c?
- ¿Qué temas en matemáticas debo aprender para la programación competitiva?
Esperemos que este pequeño ejemplo ilustra lo fácil que es verificar una solución en comparación con la producción de una. ¿Por qué es este el caso? Podemos pensar en un algoritmo como un proceso de eliminación en el espacio de la solución. En mi ingenuo algoritmo, simplemente verifiqué todas las soluciones posibles hasta que encontré una solución válida o me quedé sin soluciones para verificar. Pero si solo necesito verificar una respuesta, no necesito verificar todas las respuestas posibles, solo necesito verificar la que me dieron.
Una última cosa. Observe cómo si es fácil resolver un problema de decisión, también es fácil verificar una solución (ignore la prueba de su amigo; solo resuelva el problema usted mismo). Sin embargo, actualmente se desconoce si lo contrario es cierto, es decir, si es fácil verificar una solución a un problema, ¿también es fácil resolver el problema? Existe una gran cantidad de evidencia que sugiere que esto no es cierto, aunque nadie lo ha probado todavía. Ver problema P versus NP – Wikipedia
