• El problema
• La solución
• Resumen

si pasa tiempo en o alrededor de la comunidad de programación, probablemente escuche el término «P versus NP» con bastante frecuencia. Desafortunadamente, incluso muchos con capacitación formal en Ciencias de la Computación tienen una comprensión débil del concepto.

así que aquí hay una explicación simple y concisa:

el problema

P vs.NP el problema P vs. NP pregunta si cada problema cuya solución puede ser verificada rápidamente por una computadora también puede ser resuelto rápidamente por una computadora., (Wikipedia)

así que vamos a averiguar lo que queremos decir por P y NP.

los problemas P se resuelven fácilmente por las computadoras, y los problemas NP no se pueden resolver fácilmente, pero si presenta una solución potencial, es fácil verificar si es correcta o no.

como puede ver en el diagrama anterior, todos los problemas P son problemas NP. Es decir, si es fácil para la computadora resolver, es fácil verificar la solución. Así que el problema P vs NP es solo preguntar si estos dos tipos de problemas son los mismos, o si son diferentes, es decir, que hay algunos problemas que se verifican fácilmente, pero no se resuelven fácilmente.,

actualmente parece que P ≠ NP, lo que significa que tenemos muchos ejemplos de problemas a los que podemos verificar rápidamente posibles respuestas, pero que no podemos resolver rápidamente. Veamos algunos ejemplos:

• Un vendedor ambulante quiere visitar 100 ciudades diferentes conduciendo, comenzando y terminando su viaje en casa. Tiene un suministro limitado de gasolina, por lo que solo puede conducir un total de 10.000 kilómetros. Quiere saber si puede visitar todas las ciudades sin quedarse sin gasolina., (de Wikipedia)
• Un granjero quiere llevar 100 sandías de diferentes masas al mercado. Necesita empacar las sandías en cajas. Cada caja solo puede contener 20 kilogramos sin romperse. El agricultor necesita saber si 10 cajas serán suficientes para llevar las 100 sandías al mercado. (de Wikipedia)

todos estos problemas comparten una característica común que es la clave para entender la intriga de P versus NP: para resolverlos hay que probar todas las combinaciones.

La Solución

Esta es la razón por la respuesta a la P vs, El problema de NP es muy interesante para la gente. Si alguien fuera capaz de demostrar que P es igual a NP, haría que los problemas difíciles del mundo real fueran triviales para las computadoras.

resumen

1. P vs.NP se ocupa de la brecha entre las computadoras que pueden resolver problemas rápidamente vs. solo ser capaz de probar las soluciones propuestas para la corrección.
2. Como tal, el problema P vs. NP es la búsqueda de una manera de resolver problemas que requieren el intento de millones, billones o trillones de combinaciones sin tener que probar cada una.,
3. resolver este problema tendría efectos profundos en la informática y, por lo tanto, en nuestra sociedad.

Feb 7, 2017-agregadas atribuciones de Wikipedia.
Marzo 2, 2014-limpiado parte de la explicación para evitar confusiones.

Notas