P – Fácil de encontrar
NP – Fácil de verificar
Un problema es: más fácil o más difícil
Por supuesto, los problemas más fáciles requieren menos tiempo para resolverse, mientras que los problemas más difíciles requieren más tiempo.
- ¿Quién decidió que, en una lista de principios científicos, la numeración comienza con cero en lugar de uno?
- ¿Qué vale la pena aprender antes de ir a la carrera de ciencias de la computación para tener éxito allí?
- ¿Es posible crear un lenguaje completo de Turing con solo un puntero de instrucción modificable, una operación de intercambio y un incremento por una operación?
- No entiendo correctamente la cita de Alan Kay sobre sus antecedentes matemáticos. ¿Alguien puede explicarlo en términos simples?
- ¿Cuáles son algunos algoritmos y estructuras de datos relevantes para la robótica?
Problemas de clase P : toma tiempo polinómico para resolver un problema como n, n ^ 2, n * logn, etc., mientras que problemas de clase NP : toma tiempo polinomial “no determinista” para verificar rápidamente un problema. Los problemas de NP son más difíciles y requieren más tiempo que los problemas de clase P.
P = NP significa que podemos resolver problemas de búsqueda sin buscar
Problema de factorización de número de caso -1
8 * 3 =? , por supuesto 24, porque solo hay una respuesta definitiva. Pero, ¿qué es lo contrario, es decir
? *? = 24, aquí pocas soluciones de factorización posibles son – 1. (2 * 12) 2. (4 * 6) 3. (3 * 8)
¿Qué pasa si hay dos números muy grandes?
(2.376.976.446.362.736.881.223.445.666.777.923.456.234) * (3.444.555.222.333.456.123.765.889.456.223.664.254.726) =?
esto también lleva tiempo polinómico para resolver o muy poco tiempo debido a que solo hay una respuesta definitiva (supongamos que estos son solo factores primos) ¿Qué pasa si sucede lo contrario?
? *? = producto de dos números anteriores
Al igual que el caso anterior 24 tiene 3 factores, este caso contiene cientos de factores. Buscar todos estos factores puede llevar un tiempo exponencial, por lo tanto, encontrar factores es difícil, pero verificar si los factores producen el mismo resultado es bastante fácil.
P = NP significa resolver ese factor exacto sin buscar o evaluar otros factores, es decir, al ver el resultado, automáticamente sabe cuáles son los dos factores primos.
Por lo tanto, resolver problemas de búsqueda sin buscar.
Caso -2 Problema de apilamiento de agujas
Supongamos que desea buscar una aguja en un HayStack inmensamente grande. Tomará algún tiempo buscar una aguja o puede tomar muchos años para buscar.
Eso es realmente un problema difícil, por lo que P = NP dice: busque una aguja en el Haystack sin buscar. entonces alguien trae un imán cerca del pajar y la aguja salió automáticamente del pajar. Debe suponer esto sobre lo que P = NP realmente significa.
Caso -3 Problema de vendedor ambulante (TSA)
Tiene 5 ciudades y necesita comenzar desde cualquier ciudad A y viajar al menos cada ciudad una vez y finalmente regresar a la ciudad donde comenzó. Pero también hay una condición: tiene una cantidad limitada de combustible en su automóvil y, por lo tanto, debe encontrar la ruta más corta más eficiente.
Tienes que probar los 4! permutaciones de posibles rutas y verificar qué ruta es más eficiente. Ahora este es un problema difícil, es decir, NP
¿Qué pasa si hay 1000 ciudades … casi 999! permutaciones, que en sí mismo es un problema bastante difícil de buscar en todos estos caminos.
P = NP dice que, sin buscar, ya sabe qué camino seguir, es decir, suponga que A–> C–> D–> B–> E–> A es el único camino más corto y eficiente, y ya lo sabe. entonces, gran parte de tu tiempo se ahorra.
Problema del Buscaminas
Clásico viejo juego de Windows – MineSweeper o podemos decir P = NP juego.
Este juego se basa en el concepto P, NP. Tienes que rastrear las minas dentro de los cuadrados sin detonarlas. Para leer más sobre esto, lea esto – Página en claymath.org
Si alguien demuestra P = NP, es posible que nunca necesite la Búsqueda de Google
Becus resolviendo problemas de búsqueda sin buscar. Desea buscar algún recurso y ya sabía dónde está realmente en la web, simplemente escriba URL y verifíquelo. Fácil de verificar: recuerde.
Supongamos que no hay ningún google & person que quiera buscar un lugar como Quora. Lo sabes, para ti es P = NP, pero para esa persona es un problema NP muy difícil. Lo sabrá algún día, pero tomará un tiempo exponencial.
Para obtener más información sobre P vs NP, lea esto:
1. Explicado: P vs. NP
2. Instituto de Matemáticas Clay
3. P vs. NP explicado
4. Explique el problema P = NP a 10 años de edad
Para que pueda entender por qué es tan importante, para usted y para todos. Incluso para aquellos que aún no están conectados.
Creo que Clay Mathematics Institute ha otorgado un premio de un millón de dólares, si alguien demuestra P = NP.
