domingo, 4 de septiembre de 2016

Menú para un Domingo de Acertijos (IV):

Hola a todos otra vez, sé que he estado mucho tiempo sin escribir acertijos (más de uno me lo habéis recordado...), pero bueno, ya sabéis, cosas del verano y las vacaciones jeje. Pero ahora con la vuelta al cole (al trabajo, rutina, etcétera, según aplique) os vuelvo a traer unos cuantos rompecabezas para activar la mente después de las vacaciones. Eso sí, lo primero es lo primero, la solución al último acertijo que dejé en el blog.

Solución:

Para ver la solución hay que dejar de pensar en números romanos, moviendo el palito del dos de la derecha convertimos nuestra relación de 2 igual a 6 en números romanos, a raíz de uno igual a 1. Siendo justos esta solución no es del todo correcta, ya que la raíz de uno es uno y menos uno. Un compañero de trabajo me dio otra solución que considero aún mejor. Moviendo el palito de la izquierda del 5 en números romanos, podemos convertir el 6 (VI) en un 11 (XI) en números romanos, y ver la otra parte de la igualdad como dos unos, es decir, 11, de modo que también se verifica la igualdad. 

Este problema me parecía muy interesante porque anima a pensar desde otra perspectiva.


Y ahora vamos con los acertijos para este Domingo.

Aperitivo: los relojes de la habitación de Fermat

Si alguien no ha visto la película española de la habitación de Fermat, recomiendo que lo hagáis en cuanto encontréis un hueco. En la película se plantean varios problemas y acertijos, mi favorito es el siguiente:

"Cronometrar 9 minutos con dos relojes de arena de 7 y 4 minutos".

Primero: el problema de las ocho reinas

El ajedrez tiene algunos de los problemas mentales más divertidos de realizar, hoy os quiero proponer el conocido como problema de las ocho reinas. Este problema nos dice de situar ocho reinas en el tablero de ajedrez de manera que no se vean amenazadas entre ellas. El siguiente esquema nos da una idea de las posiciones que se sienten amenazada por una reina situada en el tablero.


Segundo: un juego no equilibrado

Este juego es conveniente realizarlo con otra persona. El funcionamiento del juego es el siguiente: Se colocan 20 fichas en el centro y cada jugador puede retirar una o dos fichas(a elección del jugador). Los jugadores juegan en turnos alternados. Después de varias partidas ¿Que es lo que ocurre?, ¿Y cual es la explicación?

Postre: pensamiento lateral

Últimamente la he cogido con este tipo de acertijos, pues me parecen muy interesantes ya que no obedecen a una lógica convencional y requieren de creatividad. 

Para empezar uno de los más famosos y fáciles:"Un hombre vive en el décimo piso de un edificio. Cada día toma el ascensor hasta la planta baja para dirigirse al trabajo o ir de compras. Cuando regresa, siempre sube en el ascensor hasta el séptimo piso y luego por la escalera los restantes tres pisos hasta su apartamento en el décimo. ¿Por qué lo hace?"

Pues nada, a entretenerse y (espero) que hasta el Domingo que viene.

viernes, 19 de agosto de 2016

El desorden completo es imposible

Trivial pero sorprendente: El Principio del Palomar

El principio del palomar o principio de Dirichlet, establece que si n palomas se distribuyen en m palomares, y si n > m, es decir, hay más palomas que palomares, al menos habrá un palomar con más de una paloma. Hasta aquí todo bien, no hemos descubierto la cuadratura del circulo, ya que lo que básicamente dice este principio es que si tenemos un determinado número de huecos (llamemos a este número m) para almacenar un determinado número de objetos (digamos por ejemplo un número n de objetos) si el número de objetos, n, es mayor que el número de huecos, m, necesariamente habrá un hueco con al menos dos objetos. 

A priori este resultado puede parecer trivial (de hecho lo es), ya que tan siquiera necesita demostración debido precisamente a su simplicidad, pero es un principio muy potente con aplicaciones en campos tan diversos como la teoría de grafos, combinatoria, ciencias de la computación, teoría de números, etcétera.

