Colecciones

P vs NP, NP-Complete y un algoritmo para todo

P vs NP, NP-Complete y un algoritmo para todo


We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

Este es el sexto artículo de una serie de siete partes sobre algoritmos y computación, que explora cómo usamos números binarios simples para impulsar nuestro mundo. El primer artículo, Cómo funcionan los algoritmos en el mundo en el que vivimos, se puede encontrar aquí.

Cuando nos sentamos a tratar de resolver un problema, muy pocos de nosotros intentamos averiguar qué tipo de problema estamos tratando de resolver. En casi todos los casos, la respuesta a esa pregunta es un ejercicio interesante e incluso puede ayudarlo a resolver el problema en algunos casos, pero no mucho más. Pero la situación es muy diferente con algo como el Problema del Viajero Viajero, razón por la cual es un tema de estudio e investigación por parte de científicos informáticos y matemáticos teóricos. Tiene todo que ver con su clasificación como problema.

Clasificación de problemas: P Vs NP

Los problemas para los que conocemos un algoritmo eficiente que es capaz de producir una solución en tiempo polinomial se clasifican como P problemasPAGS medio tiempo polinomial, en este caso. Obviamente, este fue el primer subconjunto de problemas que pudimos clasificar: de todos estos problemas, al menos logramos resolverlos aquí. Cosas como ordenar listas, equilibrar árboles, cifrar datos son problemas para los que tenemos algoritmos eficientes y, por lo tanto, pertenecen al subconjunto PAGS.

Más tarde, encontramos otro subconjunto de problemas que PAGS en sí mismo era un subconjunto de, Problemas NP. los notario público representa tiempo polinomial no determinista, pero para nuestros propósitos, no es necesario que sepa demasiado sobre lo que eso significa, excepto que es parte de la informática fundacional de la era de Turing que sustenta cada computadora moderna. Lo que necesitas saber es que Problemas NP no dispone de un algoritmo conocido que pueda producir un resultado en tiempo polinomial.

Sin embargo, si se le da una solución a un Problema NP, verificar que sea correcto es fácil y se puede hacer en tiempo polinomial o menos. Usamos este hecho cada vez que desbloqueamos nuestros iPhones o enviamos mensajes por WhatsApp. Como resulta, Problemas NP son perfectos para el cifrado; Solo hay una forma de resolver el problema que desbloquea el cifrado rápidamente, debe tener la respuesta con anticipación.

RELACIONADO: 7 ALGORITMOS ESENCIALES QUE DIRIGEN EL MUNDO

Naturalmente, nos gusta la encriptación y nos alegra que sea seguro por ahora, pero hay muchos problemas en notario público para los que realmente necesitamos algoritmos eficientes. A pesar de los mejores esfuerzos de algunas personas increíblemente inteligentes, sin embargo, ha habido muy poco progreso en la solución de todos, excepto muy pocos Problemas NP que conocemos. Esto ha generado uno de los grandes problemas matemáticos y computacionales sin resolver de los últimos 50 años: P frente a NP, también llamado P = NP.

Lo que pregunta esta ecuación es ¿puede cualquier Problema NP ser resuelto en tiempo polinomial, haciendo así Problemas NP De Verdad P problemas que solo necesitan ser resueltos adecuadamente, o hay Problemas NP para los cuales no se puede encontrar una solución en el tiempo polinomial y, por lo tanto, siguen siendo prácticamente insolubles sin importar qué algoritmos desarrollemos

Al observar estos dos conjuntos de problemas, P frente a NP, el objetivo es demostrar una de dos cosas: P = NP, lo que significa que en su conjunto, Problemas NP como conjunto, incluidos los que conocemos y los que podamos descubrir en el futuro, pertenecen en realidad a PAGS y se puede resolver en tiempo polinomial; o PAGS notario público y que no importa qué algoritmo se nos ocurra, habrá un piso matemático en la complejidad del tiempo de un problema y ese piso es mayor que el tiempo polinomial.

La respuesta a esta pregunta de cualquier manera es lo suficientemente importante como para que quien encuentre la respuesta ganará un premio de un millón de dólares del Clay Mathematics Institute, sin mencionar la instalación en el panteón de la informática además de John Von Neumann, Alan Turing, Ada Lovelace y otras luminarias. .

Para muchos, el problema de P frente a NP se trata principalmente del hecho de que existe un vacío en nuestra comprensión de las matemáticas que debe ser llenado. Los matemáticos y científicos de todas las disciplinas aborrecen el vacío de conocimiento, por lo que la solución a este problema es importante en principio. Dicho esto, la búsqueda de P = NP tiene inmensas implicaciones en el mundo real si se demuestra que, matemáticamente, P = NP. Para entender por qué, debemos incluir los dos últimos conjuntos de problemas que lo unen.

NP-Hard y NP-Complete

