¿Cuál es una explicación de los problemas P versus NP y otros términos relacionados en términos simples?

Suposición: mamá conoce el Sudoku

(PAGS)

Tú: ¿Puedes ordenar estos cubos por color?
Mamá: Claro, es muy fácil.

(NP-Hard)

Tú: resuelve este rompecabezas de Sudoku
Mamá: está bien
Después de mucho tiempo ..
Lo resolví, pero fue difícil, me llevó mucho tiempo.

(NOTARIO PÚBLICO)

Usted: ¿Puede verificar si esta solución para el Sudoku es válida o correcta?
Mamá: eso es fácil

Los informáticos intentan agrupar los problemas basándose en lo “fácil” que es resolverlos con una computadora. Dado que hay una gran cantidad de problemas, para simplificar las cosas, los han agrupado en varias clases y los analizan.
Una de las clases de problemas se llama “Polinomio”, donde los problemas pueden resolverse de una manera “fácil”. Solo necesita potencia de cálculo proporcional a los datos de entrada. Por ejemplo, si tengo que organizar una lista de nombres en orden ascendente, puedo usar un algoritmo de clasificación que resolvería el problema sin muchos problemas. Si el número de nombres aumenta de 1 millón a 10 millones, solo necesito comprar un hardware adicional y las cosas irían.

Hay otra clase importante llamada “Polinomio no determinista” (NP) donde es fácil verificar la solución, pero difícil de resolver por sí mismo. La mayoría de los problemas interesantes para la humanidad pertenecen a esta clase. Digamos que estás tratando de resolver un problema para tu clase de matemáticas. Por lo general, el tiempo necesario para resolverlo sería mucho mayor que el tiempo necesario para verificar su prueba al final. En un caso extraordinario, el último teorema de Fermat tardó 358 años para que alguien lo resolviera, mientras que se necesitó mucho menos para que otro verificara que la prueba era correcta.

El ajedrez es otro ejemplo. Es fácil encontrar si hay jaque mate o no en el movimiento actual, pero es difícil encontrar una lista de movimientos que conduzcan a un jaque mate. En todos estos casos, resolver el problema lleva un tiempo no determinista, mientras que verificar la prueba solo lleva un tiempo polinómico.

La pregunta realmente es ¿podemos resolver estos problemas de NP en tiempo polinomial al igual que podemos verificar estos problemas en tiempo polinomial? Si bien muchos creen que no hay forma de resolver estos problemas en tiempo polinómico, no hay forma de demostrarlo hasta ahora. P versus NP es, por lo tanto, un desafío venir con una prueba matemática para afirmar que la clase de problemas bajo NP puede resolverse en tiempo polinómico o no puede resolverse en tiempo polinómico.

Si pudiéramos mostrar P = NP, podría ocurrir una revolución completamente nueva en la informática, donde se podrían resolver varios problemas importantes para la humanidad con algoritmos deterministas en lugar de heurísticos.

No voy a definir el término técnico “tiempo polinómico”, aunque la definición es bastante importante técnicamente. Puedes considerarlo más o menos como si significara que la ley de Moore finalmente se pondrá al día incluso con los casos más problemáticos. Me referiré a él como “tiempo razonable”, durante el resto de esta respuesta.

P y NP son clases de complejidad. Las clases de complejidad son conjuntos de problemas que (al menos en teoría) tienen soluciones que satisfacen ciertas condiciones.

La condición para que un problema esté en P es que debe tener una solución que tome un tiempo razonable. La condición de que haya un problema en NP es que debe tener un método para verificar que una solución propuesta sea correcta y que tome un tiempo razonable.

Todos los problemas en P también están en NP ; si un problema puede resolverse en un tiempo razonable, no tomará un tiempo irrazonable para verificarlo; cualquier ejemplo de P es también un ejemplo de NP.