De la mano de este principio podemos demostrar cosas muy interesantes, por ejemplo, la cantidad de pelos en la cabeza va desde cero hasta unos 100.000 ó 150.000 (considerando solo el cuero cabelludo y según lo que dice nuestra querida amiga Wikipedia) y para curarnos en salud vamos a pensar que existe alguien híper-peludo con 1.000.000 de pelos en la cabeza. Aplicando el principio del palomar tenemos que como en España hay unos 46 millones de personas (estas serían las palomas) y que podemos tener gente con cero pelos hasta 1.000.000 (estos son los palomares, es decir, desde el palomar en el que clasificamos a la gente con cero pelos hasta la gente híper-peluda con 1.000.000 de pelos) necesariamente al menos dos personas tienen exactamente el mismo número de pelos, no solo en España, en cualquier país con más de un millón de habitantes. 

Sin embargo, no solo podemos garantizar que al menos dos personas tendrán el mismo número de pelos en la cabeza, podemos ir más allá. Dividiendo m/n obtenemos una aproximación más real del número mínimo de personas que deben compartir número de pelos en la cabeza (o palomas que comparten palomar). Entonces dividiendo la población de España (46 millones) entre el número de pelos (1 millón) tenemos que hay al menos 46 personas que comparten palomar, es decir, que tienen exactamente el mismo número de pelos en la cabeza.

Un paso más allá: Teoría de Ramsey

Como ya se podría apreciar en el título de esta entrada, el desorden completo es muy difícil (sino imposible) de conseguir. Por ejemplo, en la siguiente imagen, los puntos que aparecen han sido generados de manera aleatoria (20 puntos con sus coordenadas x e y generadas al azar mediante la función ALEATORIO() de Excel). Sin embargo, es fácil encontrar algunos patrones como cuadrados, cruces, puntos que se hayan por debajo de un nivel, zonas monótonamente crecientes, monótonamente decrecientes, etcétera.

De esto mismo se dio cuenta el matemático Frank P. Ramsey, y estudió las condiciones mínimas bajo las cuales el orden debe aparecer. En su honor, la teoría lleva su nombre. Los problemas de esta teoría son de la forma: ¿Cuántos elementos debe contener una estructura para garantizar la existencia de una propiedad particular?. Dicho de otra manera, cuando un conjunto es lo suficientemente grande, podemos encontrar patrones (orden) dentro de dicho conjunto.


Al observar la gráfica anterior la sensación es similar a cuando observamos un cielo estrellado lejos de la gran ciudad para evitar la contaminación lumínica. Si hay suficientes estrellas siempre podremos hacer todo tipo de formas geométricas tales como un triangulo, un cuadrado, etcétera. En este sentido, un resultado es el denominado problema del final feliz nombrado así por Paul Erdős. Este problema representa uno de los primeros resultados de la teoría de Ramsey y dice así:

"Cualquier conjunto de 5 puntos en el plano en posición general (no colineales) tiene un subconjunto de 4 puntos que son los vértices de un cuadrilátero convexo".

Cabe resaltar que existen otros problemas con resultados sorprendentes de la teoría de Ramsey, como el Teorema de Ramsey Infinito que nos dice que si tenemos un conjunto infinito y distribuimos sus elementos en un número finito de cajas, entonces hay una caja que contiene infinitos elementos.
Otro resultado interesante es el Teorema de Bolzano, en este caso el teorema enuncia: Toda sucesión infinita de números reales contiene una subsucesión infinita creciente o decreciente.

Y mi favorito, el Teorema de la Amistad, cuyo enunciado es el siguiente: Supongamos que en una fiesta hay seis personas. Consideremos a dos personas cualesquiera de estas seis. Puede ser que estas dos personas no se conozcan, en cuyo caso los llamaremos mutuamente extraños. Por otra parte es posible que estas dos personas ya se conocieran, en cuyo caso los llamaremos mutuamente conocidos. Ahora el Teorema de la Amistad dice:

"En cualquier grupo de seis personas existen tres personas que son  mutuamente conocidas o mutuamente desconocidas".

Para demostrar esto vamos a tirar de una vieja conocida en este blog, la teoría de grafos. En nuestro grafo, cada uno de las personas de la fiesta será un vértice, denotaremos si estos son mutuamente conocidos con una línea verde, si por el contrario son mutuamente desconocidos estableceremos la conexión entre esas dos personas mediante una línea roja. El siguiente grafo muestra una de las posibles combinaciones.


