abril 2015


En la web del Clay Mathematics Institute se encuentra el desafío de los Millenium Prizes, unos premios millonarios para quienes resuelvan los llamados problemas del milenio.

Me ha llamado la atención el apartado P vs NP (http://www.claymath.org/millenium-problems/p-vs-np-problem), donde se expone el siguiente ejemplo de problema tipo NP:

  Supongamos que estamos organizando el hospedaje de cuatrocientos estudiantes universitarios. Sólo contamos con cien plazas. Para complicar las cosas, hay una lista de estudiantes incompatibles que no quieren compartir hospedaje. Por tanto, debemos encontrar una lista de cien, de entre los cuatrocientos estudiantes, que no contenga ninguna de las parejas prohibidas.

No parece un problema difícil, puesto que, dada una lista de cien, es relativamente fácil comprobar si cumple o no los requisitos de incompatibilidad. Sin embargo, encontrar una lista de cien que cumpla los requisitos es bastante más complicado. Como punto de partida, el número de combinaciones posibles sería: 400 x 399 x 398 … x 301. Un número mayor que el total de átomos en el universo.

He aquí la definición de problema NP: verificar una solución propuesta es fácil; encontrar una solución válida es no computable.

Se me ocurre un algoritmo para tratar de resolver el problema concreto propuesto:

Definiciones:
I: lista de lista de incompatibilidades, formada por el par (I1, I2)
D: lista de estudiantes disponibles; se inicializa con los 400 estudiantes
S: solución provisional; es una lista de estudiantes compatibles; si llega a 100 elementos, el problema está resuelto


Algoritmo:
1. Ordenar los pares en I de forma creciente (I1 < I2)
2. Ordenar la propia lista I de forma creciente, primero por I1 y después por I2
3. Iniciar procedimiento recursivo por estudiante n = 1
4. Quitar n de D
5. Quitar de D todos los estudiantes incompatibles (> n) (coste lineal recorriendo I).
6. Si D está vacía, retroceder a la iteración anterior
7. Tomar el menor número de D, que será el nuevo n
8. Añadir n a S
9. Si cardinal(S) = 100, hemos encontrado una solución válida; salir de la recursión
10. Llamar a la función que empieza en 4 con el n actual
11. Si no hemos salido con éxito (punto 9), es que la recursión ha fallado; por tanto:
11.1. Quitar n de S
11.2. Volver a poner en D las incompatibilidaes de n (> n)
11.3. Ir al punto 7

El algoritmo es razonablemente eficaz para encontrar una única solución, y es fácilmente optimizable con algunas heurísticas. Sin embargo, es completamente inútil en caso de que se desee encontrar todas las posibles soluciones, especialmente si la lista de incompatibilidades es pequeña.

Anuncios

Admito que mi sueño era que esto le ocurriese a ZP (nunca es tarde…), pero me conformo contigo.

Mira cómo te atiza El País, mira: http://politica.elpais.com/politica/2015/04/09/actualidad/1428606941_836864.html.

He llegado a un punto en el que ya me importa un pimiento que seas culpable o inocente. Tienes lo que te mereces, lo que tú y tus compinches habéis pergeñado, y los que no son compinches pero sí igual de canallas que vosotros han dejado pasar, poniéndose discretamente de perfil.

Sólo te falta una cosita, a saber: renuncia a tu acta de eurodiputado y por ende al aforamiento y haz una visita a los calabozos que tantos padres han tenido que pisar por atreverse a romper con sus exparejas sin renunciar a sus hijos. Experimenta en tus ministeriales carnes lo que tantos hombres inocentes han sufrido por culpa tuya y de tus cómplices. Sangra cuando te pinchen, llora cuando te duela, siente las miradas de desprecio de los viandantes cuando te lleven esposado a comisaría por maltratador… Renuncia a tus privilegios y afronta el monstruo de siete cabezas que has contribuido a crear. Sé valiente por una vez, da la cara para que te la partan a ti también. Siempre te quedará el privilegio de que te rompan los morros con tu propio garrote.

Por supuesto no harás nada de eso. Te quedarás en tu eurosillón con el culo bien apretado y clamando justicia. Ésa que tú te cargaste con tu canallesca ley. Serás absuelto porque eres un tío importante con muchos amigos y contactos; o porque tu exmujer, presa del pánico que te tiene, retiró las acusaciones; o por falta de pruebas; o por algún defecto procesal… o quizá, incluso, porque eres inocente, qué más da. Para la sociedad emanada de tu ideología feminazi serás para siempre uno más de la lista:

De la lista de los maltratadores sin condena.

Leo en El País, el periódico del PSOE, lo siguiente:

El secretario general del PSOE, Pedro Sánchez, ha afirmado este miércoles desde Nueva York que el partido ha actuado con “contundencia” suspendiendo de militancia a López Aguilar porque “el Partido Socialista tiene que dar ejemplo en un tema que siempre ha sido una de sus reivindicaciones”.

Supongo que será la misma contundencia con la que el hoy apestado López Aguilar se aplicó en aquella ley nefasta que acababa con la igualdad legal entre hombres y mujeres y con la presunción de inocencia. La misma contundencia con la que el hoy apestado afirmaba entonces aquello de que las denuncias falsas eran un efecto colateral asumible…

Y es que esta casta de políticos necios que nos ha tocado sufrir no tiene siquiera la capacidad de previsión para ver medio palmo delante de sus narices y entender que el viejo refrán “cuando las barbas del vecino veas cortar, pon las tuyas a remojar” es sabiduría popular (no confundir con el partido del pajarito), y que el siguiente, amiguete, puedes ser tú.

Más te vale, pues, Pedrete, responder a las órdenes de tu pareja y exparejas de toda índole con un “sí ama”, no vaya a ser que el partido tenga que actuar con contundencia contigo…

En una sociedad civilizada, todo el mundo es inocente mientras no se demuestra lo contrario. Sin embargo, se da la paradoja de que el que fuera ministro de justicia cuando se aprobó la ley feminazi de violencia de género, que viola impunemente el artículo 14 de la constitución española, Juan Fernando López Aguilar, se queja ahora de que sufre una campaña de acoso a su “honorabilidad” por parte de su ex familia política.

Por encima de todo: si es culpable de algo, que lo pague.

Ahora bien, para saber si es culpable o inocente, en las sociedades democráticas se suelen celebrar juicios con una serie de garantías procesales. Los acusados suelen considerarse inocentes a menos que un juez dicte sentencia de culpabilidad. Y aún así, existen otras garantías para el acusado, como los recursos de apelación, casación, amparo, etc…

En España, por el contrario, tras la grotesca ley de violencia de género que aprobó este tipo que ahora se queja, los hombres son culpables con la sola denuncia de una señora, se les somete a pública lapidación del honor, se airean todos sus canallescos actos (verdaderos o falsos, da igual porque siendo hombre algo habrá hecho) y, por mucho que un juez dicte sentencia exculpatoria, será de por vida un maltratador. Con o sin condena, pero maltratador al fin y al cabo.

Y esto, señor López Aguilar, es lo que le ha ocurrido a usted y lo que le ocurrirá a Pedró Sánchez, a ZP o a cualquiera de ustedes que ose desobedecer a sus respectivas señoras cuando éstas les den una orden.

Ahora, amiguetes, toca asumir las consecuencias.

¡Culpable!