Puede darse el caso de que también todos los problemas NP sean también problemas P ; en este caso, si la solución de un problema se puede verificar en un tiempo razonable, entonces el problema en sí también se puede resolver en un tiempo razonable. Esto es lo que se entiende por P = NP.

Existen ideas erróneas generalizadas de que NP solo significa “difícil” y P simplemente significa “fácil”. Esto probablemente se deba a los nombres de otras dos clases de complejidad, NP-Hard y NP-Complete.

Los problemas NP-Hard son “al menos tan difíciles como los más difíciles en NP”. Hay problemas NP-Hard que no están en NP.

Los problemas NP-Hard que se encuentran en NP se llaman NP-Complete. En términos generales, cualquier problema en NP puede reformularse como un problema en NP-Complete en un tiempo razonable. Por lo tanto, si se encuentra una solución de tiempo razonable para cualquier problema en NP-Complete, entonces P = NP. No se han descubierto tales soluciones.

NP-Complete contiene todos los problemas NP famosos, como el problema del embalaje, el vendedor ambulante, el sudoku (es decir, la coloración de gráficos), la búsqueda de camarillas (es decir, grupos donde todos se conocen) en las redes sociales, etc.

Determinar si P = NP no es algo que en sí mismo debe afectar la vida cotidiana de las personas que no están interesadas en la pregunta por sí misma. Los detalles de la prueba podrían tener un gran impacto. Específicamente, si P = NP se prueba porque alguien encuentra una solución de tiempo razonable para, por ejemplo, sudoku, entonces también podemos crear una solución de tiempo razonable para todos esos otros problemas desafiantes.

He escrito una explicación intuitiva para P vs NP en este artículo: 40 conceptos clave de informática explicados en términos simples. Aquí está mi intento:

Digamos que te doy una pregunta de multiplicación como:

Q1: 7 x 17 = p

La respuesta es 119. Fácil de resolver, ¿verdad? ¿Qué pasa si revierto la pregunta:

Q2: p x q = 119 ( p & q no pueden ser 1 y 119)

Para resolver Q2, suponiendo que no haya visto Q1, es probable que tenga que pasar por todos los números posibles del 2 al 118. Todavía tenemos que descubrir un algoritmo eficiente que pueda encontrar fácilmente los factores de un número.

¿Qué pasa si te pregunto: podría ser p posiblemente 7? Puedes verificar fácilmente la respuesta ¿verdad? ¡Solo divide 119 por 7!

La multiplicación es fácil. Encontrar los factores originales de un número es difícil.
Entonces Q1 es un problema P (polinomial) porque es fácil de resolver . La computadora puede multiplicar fácilmente 2 números súper grandes sin gastar mucho más tiempo de computadora que los números pequeños.

Q2 es un problema NP (polinomio no determinista) porque es fácil de verificar , pero difícil de resolver . Encontrar los factores de 119 sigue siendo bastante fácil de resolver para la computadora, pero ¿qué tal un número de 500 dígitos? Es imposible para cualquier computadora en este momento.

Aquí está la parte importante: ¿Son los problemas de NP (por ejemplo, factorización) también problemas de P (por ejemplo, multiplicación), solo que no hemos descubierto la manera eficiente de resolver los problemas de NP? ¿Son realmente difíciles de resolver los problemas de NP, o simplemente necesitamos un “momento de aha” de un científico brillante (¿o usted?) Para obtener un algoritmo eficiente? ¿O tal vez los humanos son demasiado tontos? Imagine que existe una máquina o vida que posee una inteligencia mucho mayor que la humana. Nos ven como vemos a las hormigas. Nuestro nivel de inteligencia es demasiado insignificante para ellos. ¡Resolver el problema P vs NP es como resolverles 1 + 1!

Entonces, ¿por qué es importante el problema P vs NP? Si podemos probar P = NP, eso significa que todos los problemas de NP pueden resolverse fácilmente dentro de un tiempo razonable de la computadora. Podremos curar el cáncer, romper contraseñas, etc. Cambia el mundo.