Una forma de comprobar el resultado es mediante fuerza bruta (algo muy común en problemas de Teoría Ramsey), en otras palabras, evaluando los 78 grafos posibles. No obstante en este caso disponemos de una alternativa más eficiente gracias a la teoría de grafos.

Sobre cualquier vértice del grafo inciden 5 aristas, que pueden ser de color rojo o de color verde. Según el principio del palomar, al menos tres aristas tienen el mismo color (que es lo que nos dice el teorema), ya que si hay menos de tres aristas de un color, digamos verde, necesariamente habrá al menos tres del color contrario, rojo.

Para terminar esta entrada, voy a tirar de una de esas frases que muchos (me incluyo) empleamos cuando alguien nos cambia algo de sitio: "Déjalo como esta que yo entiendo mi orden". Ahora la podemos decir con más razón aún. 

jueves, 4 de agosto de 2016

¿De dónde viene el nombre de Google?

Un matemático de paseo con su sobrino

Edward Kasner fue un matemático estadounidense que realizó sus mayores aportaciones matemáticas al campo de la geometría diferencial en el espacio euclídeo. Sin embargo, la aportación por la cual es más conocido es por una explicación de matemáticas elementales sobre el infinito mediante un número ideado por su sobrino, el gúgol (googol, en inglés). Durante un paseo, Edward Kasner le pidió a su sobrino Milton Sirotta (de tan solo 9 años de edad) acerca del nombre que deberían darle a un número muy, muy grande, un uno seguido de cien ceros, a lo que el niño contesto "Googol". Kasner decidió mencionar este número en un libro llamado Matemáticas e imaginación.

$$1\quad gúgol\quad =\quad { 10 }^{ 100 }$$

La idea de este número es que por muy grande que fuese, en este caso un uno seguido de cien ceros, debería de tener un nombre puesto que este número aún se encontraba muy lejos del infinito. De modo que el niño decidió pensar en un número aún mayor, aunque finito, el googolplex, que inicialmente definió como un uno seguido de tantos ceros como la persona pudiera escribir antes de cansarse. Pero como en matemáticas nos gustan las definiciones estándar (y resulta que hay personas que se cansan de escribir antes que otras), Kasner decidió poner un límite a este número, y un gúgolplex sería un uno seguido por un gúgol de ceros. Para que nos hagamos una idea del tamaño de este número, si colocásemos todos los ceros de un gúgolplex en línea sobre una hoja de papel dicha hoja no entraría dentro del universo conocido. Y aún así, este número seguirá siendo finito. 

$$1\quad gúgolplex\quad =\quad { 10 }^{ gúgol }={ 10 }^{ { 10 }^{ 100 } }$$

Estos números no tienen ninguna aplicación práctica, su único interés reside en precisamente explicar el concepto de infinito, puesto que por propia definición el infinito hace referencia precisamente a una cantidad sin limite o final. Por tanto es mas grande que cualquier cantidad numérica que podamos imaginarnos, y eso que existen números monstruosamente grandes como el número de Graham, el cual es tan grande que no puede ser escrito utilizando notación matemática convencional.

Dos estudiantes de posgrado muy optimistas

En 1996, dos estudiantes de posgrado en ciencias de la computación en la Universidad de Stanford comenzaron un proyecto para conseguir un buscador alternativo al de la época, AltaVista, el cual había sido creado en 1995. El nombre originario de este buscador era BackRub, pero sus creadores, Larry Page y Serguéi Brin decidieron cambiarle el nombre a Google, inspirados por el término matemático googol, pues esperaban conseguir organizar la gran cantidad de información de la web con su buscador. Asimismo las oficinas de Google son conocidas como Googleplex, haciendo clara referencia al número gúgolplex, remarcando de nuevo el afán de organizar la gran cantidad de información disponible en Internet. 

lunes, 11 de julio de 2016

¿Cuáles son las probabilidades de ganar los Euromillones?

¿Cuántas probabilidades tengo de ganar?

