P vs NP
Como todos saben, sin la matemática discreta la informática no existiría y ahora no podría estar escribiendo esto, capaz que anduviera jugando al luche … en fin.. les presentare uno de los problemas actuales de la computación que es el famoso P vs NP
Para empezar debo explicarles que esto se trata de la complejidad que tiene resolver un problema de desición ya sea en tiempo polinomial (P) o en tiempo no polinomial (NP), por ejemplo:
Supongan que tienen una lista de numeros y quieren saber si el primer numero es el menor de esta lista, para hacerlo solo deberan recorrer su lista n-1 veces. Por lo tanto el algoritmo es de orden n O(n) que es de tipo polinomial.
3 comments