Un ejemplo canónico de un problema P es la ordenación. Los escenarios comunes que involucran la clasificación incluyen ordenar una mano de cartas por rango o ordenar páginas impresas por número de página.

Los problemas de NP existen en la vida diaria, pero son menos evidentes. Vienen en forma de problemas en los que debe tomar la decisión de optimizar algunos recursos. Al hacer mandados, puede estar tratando de resolver el problema del vendedor ambulante, que puede considerarse como: “Dada una lista de tiendas y sus distancias por pares, encuentre el recorrido más corto posible que visite cada tienda exactamente una vez”. Desea ahorrar en kilometraje en su automóvil y desea hacer todos sus recados sin tener que volver a una tienda sin ningún motivo.

Cuando se mueva entre apartamentos / casas, intentará resolver un problema de embalaje del contenedor, otro problema de NP. En tal problema, “los objetos de diferentes volúmenes deben empaquetarse en un número finito de contenedores de capacidad V de una manera que minimice el número de contenedores utilizados”.

Para comprender las clases P y NP, debe tener una comprensión básica de un par de cosas.

Un problema de decisión es un problema que siempre puede responder “sí” o “no”. Por ejemplo, “¿Tienes un hermano?”. Siempre puede responder “sí” o “no” para tales preguntas. Tales problemas son lo que llamamos problemas de decisión.

Una máquina determinista de Turing es la máquina a la que estamos acostumbrados normalmente. Una computadora es una máquina de Turing determinista. Una máquina de Turing no determinista es una máquina que viene con paralelismo ilimitado. Por ejemplo, si llega a una bifurcación en una carretera, puede tomar la carretera izquierda o la carretera derecha. Así es como funciona la máquina determinista de Turing. Pero como la máquina de Turing no determinista tiene un paralelismo ilimitado, puede tomar ambos caminos. Es similar a ejecutar múltiples subprocesos en una computadora. Las máquinas de Turing no deterministas no pueden realizarse en la práctica.

Un problema de decisión está en la clase P, si podemos resolver el problema en tiempo polinómico usando una máquina de Turing determinista. Significa que podemos resolver el problema muy rápidamente. Terminará el problema en algún momento n ^ k, donde k es alguna constante. Por ejemplo, encontrar el elemento max en una matriz, verificar si una cadena es palíndromo o no, verificar si un número es primo o no, y así sucesivamente.

Un problema de decisión está en la clase NP, si podemos resolverlo en tiempo polinómico usando una máquina de Turing no determinista para obtener la respuesta “sí” a su problema. (La respuesta “no” se considera en clase co-NP). Eso significa que no podemos resolver el problema en tiempo polinómico usando una máquina de Turing determinista. Pero siempre podemos verificar si nuestra solución es correcta en el tiempo polinómico. Entonces, si alguien le da un problema NP y la respuesta es “sí”, podemos verificar si la respuesta es correcta o no en el tiempo polinómico. Pero tenga en cuenta que no podemos encontrar la respuesta en el tiempo polinómico (solo verifique si la respuesta es correcta).

También un problema de clase P también debe residir en la clase NP, ya que cualquier problema que pueda ser resuelto por una máquina de Turing determinista en tiempo polinómico, también puede ser resuelto por una máquina de Turing no determinista en tiempo polinómico. Pero tenga en cuenta que lo contrario puede no ser cierto. Esa es la carne de la famosa declaración P = NP . En caso de que resulte ser cierto, tendrá profundas implicaciones en campos como la criptografía. Podemos descifrar un cifrado usando solo su clave pública. Pero la mayoría de los científicos opinan que P ≠ NP . ¡En caso de que resuelva el problema anterior, puede ganar $ 1 millón!