Para calcular las probabilidades de que nos toquen los Euromillones primero tenemos que saber cuantas combinaciones posibles existen, puesto que jugamos una (o varias) de esas combinaciones. En este pequeño artículo, vamos a suponer que jugamos un único boleto de Euromillones, es decir, una combinación. 

Las posibles combinaciones de n elementos sin repetición se calculan con lo que en matemáticas se conoce como factorial, que se define formalmente como: 

$$ n!\quad =\quad n·(n-1)·(n-2)·...·1 $$

En esencia, la formula de arriba nos dice que para calcular el factorial de un número natural n, debemos multiplicar todos los números naturales desde 1 hasta n. Por ejemplo, el factorial de 4 se escribe 4! (leído "cuatro factorial") y se calcula como 4! = 4·3·2·1 = 24

Ilustremos la relación entre el factorial y las combinaciones con un ejemplo. Si tenemos 4 tarjetas de colores, digamos una roja, una azul, una verde y una amarilla, existen 24 posibles formas de combinarlas siguiendo un orden específico y sin repetición (un orden específico sin repetición podría ser: amarillo/verde/rojo/azul; quedarían otras 23 combinaciones posibles).

Ahora bien, en los Euromillones tenemos 50 números de los cuales elegimos 5, y 11 estrellas de las cuales elegimos 2. Las probabilidades de obtener un subconjunto determinado de k elementos de un conjunto de n elementos se calcula con lo que se conoce como el coeficiente binomial, que se define según la siguiente fórmula:

$$ \left( \begin{matrix} n \\ k \end{matrix} \right) =\frac { n! }{ k!(n-k)! } $$

Con la cual ya podemos calcular cuantas combinaciones existen a la hora de escoger 5 números de los 50 totales, y 2 estrellas de las 11 totales. 

Número de combinaciones de números:

$$ \left( \begin{matrix} 50 \\ 5 \end{matrix} \right) =\frac { 50! }{ 5!·(50-5)! } =\frac { 50! }{ 5!·45! } =2.118.760 $$

Número de combinaciones de estrellas:

$$ \left( \begin{matrix} 11 \\ 2 \end{matrix} \right) =\frac { 11! }{ 2!·(11-2)! } =\frac { 11! }{ 2!·9! } =55 $$

Entonces, dado que a cada combinación de números, le corresponde una única combinación de estrellas, tenemos que el número total de combinaciones posibles es el producto de ambos números de combinaciones (números y estrellas). Luego,

Número total de combinaciones:

2.118.760·55 = 116.531.800

Por lo tanto, si nosotros jugamos una única papeleta o boleto, la probabilidad de que nos acabemos llevando los millones es de una entre unos cien millones, concretamente de: 

$$ P(Ganar\quad Euromillones)=\frac { 1 }{ 116.531.800 } $$

Yo siempre juego el mismo número, ¿tengo más posibilidades de que me toque?

Supongamos que jugamos durante 100 años la misma combinación, pues "tarde o temprano tiene que salir". Esta forma de pensar es, en parte (y solo en parte...), acertada y está basada en el concepto frecuentista de la probabilidad.

Pensemos en una moneda, si la moneda está equilibrada, existe la misma probabilidad de que salga cara que cruz. Si hacemos 10 lanzamientos completamente aleatorios, puede que nos salgan 3 (30%) caras y 7 (70%) cruces, lo cual no se parece mucho a nuestra hipótesis inicial, la cual nos dice que deberían de ser 5 caras (50%) y 5 cruces (50%). Si hacemos 100 lanzamientos, es más probable que estemos más cerca de la situación teórica. Y si hacemos 1.000 estaremos aún más cerca (y más con 10.000, y más con 100.000, y así hasta que lleguemos a eso que llamamos infinito).

El concepto frecuentista de la probabilidad se basa en el empirismo, ya que la experiencia nos dice que la frecuencia relativa de un suceso (por ejemplo que salga cara) tiende a estabilizarse cuando la frecuencia total aumenta (número de lanzamientos de moneda que realizamos). Por ello, cuantos más lanzamientos hacemos, más nos vamos acercando a la probabilidad teórica (50/50). En el caso de los Euromillones todas las combinaciones tienen (a priori) la misma probabilidad de ocurrir, por tanto si jugamos infinitas veces, tarde o temprano saldrá nuestro boleto y seremos premiados.

