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(N1/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(N1/3 (log N)5/3).
#3 Gracias. En el enlace del artículo me pedían usuario y contraseña.
Estoy algo oxidado con lo de NPCompleto y Polinomico pero... Si es correcto, no es esto la ostia??
#11 Si mal no recuerdo la factorización en primos para un N es NPCompleto.
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.
Lo he leído, y acabo de comprender cómo se siente Penny, en The Big Bang Theory, cuando Sheldon o Leonard le explican algo. Tonto. Me he sentido tonto.
Por cierto, hoy emiten en directo, en los usa, el último capítulo de The Big Bang Theory.
#5 Hombre, ayer hicieron el último capítulo, con público en directo. Normalmente eso no lo hacen si a la vez no lo emiten, porque dudo mucho que todo el público del directo guardase silencio acerca de la trama del último capítulo. Ya sabes, spoilers y eso.
Comentarios
El PDF en cuestión está aquí: https://arxiv.org/abs/1712.09130
#3 Gracias. En el enlace del artículo me pedían usuario y contraseña.
Estoy algo oxidado con lo de NPCompleto y Polinomico pero... Si es correcto, no es esto la ostia??
#10, uhm, no sé si te entiendo, ¿te refieres a lo de P y NP? En un principio creo que no tiene nada que ver.
#11 Si mal no recuerdo la factorización en primos para un N es NPCompleto.
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.
Lo he leído, y acabo de comprender cómo se siente Penny, en The Big Bang Theory, cuando Sheldon o Leonard le explican algo. Tonto. Me he sentido tonto.
Por cierto, hoy emiten en directo, en los usa, el último capítulo de The Big Bang Theory.
#1 ¿? Quedan 4 capítulos creo recordar...
#2 No. Hoy era el último. Lo sé porque sigo a los actores en Instagram y están todos llorando a moco tendido por el fin.
#4 será el fin del rodaje, pero no de emisión.
#5 Hombre, ayer hicieron el último capítulo, con público en directo. Normalmente eso no lo hacen si a la vez no lo emiten, porque dudo mucho que todo el público del directo guardase silencio acerca de la trama del último capítulo. Ya sabes, spoilers y eso.
#6 No te lo tomes a mal pero tienes un buen lío.
#7 Seguramente. Así es mi vida, un buen lío. A veces me dan ganas de acabar con el lío, pero....
#8 Todos te queremos
@zurditorium
fantomax Por si les interesa o pueden decir algo al respecto.