Eratóstenes tuvo una idea para encontrar los primos menores que un límite superior N hace más de 22 siglos.
En un artículo el matemático Harald Helfgott nos da una versión de la criba más rápida y que ocupa menos espacio. Su trabajo muestra que es posible encontrar los primos menores de N en tiempo O(N log N) y espacio O(N
1/3 (log N)
2/3). Además, es posible factorizar los números enteros inferiores a N en tiempo O(N log N) y espacio O(N
1/3 (log N)
5/3).
Por cierto, hoy emiten en directo, en los usa, el último capítulo de The Big Bang Theory.
Estoy algo oxidado con lo de NPCompleto y Polinomico pero... Si es correcto, no es esto la ostia??
Creo que hay un algoritmo que transforma cualquier problema NPCompleto en otro NPC. Así que si resuelves un NPCompleto en NP resuelves todos los NPCompletos.
Pero hablo muy de memoria cuñada.