Sin embargo, jugar durante 100 años, no nos da probabilidades extra de ganar nuestro boleto.  ¿Por qué? volvamos a nuestra moneda. Supongamos la siguiente situación, lanzamos la moneda y obtenemos cara, volvemos a lanzar y volvemos a obtener cara, volvemos a lanzar y volvemos a obtener cara, y lanzamos por última, y cuarta vez, y obtenemos de nuevo cara. Ahora te pregunto: ¿A que quieres apostar que saldrá en el quinto lanzamiento, cara o cruz? Si has contestado cruz pensando, "ya toca" tienes razón, pero solo en términos frecuentistas. Existe una error muy común que es el de confundir la probabilidad de obtener 5 caras seguidas, la cual es 1 entre 32:

$$ P(5\quad caras\quad seguidas)\quad ={ \left( \frac { 1 }{ 2 }  \right)  }^{ 5 }=0.03125 $$

Con la probabilidad de obtener cara en el quinto lanzamiento, que es la misma que la de obtener cara en cualquier lanzamiento (1/2), dado que cada lanzamiento es independiente de lo que haya ocurrido en el lanzamiento anterior (o lanzamientos anteriores).

Un experimento que sí depende de lo ocurrido anteriormente (dependiente) puede ser un saco con 5 bolas negras y 5 bolas blancas. De inicio, al sacar una bola, existe la misma probabilidad (5 entre 10) de que esta sea blanca o negra, pero si continuamos sacando bolas sin reponerlas hasta agotarlas, las probabilidades de obtener una bola u otra dependerán de las extracciones anteriores.

En definitiva, jugar el mismo número durante 100 años no aporta ninguna ventaja adicional.

Extra: un "pequeño" cambio

En 2011 se decidió cambiar el número de estrellas de 9 a 11 (en ambos casos el jugador selecciona 2). A priori este cambio no parece tener grandes implicaciones, pero ya que sabemos calcular las probabilidades, veamos cuantas combinaciones extra incluyó este cambio. 

Número de combinaciones de estrellas (Caso: 9/2):

$$ \left( \begin{matrix} 9 \\ 2 \end{matrix} \right) =\frac { 9! }{ 2!·(9-2)! } =\frac { 9! }{ 2!·7! } =36 $$

Los números son los mismos, 50 a elegir 5. Por lo tanto para calcular las todas las posibles combinaciones con 9 estrellas procedemos del mismo modo que anteriormente multiplicando todas las combinaciones posibles de números por todas las posibles combinaciones de estrellas:

2.118.760·36 = 76.275.360

Pues parece que este cambio introdujo unas "cuantas" combinaciones extra, de hecho unos 40 millones de combinaciones extra (exactamente 40.256.440). Lo sorprendente de este resultado es su que parece ir en contra de la intuición, pues es difícil suponer que la inclusión de dos estrellas en el bombo (y en el boleto) pueda incrementar de manera tan bestial las posibles combinaciones, y en consecuencia reducir considerablemente las probabilidades de acertar.  

domingo, 10 de julio de 2016

Maneras complicadas de ganar un millón (I): P vs NP

Los problemas del milenio

Existen siete problemas matemáticos conocidos como "los Problemas del Milenio". Estos siete problemas fueron anunciados por el Instituto Clay de Matematicas, anunciando además que premiaría su resolución con "la respetable suma" de un millón de dolares. Estos problemas fueron seleccionados por una comisión de expertos, quiénes valoraron que su resolución repercutirá en todos los ámbitos del progreso de la humanidad.  

A día de hoy solo uno de estos problemas ha sido resuelto, la hipótesis de Poincaré (hablaremos de el).  Este es el primero de una serie de siete artículos que pretenden mostrar de la manera "más simple posible" (si es que existe una manera simple de presentarlos) cada uno de los siete Problemas del Milenio. 

P vs NP

Solucionar no es lo mismo que verificar una posible solución. Bajo esta afirmación se sustenta todo el problema de P vs NP. Es una tortura calcular una raíz cuadrada a mano, por ejemplo calcular la raíz de 961, no obstante es inmediato elevar 31 al cuadrado y comprobar que efectivamente 312 = 961.