NP-completo es una categoría especial de Problemas NP que tienen complejidades de tiempo mayores que el tiempo polinomial, son verificables en tiempo polinomial y pertenecen a un conjunto de problemas conocidos como NP-duro. NP-duro Los problemas son esencialmente aquellos que son al menos tan difíciles como los más difíciles. Problema NP, pero no es necesario que sea verificable en tiempo polinomial.

Enumerar todos los posibles subconjuntos del conjunto de cada átomo individual en el universo es una NP-duro problema. No podemos probar que tal problema no se pueda resolver en tiempo polinomial, pero no hay razón para creer que alguna vez encontraremos ese algoritmo o incluso construiremos una máquina lo suficientemente poderosa para ejecutarlo e incluso si alguien nos diera una respuesta, no lo haríamos. incluso empezar a saber cómo hacer para verificarlo.

Otro NP-duro El problema es identificar una jugada de ajedrez en cualquier estado del tablero que sea la mejor jugada que puedes hacer. Para determinar esto, tendrías que saber que cualquier otro movimiento conducirá a un peor resultado, y la única forma en que sabemos cómo determinarlo es seguir cada camino de ramificación de cada movimiento, contraataque, etc., que es posible. con la posición del tablero dada. Una vez que llegue al resultado final de cada rama de este árbol de decisiones prácticamente infinito, tomaría el mejor resultado y diría que este fue el mejor movimiento que pudo haber hecho.

Dejando a un lado lo funcionalmente imposible de navegar por este árbol en los próximos dos mil millones de billones de años, si me dices que un movimiento en particular fue realmente el mejor movimiento posible que podrías haber hecho, no hay forma de que pueda verificar esto rápidamente. Tendría que recurrir exactamente al mismo algoritmo de permutación de fuerza bruta que usaste para explorar cada consecuencia de cada movimiento. Verificar la solución tomaría exactamente el mismo tiempo que se tardó en resolver el problema.

Si esto le suena familiar, es porque lo es. Este es el mismo problema básico que el Problema del vendedor ambulante, lo que significa que se trata esencialmente de optimización. Como resultado, esta es una de las características definitorias de NP-completo problemas; en realidad, solo está tratando de resolver un problema que tiene innumerables variaciones y esas variaciones abarcan la totalidad de lo que consideramos esencial para la toma de decisiones comerciales, políticas o de investigación.

El algoritmo para todo

Esta es la razón por P = NP importa. No podemos saberlo con certeza, pero existen muchas razones para creer que la respuesta a esa pregunta es correcta NP-completo. Primero, cualquier algoritmo que devuelva una solución a un NP-completo problema en tiempo polinomial se puede modificar para resolver cada NP-completo problema en tiempo polinomial, ya que todos son el mismo problema en su núcleo.

No solo eso, sino que forma parte de la definición de NP-completo el problema es cada problema en notario público es reducible a cada NP-completo problema, lo que significa que un algoritmo que resuelve NP-completo en tiempo polinomial también resolverá todos notario público problemas en el tiempo polinomial también; en otras palabras, resolviendo un NP-completo problema en tiempo polinomial demuestra P = NP de forma predeterminada y resuelve de forma eficaz casi todos los problemas informáticos más difíciles del mundo real, literalmente de la noche a la mañana.

Entonces esto esencialmente hace que el algoritmo que resuelve un NP-completo problema en tiempo polinomial un algoritmo para todo. Esta es la razón por P = NP, esta ecuación extraña, que suena opaca, es muy prometedora si se puede demostrar que es cierta y la única forma real de hacerlo es resolver un NP-completo Problema en tiempo polinomial. Ese algoritmo se convertiría en un algoritmo que podría desbloquear un mundo completamente diferente en un instante. Hay mucho entusiasmo en torno a la posibilidad de la computación cuántica precisamente porque puede ser nuestra mejor oportunidad para resolver NP-completo en tiempo polinomial, aunque queda por ver si se puede o no.

El artículo final de nuestra serie sobre algoritmos y computación, Algoritmos cuánticos y el futuro de la informática posclásica, se puede encontrar aquí


Ver el vídeo: Why is P vs NP Important? (Junio 2022).


Comentarios:

  1. Cyneric

    Más artículos de este tipo

  2. Zach

    De acuerdo, una frase muy útil

  3. Brocleah

    Soy definitivo, lo siento, pero esta variante no se acerca a mí.

  4. Sultan

    Lo siento, pero, en mi opinión, se cometen errores. Propongo discutirlo. Escríbeme en PM, habla.

  5. Lamorak

    Pido disculpas, pero, en mi opinión, no tienes razón. Lo sugiero que debatir. Escríbeme en PM, nos comunicaremos.

  6. Kek

    Es una pena que no pueda hablar ahora, llego tarde a la reunión. Seré liberado, definitivamente expresaré mi opinión.



Escribe un mensaje