“Si P = NP, entonces el mundo sería un lugar profundamente diferente de lo que generalmente suponemos. No habría ningún valor especial en ‘saltos creativos’, no habría una brecha fundamental entre resolver un problema y reconocer la solución una vez que se encuentra. Todos los que podrían apreciar una sinfonía serían Mozart; todos los que pudieran seguir un argumento paso a paso serían Gauss … “ – Scott Aaronson

Digamos que planeaste una velada perfecta con tu pareja y dejaste una nota en tu sala que decía:

”
Estoy esperando en el dormitorio
La llave está sobre la mesa.
Amor,
METRO
”

Pero para hacerlo interesante, habías dejado un montón de llaves en la mesa y solo una de ellas abre el dormitorio.

Ahora estás acostado en la cama, esposado a los rieles, (presumiblemente desnudo) contemplando si lo has hecho demasiado difícil para tu pareja.

Te das cuenta de que aunque dejaste muchas llaves diferentes, una mirada al tamaño y la forma del ojo de la cerradura en la puerta será suficiente para reducir la llave correcta a una.

Sin embargo, no recuerdas si dejaste las luces afuera de la puerta, para que tu pareja incluso vea el ojo de la cerradura, en cuyo caso, tu pareja tendrá que probar las llaves una por una para encontrar la correcta.

Pero estás atado a una cama y solo te queda contemplar el problema en cuestión. Siendo un nerd, ¿te preguntas si los dos casos son el mismo tipo de problemas?

El segundo caso de “luces apagadas” definitivamente parece más difícil que el primero.

¿Pero son ambos igualmente duros o igualmente fáciles?

Todo se reduce a la pregunta más importante de todas … ¿tendré sexo esta noche?

Hay muchos problemas que queremos resolver, y algunos son más difíciles que otros. Por ejemplo, ordenar un mazo de cartas es bastante fácil, y sabemos cómo hacerlo rápido. Este conjunto fácil de problemas es P;
Hay una serie de problemas más difíciles, en los que, si le di la pregunta y la respuesta, verificar que la respuesta es correcta es fácil. Este conjunto de problemas es NP Obviamente, los problemas fáciles entran en esta categoría; si puedo encontrar fácilmente la respuesta, puedo decir fácilmente si su respuesta es correcta, encontrando la respuesta yo mismo si no hay una manera más simple.
La pregunta es si la capacidad de reconocer fácilmente la solución a un problema significa que es fácil descubrir cuál es la solución desde cero. Si lo hace, significa que P = NP, cada problema con una solución fácilmente identificable se resuelve fácilmente. Si P! = NP, significa que hay problemas para los que podemos identificar respuestas correctas, pero es realmente difícil encontrar esa respuesta desde cero.
Hasta ahora, no hemos podido demostrarlo de una forma u otra.

Esto se trata de complejidad. Hay dos formas de describir un cierto aspecto de la complejidad de un problema, y ​​la pregunta es si esas dos descripciones aparentemente diferentes son realmente diferentes.

Antes de continuar, algunas personas podrían preguntarse cómo en la Tierra dos descripciones aparentemente diferentes pueden ser realmente diferentes. Considere este ejemplo no matemático: acaba de mudarse a una nueva ciudad y dos personas le dicen que hay un restaurante increíble que solo tiene que probar. Ambos olvidan el nombre, pero te dan instrucciones. El primer tipo dice que se dirija al norte por Main Street, tome la segunda a la izquierda, etc. El segundo tipo le dice que se dirija al oeste por State Street, tome la tercera a la derecha, etc. Es posible que ambos le estén dando dos rutas hacia el mismo restaurante, pero no se sabe hasta que aprendes un poco mejor la ciudad.

Con respecto a P = NP, todavía estamos en la fase en la que estamos aprendiendo mejor la ciudad. (Resulta que es una ciudad complicada).

Bien, hay dos formas de definir la complejidad de un problema: P y NP.

