jueves, 23 de enero de 2014

Qué pequeño es Q y qué raros son los abiertos

Me he encontrado con un problema que me ha parecido curioso: si un conjunto abierto $E$ verifica $\mathbb{Q} \subsetneq E \subsetneq \mathbb{R}$, ¿es verdad que $E$ debe ser igual a $\mathbb{R}$ salvo, a lo sumo, un conjunto de medida cero? Sabiendo que $\mathbb{Q}$ es un conjunto denso en $\mathbb{R}$ con la topología usual, y que un abierto es algo "gordito" en el sentido de que ningún abierto mide $0$, la existencia de un abierto que recubra todos los naturales y que mida menos que $\mathbb{R}$ es algo contraintuitiva.

jueves, 9 de enero de 2014

Tests de primalidad

Para mi asignatura de Complejidad Computacional he hecho un trabajo más o menos bibliográfico, más o menos divulgativo, sobre tests de primalidad. La estrella, digamos, del trabajo, es la demostración desmenuzada, en términos algo más elementales que los del paper original, del test AKS. Aparecen también, sin tanto detalle, los tests probabilistas de Fermat, Miller-Rabin y Solovay-Strassen. Aquí lo dejo.