in

Ciencias de la computación – ¿Qué es «P = NP?», y por qué es una pregunta tan famosa?

apple touch icon@2

Para dar la respuesta más simple que se me ocurre:

Suponga que tenemos un problema que requiere un cierto número de entradas y tiene varias soluciones potenciales, que pueden o no resolver el problema para determinadas entradas. Un acertijo de lógica en una revista de acertijos sería un buen ejemplo: las entradas son las condiciones («George no vive en la casa azul o verde»), y la solución potencial es una lista de afirmaciones («George vive en la casa amarilla casa, cultiva guisantes y es dueño del perro «). Un ejemplo famoso es el problema del viajante: dada una lista de ciudades, y los tiempos para ir de una ciudad a otra, y un límite de tiempo, una posible solución sería una lista de ciudades en el orden en que el vendedor las visita, y funcionaría si la suma de los tiempos de viaje fuera menor que el límite de tiempo.

Tal problema está en NP si podemos verificar de manera eficiente una posible solución para ver si funciona. Por ejemplo, dada una lista de ciudades para que el vendedor las visite en orden, podemos sumar los tiempos para cada viaje entre ciudades y ver fácilmente si está por debajo del límite de tiempo. Un problema está en P si podemos encontrar eficientemente una solución, si existe.

(Eficiente, aquí, tiene un significado matemático preciso. Prácticamente, significa que los problemas grandes no son excesivamente difíciles de resolver. Cuando se busca una posible solución, una forma ineficiente sería enumerar todas las posibles soluciones, o algo parecido a eso. , mientras que una forma eficiente requeriría buscar en un conjunto mucho más limitado).

Por lo tanto, el problema P = NP se puede expresar de esta manera: si puede verificar una solución para un problema del tipo descrito anteriormente de manera eficiente, ¿puede encontrar una solución (o demostrar que no la hay) de manera eficiente? La respuesta obvia es «¿Por qué debería poder hacerlo?», Y eso es lo que pasa hoy en día. Nadie ha podido demostrarlo de una forma u otra, y eso molesta a muchos matemáticos e informáticos. Es por eso que cualquiera que pueda probar la solución está dispuesto a recibir un millón de dólares de la Fundación Claypool.

Generalmente asumimos que P no es igual a NP, que no existe una forma general de encontrar soluciones. Si resultara que P = NP, cambiarían muchas cosas. Por ejemplo, la criptografía se volvería imposible y con ella cualquier tipo de privacidad o verificabilidad en Internet. Después de todo, podemos tomar de manera eficiente el texto cifrado y la clave y producir el texto original, por lo que si P = NP podríamos encontrar la clave de manera eficiente sin saberlo de antemano. El descifrado de contraseñas se volvería trivial. Por otro lado, existen clases enteras de problemas de planificación y problemas de asignación de recursos que podríamos resolver de manera eficaz.

Es posible que haya escuchado la descripción NP-complete. Un problema NP-completo es uno que es NP (por supuesto), y tiene esta propiedad interesante: si está en P, todos los problemas NP lo están, por lo que P = NP. Si pudieras encontrar una manera de resolver eficientemente el problema del viajante, o los acertijos de lógica de las revistas de acertijos, podrías resolver eficientemente cualquier cosa en NP. Un problema NP-completo es, en cierto modo, el tipo más difícil de problema NP.

Entonces, si puede encontrar una técnica de solución general eficiente para cualquier problema NP-completo, o demostrar que no existe, la fama y la fortuna son suyas.

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Java – Clase de caracteres

gfg 200x200 min

Python | Convertir diccionario de cadenas en diccionario