En términos simples, “P” se refiere a problemas cuyas soluciones se pueden llegar rápidamente. Por supuesto, “rápidamente” puede hacerse mucho más preciso, pero eso podría sacarnos del territorio de los “términos simples”. Pero podemos ser un poco más precisos sin necesidad de extraer fórmulas.

Quizás la aclaración más útil para hacer por adelantado es que no estamos hablando de qué tan rápido se ejecuta un programa de computadora en particular en un hardware en particular. Obviamente, la misma “solución” se implementará más rápido en una supercomputadora que en un teléfono inteligente. En cambio, cuando hablamos de un problema “fácil” o una solución “rápida”, estamos comparando la cantidad de trabajo que tiene que hacer en función de la entrada .

Por ejemplo, ordenar un montón de palabras en orden alfabético es un problema rápido. Hay muchas maneras de hacerlo, pero hablando en términos generales, se hacen muchas comparaciones de palabras con otras palabras, y la cantidad de comparaciones no se sale de control demasiado. Es decir, si tiene diez palabras para ordenar, es posible que necesite hacer diez o veinte comparaciones. Si no tienes suerte, es posible que incluso necesites hacer 100 comparaciones, pero no mucho más que eso. Pero si agrega una palabra y ahora tiene 11 palabras, de repente no tendrá que hacer 1,000,000 de comparaciones. Aún necesita hacer una serie de comparaciones en el mismo estadio que el tamaño de la lista con la que comenzó.

Compare eso con el famoso “problema del vendedor ambulante”: dado un montón de puntos (que representan, por ejemplo, ciudades), encuentre una ruta de distancia mínima que recorra cada ciudad al menos una vez. Quizás pueda ver cómo esto se sale de control rápidamente. Si adoptas un enfoque ingenuo y de fuerza bruta, cada nueva ciudad ofrece un número cada vez mayor de nuevas rutas para probar.

Así que eso es P: problemas cuyas soluciones no crecen mucho más rápido que el tamaño de su entrada. (Y no puedo resistirme: aunque puede que no sean términos simples, “no demasiado rápido” significa polinomio. Por ejemplo, ordenar una lista de longitud n requiere del orden de n ^ 2 comparaciones. El problema del vendedor viajero con n ciudades involucra n ! rutas, que crece más rápido que cualquier polinomio. Si todo eso es engullido, ignóralo.)

Bien, ¿y qué hay de NP? Estos son problemas cuyas soluciones propuestas son fáciles de verificar como correctas o incorrectas . Por ejemplo, considere los dos problemas que discutimos anteriormente: el problema del vendedor ambulante y la clasificación de una lista.

Con una lista, es fácil verificar si una lista propuesta ya está ordenada. Simplemente escanea la lista y asegúrate de que nada esté fuera de lugar. Si hay 10 cosas en la lista, tendrá que hacer 10 comprobaciones. (Si hay 10,000 cosas en la lista, solo tiene que hacer 10,000 cheques).

Compare eso con el problema del vendedor ambulante. Si te doy una ruta entre 20 ciudades y te pregunto si es la ruta más corta posible, ¿cómo haces para verificar eso? No hay nada intrínseco en la ruta que anuncia su óptimo. En este caso, verificar si tienes la ruta más corta posible solo implica resolver el maldito problema desde cero, y tener suerte y encontrar una ruta más corta antes de tiempo, o verificar que la ruta que te dieron para comenzar era, de hecho, la ruta más corta posible . (Hurra.)

Resumiendo … ordenar una lista no es muy complejo de dos maneras. Primero, es fácil ordenar una lista. En segundo lugar, es fácil (incluso más fácil, de hecho) verificar si una lista que alguien le entrega está ordenada. El problema del vendedor ambulante es muy complejo de dos maneras. Primero, el trabajo que tiene que hacer crece muy rápido con el tamaño de la entrada. Y segundo, incluso clasificar una solución propuesta como correcta o incorrecta requiere mucho trabajo (casi tanto como resolver el problema original desde cero).

