Np-completos

Problemas NP-completos

Esto va del "tiempo de resolución"
Si mides cuánto tarda un programa de ordenador en resolver problemas más y más difíciles, como ordenar una lista de 10 objetos, 20objetos, 30 objetos, etc., entonces puedes dibujar en un gráfico los tiempos y así tienes una función.
| Por ejemplo el tiempo puede crecer como x², así que un problema que es el doble de difícil tarda4 veces más. Decimos que ese programa estaría en "P", que significa que el problema se resuelve en tiempo "polinomial". En ese caso el polinomio es:t = x² |
Pero si el tiempo aumentaraexponencialmente o factorialmente, o algo por encima de lo que crecería un polinomio, no estaría en "P". No es resoluble en tiempo "polinomial".
La Computadora Asombrosa puede hacer cosas que las normales nopueden
Ahora bien, el "N" de "NP" se refiere al hecho de que no estás limitado por el funcionamiento normal de las computadoras, que es paso a paso. El "N" en realidad quiere decir "no determinista". Estosignifica que lo podría hacer una computadora asombrosa que puede hacer varias cosas a la vez o adivinar el camino correcto de alguna manera, o algo así.
Así que esta computadora "N" puede resolvermuchos más problemas en tiempo "P", por ejemplo podría clonarse a sí misma cuando hiciera falta.
No es una supercomputadora (esas sólo son computadoras normales), es una computadora "nodeterminista", ¡yo la llamo la Computadora Asombrosa para que te hagas una idea!
Así los programas que tardan muchísimo más cuando el problema se complica (o sea, no en "P") se podrían resolver rápidamente conesta asombrosa computadora "N" así que decimos que está en "NP". O sea que "NP" significa "lo podemos resolver en tiempo polinomial si podemos romper las reglas normales de la computación paso a paso".La Computadora Asombrosa también puede hacer lo que hacen las computadoras normales
| Como la computadora asombrosa "N" puede hacer lo que hacen las computadoras normales, sabemos que los...