Entonces la pregunta que nos ocupa es la siguiente: ¿Las cuestiones que pueden verificarse en un tiempo razonable pueden también resolverse en un tiempo razonable?.

Hagamos otro ejercicio. Pensemos en un número y en un posible divisor exacto de ese número, es inmediato comprobar si el citado número es divisor exacto o no (simplemente realizando la división). Pero si nos pidiesen que dado un número encontrásemos sus factores primos, esto ya es otra cosa, sobretodo si ese número es muy grande. De hecho al dificultad de encontrar factores primos en números muy grandes es tal, que en eso se basa la criptografía actual, por ejemplo intenta descomponer el número 3.579.194 (está escogido con muy mala leche..., ver final del post). 

Llamando P al conjunto de problemas solucionables en un tiempo razonable y NP al conjunto de problemas verificables en un tiempo razonable, el Instituto Clay propone el problema: 

¿Es P = NP?

Pero ¿qué es un tiempo razonable?, o mejor dicho, ¿cuánto es un tiempo razonable?. Para entender esto tenemos que adentrarnos un poco en la teoría de algoritmos.

Algoritmos

Un algoritmo no es más que un conjunto de finito de reglas o instrucciones bien definidas para realizar una actividad. Por ejemplo para llenar un vaso de agua, este podría ser el algoritmo (es uno de muchos, esto se puede complicar tanto como se quiera):

1. Coger la botella de agua.
2. Quitar tapón de la botella.
3. Coger un vaso vacío.
4. Echar agua en el vaso hasta que este lleno, cuando el vaso este lleno, dejar de echar agua.
5. Cerrar botella con el tapón.

Al final, casi todo lo que hacemos puede ser reducido a un algoritmo, la cosa es que este algoritmo puede o no ser eficiente, ya que (¡sorpresa!), un algoritmo depende de la "cantidad" de datos de entrada. Por decirlo de manera entendible, en este caso, el tamaño importa.

Para ilustrar esto, imaginemos el siguiente problema:

Un determinado virus ha sido liberado en un laboratorio, infectando a un investigador, sin que él lo sepa. Ese mismo día tiene la cena de navidad con el resto de compañeros. El virus que ha contagiado se multiplica por 3 cada hora, es decir, afecta a otros tres individuos cada hora. Hasta el día siguiente nuestro colega investigador no se da cuenta de que ha sido infectado. Han pasado 24 horas. ¿A cuantas personas puede haber contagiado?

El investigador comienza sus cálculos del siguiente modo:
En la primera hora (t = 1) infectará a 3 personas, en la segunda (t = 2) el investigador podrá infectar a otras tres,pero además cada una de las 3 personas infectadas en la primera hora, tendrá la capacidad de infectar a otras tres, es decir, tenemos 9 posibles infectados solo por los tres infectados iniciales... A las 12 horas (t = 12) el número de infectados asciende a 531.441. Puesto que han pasado 24 horas desde la cena (t = 24) el número de personas potencialmente infectadas es de nada más ni nada menos que 282.429.536.481. Efectivamente, este tipo de crecimiento es exponencial, y enseguida nos percatamos de su rápido crecimiento (NOTA: esto es solo un ejemplo para ilustrar el crecimiento exponencial, la propagación de virus tiene en cuenta otros muchos factores).

$$ N={ 3 }^{ t } $$

El tiempo de ejecución de algunos algoritmos crece de forma exponencial en función del "tamaño/longitud" de sus datos de entrada. Esto es un problema muy serio en computación, puesto a poco grande que sea nuestra cadena de entrada, el tiempo va creciendo cada vez más, hasta volverse inabordable en un tiempo razonable (podría tardar siglos en computarse el algoritmo), incluso para el ordenador más potente. Sin embargo, el crecimiento exponencial no es tan temible como el crecimiento combinatorio. La siguiente gráfica muestra tipos de crecimiento, podemos ver que el combinatorio es mayor que el exponencial:



Por otra parte, el crecimiento combinatorio no es el mayor, puesto que es superado por:

$$ f(n)={ n }^{ { n }^{ n } } $$