La gran pregunta P = NP es si esas descripciones son redundantes: ¿ cada problema que es muy complejo (o no) en el primer sentido también es muy complejo (o no) en el segundo sentido?

Siempre es más difícil buscar tu juguete perdido (NP) que decirme cómo se ve (P).

Por lo tanto, hasta nuevo aviso, buscar agujas en los pajares siempre llevará más tiempo que verificar si el objeto que tiene en la mano es, de hecho, una aguja.

suponga que está buscando definiciones intuitivas, ya que las definiciones técnicas requieren bastante tiempo para comprender. En primer lugar, recordemos un concepto preliminar necesario para comprender esas definiciones.

• Problema de decisión : un problema con una respuesta de sí o no .

Ahora, definamos esas clases de complejidad .

PAGS

P es una clase de complejidad que representa el conjunto de todos los problemas de decisión que se pueden resolver en tiempo polinómico . Es decir, dada una instancia del problema, la respuesta sí o no se puede decidir en tiempo polinómico.
Ejemplo
Dado un gráfico conectado G, ¿se pueden colorear sus vértices usando dos colores para que ningún borde sea monocromático?
Algoritmo: comience con un vértice arbitrario, coloréelo en rojo y todos sus vecinos en azul y continúe. Deténgase cuando se quede sin vértices o se vea obligado a hacer que un borde tenga sus dos puntos finales del mismo color.

notario público

NP es una clase de complejidad que representa el conjunto de todos los problemas de decisión para los cuales las instancias donde la respuesta es “sí” tienen pruebas que pueden verificarse en tiempo polinómico.
Esto significa que si alguien nos da una instancia del problema y un certificado (a veces llamado testigo) de la respuesta afirmativa, podemos verificar que sea correcto en el tiempo polinómico.
Ejemplo
La factorización entera está en NP. Este es el problema que da a los enteros n y m, ¿hay un entero f con 1 Este es un problema de decisión porque las respuestas son sí o no. Si alguien nos entrega una instancia del problema (por lo que nos da números enteros n y m) y un número entero f con 1 tiempo polinomial realizando la división n / f.

NP-Complete

NP-Complete es una clase de complejidad que representa el conjunto de todos los problemas X en NP para los cuales es posible reducir cualquier otro problema NP Y a X en tiempo polinómico.
Intuitivamente, esto significa que podemos resolver Y rápidamente si sabemos cómo resolver X rápidamente. Precisamente, Y es reducible a X, si hay un algoritmo de tiempo polinomial f para transformar instancias y de Y en instancias x = f (y) de X en tiempo polinomial, con la propiedad de que la respuesta a y es sí, si y solo si La respuesta a f (y) es sí.
Ejemplo
3-SAT. Este es el problema en el que se nos da una conjunción (AND) de disyunciones de 3 cláusulas (OR), declaraciones de la forma
(x_v11 O x_v21 O x_v31) Y (x_v12 O x_v22 O x_v32) Y … Y (x_v1n O x_v2n O x_v3n)
donde cada x_vij es una variable booleana o la negación de una variable de una lista predefinida finita (x_1, x_2, … x_n).
Se puede demostrar que cada problema de NP puede reducirse a 3-SAT . La prueba de esto es técnica y requiere el uso de la definición técnica de NP ( basada en máquinas de Turing no deterministas ). Esto se conoce como el teorema de Cook .
Lo que hace que los problemas NP-completos sean importantes es que si se puede encontrar un algoritmo determinista de tiempo polinómico para resolver uno de ellos, cada problema NP puede resolverse en tiempo polinómico (un problema para gobernarlos todos).

NP-hard

