Notición: Graph Isomorphism en quasiP?

B

http://www.scottaaronson.com/blog/?p=2521

Rumores, rumores. Se dice que el informático László Babai en una conferencia el próximo martes explicará cómo se resuelve el problema del isomorfismo de grafos en tiempo cuasi polinómico. El mejor resultado hasta ahora (del mismo autor) era capaz de resolver el problema de saber si un grafo es isomorfo a otro en (e{\sqrt{n \log n}}), y ahora parece que lo tiene en (e{\text{polylog} n}), que es casi un tiempo polinómico.

Esto no arreglaría en nada la pregunta P!=NP, pero estaría al nivel del descubrimiento de que PRIMES es P.

Un poco de explicación:

Un grafo no es más que una colección de vértices y aristas (que conectan los vértices). Dos grafos son isomorfos si podemos reetiquetar los vértices de uno de manera que encaje perfecto con el otro (siempre y cuando se conserven las conexiones entre vértices, claro). Este problema lleva desde los 80 sin saberse si es NP o es P, y este resultado parece que lo situa muuy cerca de P.

Polylog es una función que crece un poco más rápido que el logaritmo pero no tanto como un polinomio. Es un poco técnico y hasta que no salga la conferencia y sus posteriores análisis no puedo dar más detalles (porque no los conozco, no porque sea un secreto xD), pero este es uno de los resultados en teoría de la computación más importantes de los últimos 10 años.

Aplicaciones tiene muchas por cierto para los fans del "y pa qué sirve esto". Desde saber si dos capturas de moléculas son de la misma molécula (aunque esté retorcida, girada, o entrelazada), hasta simplificación de problemas de logística o geociencias o lo que queráis. Compiladores, verificación de demostraciones por ordenador, pf, muchas cosas xD.

7
Javimorga

Esto que quiere decir: ¿que el tío ha hecho un algoritmo que lo resuelve en quasyP? ¿O que ha demostrado que puede resolverse en quasyP?

1 respuesta
B

#2 ha hecho un algoritmo que explicara el martes que viene! Es posible que no sea eficiente de implementar (en plan tiene un overhead tan bestia que cuando se empiece a notar la mejora respecto al que se usa ahora sea cuando los tiempos ronden la edad del universo xD) pero aun así nos permitirá entender mucho mejor los problemas y cómo solucionarlos.

Creo que somos el primer foro en español que recibe la noticia así que más os vale fardar con los coleguis :P .

2 respuestas
Millonet1

Jajajaja #3, tenemos conexión en directo con Princeton.

PD: ¿que desayunan los húngaros?

1 respuesta
B

#4 anfetas

4 1 respuesta
W

Me encanta sentirme así de retrasado.

Mi cara leyendo el primer párrafo: http://38.media.tumblr.com/907e41d3f0c26bd113b6a60023cf889c/tumblr_njzfsuaijd1s9y3qio2_250.gif

13 1 respuesta
B

#6 Hay algo en particular que pueda intentar esclarecer??

NueveColas

#5 ¿Pero no se supone que come café y caga con dolor por culpa de las hemorroides de tomar tanto café?

BTW, con este algoritmo... ¿la seguridad y encriptación con primos puede resentirse?

1 respuesta
B

#8 nah, ni con este ni con el de saber si un numero es primo o compuesto. Nadie ha usado el problema de isomorfismo de grafos para encriptar nada porque es muy chungo encontrar el "caso peor" (en cambio encontrar 2 numeros primos de muchas cifras que esten muy cercanos no es tan chungo) asi que un algoritmo cutrillo tipo una heuristica o incluso aleatorizado se lo sacaria rapido.

En cambio el problema de encontrar un subgrafo (tienes un grafo de n vertices y uno de m<n y quieres ver si el segundo es parte del primero) si que es NP-completo, y quizas este descubrimiento ayude a entender mejor el otro problema (o quizas no, realmente sobre los problemas sabemos muy poco, poquisimo).

1 respuesta
NueveColas

#9 Ah vale. Creía que AES se podía usar con grafos (hace la ostia que no miro estas cosas). Sobre los problemas de complejidad pues ni flowers, ya sabes que soy un lego de la ostia a estos niveles.

Edit: ahora que estoy leyendo un poco me parece extremadamente interesante

1 respuesta
mTh

Creo que es quasi no quasy pero no me hagas mucho caso.

Ahora que estoy con las últimas correcciones, detecto typos en inglés con los ojos cerrados.