Y este a su vez vuelve a ser superado por:

$$ f(n)={ n }^{ { n }^{ { n }^{ n } } } $$

Y mediante esta relación recursiva podríamos seguir así hasta el infinito.

Un problema dado puede ser resuelto mediante varios algoritmos. Por ejemplo el problema de ordenamiento puede ser resuelto en un tiempo O(n2) si consideramos el algoritmo Bubblesort y en un tiempo O(n·log(n)) si consideramos Merge sort. Por tanto es inmediato ver que si queremos resolver el problema de ordenamiento lo más eficiente es utilizar merge sort, puesto que tiene un tiempo menor (número de pasos a seguir es del orden de n·log(n), donde n es la longitud de la cadena de entrada).

Definiciones "formales"

Y aquí viene la primera definición. ¿qué problemas consideramos P? Básicamente P son todos los problemas abordables en un tiempo polinómico, es decir, que pueden resolverse en un número de pasos del orden nk, siendo n la longitud de la cadena de entrada y k un número natural.
Esta definición es demasiado formal, porque ¿qué pasa si   k = 1.000?, el tiempo sería demasiado, aunque fuera polinómico. En la práctica se considera un tiempo polinómico todo aquel del orden O(n5), es decir, k = 5 (intuitivamente los programadores suelen buscar algoritmos mejores que O(n2)).

Y por supuesto,la definición de NP. Los problemas NP son aquellos en los que comprobar la repuesta nos llevaría un tiempo polinómico. Es decir, en este caso el algoritmo busca esa posible solución, no soluciona el problema per se. Dicho de otro modo, existe cierta influencia del azar, pues en algún momento del algoritmo habrá que considerar una solución potencial (y esta será tomada de manera más o menos aleatoria o bajo influencia del azar, en mayor o menor medida), y luego en etapas posteriores comprobar dicha solución. Si el tiempo de comprobación es polinómico, diremos que estamos ante un problema NP.

Una parte está clara, P esta contenido en NP, es decir,

$$ P\subseteq NP $$

Puesto que podemos pensar en el algoritmo que resuelve un problema P en un tiempo polinómico también como el algoritmo de comprobación de resultado.

Y aquí volvemos al inicio del post, ¿es P = NP?, es decir, ¿Si podemos verificar las respuestas de un problema  del tipo SI/NO (problema de decisión) en un tiempo razonable (polinómico), también podemos obtener las respuestas en un tiempo razonable (polinómico)?

Los expertos en el tema son bastante escépticos, y se inclinan más por la posibilidad de que P no sea igual a NP. Y motivos para ello hay.

Consecuencias de P = NP

Supongamos por un instante que se demuestra que, efectivamente, P = NP. Los ordenadores podrían llevar a cabo tareas que hoy en día son inabordables, como que un ordenador juegue al ajedrez de forma perfecta (con la infinidad de combinaciones y jugadas posibles desde el estado inicial que eso conlleva), los computadores traducirían de forma simultánea y mejor que un traductor humano, la inteligencia artificial sería posible, pues podríamos realizar búsquedas masivas en tiempos polinómicos, etc. 

Todos estos son algoritmos que en la actualidad son inabordables en un tiempo polinómico, como el problema del viajero, donde se quieren recorrer un conjunto de ciudades pasando por todas ellas y haciendo el menor recorrido en distancia posible. Parece que no hay otra solución que la fuerza bruta (comprobar todas las posibles soluciones). 

En este sentido hay una implicación más de índole filosófica. Es mucho más difícil diseñar un avión que comprobar que está bien diseñado, al igual que es más sencillo comprobar que una demostración matemática es correcta que idear la propia demostración (que le pregunten a Andrew Wiles, quien tras 8 años de aislamiento resolvió el último teorema de Fermat, el cual llevaba sin resolverse desde 1637, prometo hablar de él en otra ocasión). 

Esta sería la última frontera, donde perderíamos toda creatividad, algo que, si bien suena aterrador, según los expertos parece poco probable. Aunque quien sabe, tal vez las máquinas puedan superar algún día el Test de Turing...



PD: El número 3.579.194 no es primo, su descomposición en factores primos es 2·1.789.597.