Intuitivamente, estos son los problemas que son al menos tan difíciles como los problemas NP-completos . Tenga en cuenta que los problemas NP-hard no tienen que estar en NP , y no tienen que ser problemas de decisión .
La definición precisa aquí es que un problema X es NP-duro, si hay un problema NP completo Y, de modo que Y es reducible a X en tiempo polinomial .
Pero dado que cualquier problema NP-completo puede reducirse a cualquier otro problema NP-completo en tiempo polinómico, todos los problemas NP-completos pueden reducirse a cualquier problema NP-difícil en tiempo polinómico. Entonces, si hay una solución a un problema NP-duro en tiempo polinómico, hay una solución a todos los problemas NP en tiempo polinómico.
Ejemplo
El problema de detención es el clásico problema NP-hard. Este es el problema que, dado un programa P y una entrada I, ¿se detendrá? Este es un problema de decisión pero no está en NP. Está claro que cualquier problema de NP completo se puede reducir a este.
Mi problema NP-complete favorito es el problema del Buscaminas.

P = NP

Este es uno de los problemas más famosos de la informática y una de las preguntas pendientes más importantes en las ciencias matemáticas. De hecho, el Instituto Clay está ofreciendo un millón de dólares para una solución al problema (el informe de Stephen Cook en el sitio web de Clay es bastante bueno).
Está claro que P es un subconjunto de NP. La pregunta abierta es si los problemas de NP tienen o no soluciones deterministas de tiempo polinomial. Se cree en gran medida que no lo hacen. Aquí hay un artículo reciente sobresaliente sobre el último (y la importancia) del problema P = NP: El estado del problema P versus NP.
El mejor libro sobre el tema es Computadoras e Intractabilidad de Garey y Johnson.

Fuente: ¿Cuáles son las diferencias entre NP, NP-Complete y NP-Hard? (desbordamiento de pila)

Aunque esta explicación puede hacerse significativamente más compleja, atendiendo a los requisitos de la pregunta que pide una explicación amigable, déjenme intentar explicar esto con ejemplos simples y principalmente texto sin cálculos.

El concepto de P, NP-Hard y NP-Complete trata de encontrar soluciones a los problemas y verificar si una solución determinada resuelve un problema o no.

P se refiere al tiempo polinomial y se relaciona con el tiempo (cada paso en la solución se considera una unidad de tiempo) tomado para resolver un problema por una máquina determinada. Si una máquina resuelve un problema específico que tiene n valores de entrada en n ^ k pasos, donde k es un número entero no negativo, se dice que esa máquina puede resolver el problema en tiempo polinómico.

Consideremos un problema en el que un vendedor tiene que visitar un gran grupo de ciudades, donde cada ciudad está conectada con algunas otras del grupo. Una condición para visitar las ciudades es que cada ciudad debe ser visitada exactamente una vez.

Asuma dos máquinas construidas para resolver este problema. La máquina 1 puede comprender las condiciones del problema y cada vez que llega a un punto de decisión con respecto a qué ciudad visitar a continuación, elige una ciudad para viajar. Al mismo tiempo que la máquina 1 tarda en elegir una ciudad, la Máquina 2, por otro lado, es capaz de atravesar cada ciudad en todas las combinaciones posibles, es decir, la Máquina 2 es capaz de tomar todas las decisiones / pasos posibles y elegir la mejor ruta absoluta.

En otras palabras, la Máquina 2 también comprende las reglas del juego, pero cada vez que hay que elegir en el juego, la máquina 2 hace una copia de sí mismo que sigue cada opción disponible al tomar esa decisión. El problema P vs NP en términos muy simples está relacionado con probar que el comportamiento de la Máquina 2 (Máquina no determinista) se puede simular / Alcanzar con la Máquina 1 (Máquina determinista).

En este ejemplo, el proceso real de encontrar una solución a este problema se vuelve cada vez más difícil a medida que aumenta el número de ciudades y no puede ser resuelto en tiempo polinómico por la máquina 1. Tal problema solo puede ser resuelto en tiempo polinómico por una máquina no determinista que puede explorar múltiples caminos de decisión a la vez. Tales problemas se conocen como problemas NP-Hard.