Por vibraciones de la fuerza o algo.

1 respuesta
B

#11 tienes razon, sorry, voy a pedir que lo cambien. Me lie con polylog que no es polilog xD.

B

es hoy el anuncio entonces?

2 respuestas
B

#13 Hoy da la conferencia Babai dentro de unas horas, espero que salga algo y lo comento...

edit: De momento no hay info..

1
B

#13
https://storify.com/ptwiddle/babai-s-first-graph-isomorphism-talk
https://plus.google.com/+TimothyGowers0/posts/JbSPELbKQED

Traduciré ASAP.

#10 en este link mismo lo comenta: Es muy difícil encontrar grafos difíciles de "isomorfizar" con heurísticas simples. Con lo cual es impráctico hacer criptografía con este problema. El algoritmo no es práctico tampoco, los algoritmos actuales van más rápido en la mayoría de casos (para que este algoritmo fuera más rápido en la práctica, los tiempos tendrían que ser del orden de la edad del universo así que tampoco nos importa mucho xD). Lo mismo pasa con los algoritmos para saber si un número es primo o no, es mejor usar algoritmos aleatorizados que el algoritmo polinómico que se conoce.

1
T-1000

Y qué función tiene esto?

2 respuestas
B

#16 Desde saber si dos capturas de moléculas son de la misma molécula (aunque esté retorcida, girada, o entrelazada), hasta simplificación de problemas de logística o geociencias o lo que queráis. Compiladores más rápidos, verificación de que los algoritmos funcionan...

Si logramos entender bien este problema lograremos también entender mucho mejor todos los de arriba.

B

#16

En #1 tienes la explicación.

Un grafo está compuesto de vértices y aristas: https://en.wikipedia.org/wiki/Graph_(mathematics)

A cada vértice y a cada arista le pones una etiqueta/nombre, normalmente a los vértices se les pone un número natural {1, 2, 3, 4...} y a las aristas se les pone los vértices que enlazan {(1,2), (2, 3), (3, 1)....} . Por supuesto puedes inventarte la notación más bizarra del mundo, pero entonces te costará más comunicarte con otras personas :P.

Imagínate que tienes un triángulo. Entonces tienes tres vértices {1, 2, 3} y tres aristas {(1,2), (2,3), (3,1)}. Dibuja ese triángulo en el papel y pon los nombres encima. Ahora imagina una serie de transformaciones, cómo cambiar los nombres, por ejemplo {2, 3, 5} (y sus correspondientes aristas), o rota/translada en el papel el triángulo de los nombres originales...

El colega no importa cómo lo llames, cómo lo rotes, cómo lo translades... al final es siempre un triángulo! Tu cerebro eso lo puede resolver fácil, simplemente mirándolo en el papel xD, pero y cómo puede hacer eso una máquina? Ahí es dónde entra la aplicación de este tipo de herramientas.

Ahora imagina que no tienes un triángulo, si no que tienes un objeto random que puede ser descrito con una grafo, cómo una molécula o una red de transporte. Si dos objetos comparten el mismo grafo, también comparten las mismas propiedades relacionadas con el mismo!

Cómo curiosidad, el primer problema relacionado con grafos del que se tiene constancia fue
https://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

precisamente sobre red de transportes y resuelto por Euler :P

3
Zerokkk

#3 Pero, todo esto sin aplicar reducciones, no? Es decir, sin tratarlo como si inicialmente fuera un problema NP, no?

No conocía este tipo de problemas, pero desde luego me parece una buena noticia que se demuestren ser P o quasi-P.

2 respuestas
B

#19 los problemas no se tratan de manera distinta si son NP o no , no entiendo tu pregunta!

Han salido novedades, comentare ma;ana.

Corwils

#19 Si no lo he leído mal, no ha dado ninguna reducción si no que ha dado directamente un algoritmo para decidir el problema de isomorfismo de grafos en tiempo quasiP.

Aunque releyendo el link en #1 creo que su algoritmo decide un problema más general y luego demuestra que decidir si dos grafos son isomorfos se reduce a este problema más general

1 1 respuesta
B

#21 eso son las novedades, ya me has chafado el spoiler :P (es bromi). Exactamente eso es lo que hace.

B

Mas info: http://blogs.ams.org/blogonmathblogs/2015/11/16/meanwhile-over-in-computer-science/

Lamento no traducir, estoy hasta el cuello.

Usuarios habituales