Sin embargo, con este problema, una vez que se presenta una solución, es mucho más simple verificar si la solución es correcta o no y si la Máquina 1 puede hacerlo en tiempo polinómico. Tales problemas pertenecen a un subconjunto de problemas NP-Hard, llamado NP-Complete.

Los problemas a diferencia de esto, como ordenar o agregar un grupo de números, que la máquina 1 puede resolver y verificar en tiempo polinómico, pertenecen al conjunto P.

Las computadoras, incluso las más rápidas que se usan actualmente son típicamente de la Máquina 1 y no pueden resolver bien los problemas NP-Hard a diferencia de la Máquina teórica 2. El argumento P vs NP es muy relevante ya que muchos algoritmos importantes que utilizamos, como los que protegen su las contraseñas y las transacciones bancarias a través de Internet dependen de que las computadoras no puedan resolver los problemas NP-Hard de manera eficiente. Por ejemplo, si se prueba P a NP, significa que una computadora puede verificar todos los valores cifrados posibles de una contraseña específica en el tiempo necesario para verificar un valor. Esto haría que la mayoría de los algoritmos y medidas de seguridad sean inútiles de la noche a la mañana.

P = el conjunto de problemas que son fáciles de resolver (es decir, se puede resolver en tiempo polinómico con el tamaño de la entrada)

NP = el conjunto de problemas cuyas soluciones son fáciles de verificar (es decir, pueden verificarse en tiempo polinómico con el tamaño de la entrada)

Entonces, el problema P versus NP dice esencialmente: si podemos verificar la solución fácilmente, ¿significa que también podemos resolver el problema fácilmente?

Los fluidos y las corrientes eléctricas en la naturaleza y el laboratorio tienden a encontrar por sí mismos el camino de menor resistencia [ o mínimo de configuración o equilibrio de energía] .
¿Cómo le enseñas a un robot [o computadora] haciendo eso y cosas así? .
¿Te imaginas que con circuitos más complicados será más difícil y tomará más y más pasos para la computadora?
Resolverlo a mano es una tarea desalentadora que es propensa a errores. ¿Cuántas veces te has olvidado de llevar un dos o pensaste que 3 + 4 de alguna manera equivalía a 8? Es mejor dejarlo en manos de un algoritmo informático para que lo resuelva. Si bien podría encontrar rápidamente la mejor ruta para un pequeño número de ciudades, agregar más ciudades hace que encontrar una solución sea más difícil. Aumenta a una velocidad polinómica, por lo que en lugar de algo [matemática] x ^ 2 [/ matemática] número de pasos, podría tomar [matemática] x ^ 3, x ^ 4 [/ matemática], y así sucesivamente, comer más y más tiempo computacional con cada potencia más alta
Existe un enfoque científico que intenta categorizar una dificultad tan popular como la teoría de la complejidad. P y np son algunas de esas categorías.
.
P = NP busca equivalencia entre estos grados de dureza
y ha habido intentos muy interesantes de hacerlo
a la
una conocida pieza del folklore de la informática sostiene que, si dos placas de vidrio con clavijas entre ellas se sumergen en agua jabonosa, las burbujas de jabón formarán rápidamente un árbol Steiner [1] que conectará las clavijas, siendo esta la configuración de energía mínima .
por el bien de la familiaridad

¿Qué videojuego juegas?

1. El recorrido de ubicación y los senderos de un solo uso, ala Pac-Man , son NP-hard.
   
2. Las placas de presión, a la Prince of Persia o Portal , son duras para PSPACE si hay dos placas de presión, y duras para NP si solo se requiere una para abrir una puerta.
3. En el caso de los interruptores, un interruptor es P-hard, dos es NP-hard y tres o más son PSPACE-hard.

Pregunta porque ?
[1] http://en.wikipedia.org/wiki/Ste…
[2] http://www.technologyreview.in/b…
[3] http://www.scottaaronson.com/pap…