Los científicos informáticos están
entusiasmados con un nuevo algoritmo rápido para resolver uno de los problemas
centrales en el campo.
La pregunta
"gráfico isomorfismo" simplemente pregunta si dos redes que se ven
diferentes son realmente iguales.
Michael Sollami para la revista Quanta
Un científico de la computación teórica ha presentado un
algoritmo que se considera un avance en el mapeo del oscuro terreno de la
teoría de la complejidad, que explora la dificultad de resolver los problemas
de cómputo.
El mes pasado, László Babai , de la Universidad de Chicago, anunció
que había ideado un nuevo algoritmo para el problema del “gráfico isomorfismo”, uno de los misterios más tentadores de la
informática.
El nuevo algoritmo parece ser mucho más eficiente que el
mejor algoritmo anterior, que había mantenido el registro durante más de 30
años.
(Actualización del 15 de enero de 2017: el 4 de
enero, Babai retiró su reclamo de que el nuevo algoritmo se ejecuta en un
tiempo casi polinomial y cinco días después anunció que había corregido el
error. Lea más en el blog de Abstractions).
Durante décadas, el problema del isomorfismo gráfico ha
mantenido un estatus especial dentro de la teoría de la
complejidad. Mientras miles de otros problemas computacionales han
sucumbido dócilmente a la categorización, ya sea duro o fácil, el isomorfismo
gráfico ha desafiado la clasificación. Parece más fácil que los problemas
difíciles, pero más difícil que los problemas fáciles, ocupando una especie de
tierra de nadie entre estos dos dominios.
Es uno de los dos problemas más famosos en esta extraña área
gris, dijo Scott Aaronson, un
teórico de la complejidad en el Instituto de Tecnología de
Massachusetts. Ahora, dijo, "parece
que uno de los dos puede haber caído".
El legendario problema del isomorfismo en la
gráfica puede ser más difícil de lo que parece sugerir un resultado de 2015.
El anuncio de Babai ha electrificado a la comunidad teórica
de la informática. Si su trabajo resulta correcto, será "uno de los grandes resultados de la
década, si no las últimas décadas", dijo Joshua Grochow , científico informático del Instituto de
Santa Fe.
Los científicos informáticos utilizan la palabra "gráfico" para referirse a una
red de nodos con bordes que conectan algunos de los nodos.
La pregunta sobre el isomorfismo de la gráfica simplemente
pregunta cuándo dos gráficas son realmente la misma gráfica disfrazada porque
hay una correspondencia uno a uno (un "isomorfismo") entre sus nodos
que preserva las formas en que se conectan los nodos.
El problema es fácil de plantear, pero es difícil de resolver,
ya que incluso los pequeños gráficos pueden verse muy diferentes simplemente
moviendo sus nodos alrededor.
Ahora, Babai ha dado lo que parece ser un gran paso adelante
para determinar el nivel de dificultad del problema, al establecer lo que
afirma es un algoritmo de "tiempo casi polinomial" para
resolverlo.
Como lo describe Aaronson, el algoritmo coloca el problema
dentro de "el área metropolitana
mayor" de P, la clase de problemas que se pueden resolver de manera
eficiente. Si bien este nuevo trabajo no es la última palabra sobre cuán
difícil es el problema del isomorfismo de la gráfica, los investigadores lo ven
como un factor de cambio de juego. "Antes
de su anuncio, no creo que nadie, excepto tal vez por él, pensara que este resultado
iba a suceder en los próximos 10 años, o tal vez nunca", dijo Grochow.
László Babai anunció su algoritmo de isomorfismo gráfico en la
Universidad de Chicago el 10 de noviembre. Jeremy Kun
En las últimas semanas, Babai dio
cuatro charlas que describían su algoritmo. Sin embargo, tomará tiempo
para que su nuevo documento sea examinado por otros expertos.
Babai se negó a hablar con la prensa
y escribió en un correo electrónico: "La
integridad de la ciencia requiere que los nuevos resultados sean sometidos a
una revisión exhaustiva por parte de colegas expertos antes de que los
resultados se publiquen en los medios".
Otros investigadores tienen una
cautelosa esperanza de que su prueba saldrá bien. "Babai tiene un record excelente", dijo Aaronson. "Es tan confiable como ellos
vienen".
"Creo
que la gente es bastante optimista",
dijo Luca Trevisan , científica informática de la
Universidad de California en Berkeley, después de la segunda charla de
Babai. “Suponiendo que la prueba sea
correcta”, dijo, "es un
resultado histórico".
Una
prueba de sabor a ciegas
Dados dos gráficos, una forma de
verificar si son isomorfos es
simplemente considerar todas las formas posibles de hacer coincidir los nodos
en un gráfico con los nodos en el otro.
Pero para los gráficos con n nodos,
el número de emparejamientos diferentes es n factorial (1* 2*
3*… * n ), que es mucho mayor que n que este
enfoque de fuerza bruta es irremediablemente impráctico para todos, excepto
para los gráficos más pequeños. Para gráficos con solo 10 nodos, por
ejemplo, ya hay más de 3 millones de coincidencias posibles para
verificar. Y para los gráficos con 100 nodos, el número de posibles
emparejamientos supera con creces el número estimado de átomos en el universo
observable.
Los científicos informáticos
generalmente consideran que un algoritmo es eficiente si su tiempo de ejecución
puede expresarse no como un factorial sino como un polinomio, como n 2 o n 3; Los
polinomios crecen mucho más lentamente que los factoriales o las funciones
exponenciales, como 2 n. Se dice que los problemas
que tienen un algoritmo de tiempo polinomial están en la clase P, y durante las
décadas desde que se propuso esta clase, se ha demostrado que miles de
problemas naturales en todas las áreas de la ciencia y la ingeniería le
pertenecen.
Los científicos de computación
piensan que los problemas en P son relativamente fáciles, y piensan que los
miles de problemas en otra categoría, "NP-completo",
son difíciles. Nadie ha encontrado nunca un algoritmo eficiente para un
problema de NP completo, y la mayoría de los científicos informáticos creen que
nadie lo hará. La cuestión de si los problemas de NP-completo son
realmente más difíciles que los de P es el problema de un millón de dólares deP contra NP, considerado como una de las
preguntas abiertas más importantes en matemáticas.
No se sabe que el problema de
isomorfismo de la gráfica esté en P ni que NP esté completo; en cambio,
parece flotar entre las dos categorías. Es uno de los pocos problemas
naturales que ocupan este limbo; El único otro problema similar que es tan
conocido como el isomorfismo gráfico es el problema de factorizar un número en
números primos.
"Muchas
personas han pasado tiempo trabajando en el isomorfismo gráfico, porque es un
problema muy natural, simple al estado, pero también es muy misterioso", dijo Grochow.
Hay buenas razones para sospechar que
el isomorfismo del gráfico no es NP-completo. Por ejemplo, tiene una
propiedad extraña que ningún problema de NP-completo ha demostrado tener: es
posible, en teoría, que un ser omnisciente ("Merlín") convenza a una
persona común ("Arturo") de que dos Los gráficos son diferentes sin
revelar ningún indicio sobre dónde se encuentran las diferencias.
Esta prueba de "conocimiento
cero" es similar a la forma en que Merlín pudo convencer a Arthur de que
Coke y Pepsi tienen fórmulas diferentes, incluso si Arthur no puede probar la
diferencia entre ellos. Todo lo que Merlín tendría que hacer es tomar
repetidas pruebas de sabor a ciegas; Si siempre puede identificar
correctamente a Coke y Pepsi, Arthur debe aceptar que las dos bebidas son
diferentes.
De manera similar, si Merlín le dijo
a Arturo que dos gráficos son diferentes, Arturo podría probar esta afirmación
colocando los dos gráficos detrás de su espalda, moviendo sus nodos alrededor
para que se vieran muy diferentes de la forma en que comenzaron, y luego
mostrándolos a Merlín y preguntándoles lo que era cual. Si las dos
gráficas son realmente isomorfas, no hay manera de que Merlín pueda
decirlo. Entonces, si Merlín responde a estas preguntas una y otra vez,
Arthur eventualmente concluirá que las dos gráficas deben ser diferentes, incluso
si él mismo no puede detectar las diferencias.
Nadie ha encontrado nunca un
protocolo de prueba de sabor ciego para ningún problema de
NP-completa. Por esa y otras razones, existe un consenso bastante fuerte
entre los científicos informáticos teóricos de que el isomorfismo gráfico
probablemente no está completo en NP.
Para la pregunta inversa, si el
isomorfismo de la gráfica está en P, la evidencia es más variada. Por un
lado, hay algoritmos prácticos para el isomorfismo gráfico que no pueden
resolver el problema de manera eficiente para cada gráfico individual, pero que
funcionan bien en casi cualquier gráfico que pueda arrojarles, incluso los
elegidos al azar. Los científicos de computación tienen que trabajar duro
para crear gráficos que disparen estos algoritmos.
Por otra parte, el isomorfismo
gráfico es lo que los científicos informáticos llaman un problema
"universal": todos los problemas posibles sobre si dos
"estructuras combinatorias" son isomorfas, por ejemplo, la pregunta
de si dos rompecabezas Sudoku diferentes son realmente el mismo rompecabezas
subyacente, puede Ser refundido como un problema de isomorfismo
gráfico. Esto significa que un algoritmo rápido para el isomorfismo
gráfico resolvería todos estos problemas a la vez. "Por lo general, cuando tienes ese tipo de universalidad, implica
algún tipo de dureza", dijo Grochow.
En 2012, William Gasarch , un
científico informático de la Universidad de Maryland, College Park, encuestó informalmente a
científicos informáticos teóricos sobre el problema del isomorfismo en la
gráfica y descubrió que 14 personas creían que pertenecía a P, mientras que
seis creían que no. Antes del anuncio de Babai, muchas personas no
esperaban que el problema se resolviera pronto. "Pensé que tal vez no estaba en P, o quizás sí, pero no lo
sabríamos en mi vida", dijo Grochow.
Pintar
por números
El algoritmo propuesto por Babai no
introduce el isomorfismo gráfico en P, pero se acerca. Afirma que es casi
polinomial, lo que significa que para un gráfico con n nodos,
el tiempo de ejecución del algoritmo es comparable a n elevado
no a una potencia constante (como en un polinomio) sino a una potencia que
crece muy lentamente.
El mejor algoritmo anterior ,
que Babai también participó en la creación en 1983 con Eugene Luks, ahora
profesor emérito en la Universidad de Oregón, se ejecutó en tiempo
"subexponencial", un tiempo de ejecución cuya distancia del tiempo
casi polinomial es casi tan grande como el abismo entre el tiempo exponencial y
el tiempo polinomial. Babai, quien comenzó a trabajar en el isomorfismo
gráfico en 1977, "ha estado evitando
este problema durante unos 40 años", dijo Aaronson.
El nuevo algoritmo de Babai comienza
tomando un pequeño conjunto de nodos en el primer gráfico y virtualmente
"pintando" cada uno de un color diferente. Luego comienza a
buscar un isomorfismo al hacer una estimación inicial de qué nodos del segundo
gráfico pueden corresponder a estos nodos, y pinta esos nodos de los mismos
colores que sus nodos correspondientes en el primer gráfico. El algoritmo
eventualmente pasa por todas las conjeturas posibles.
Una vez que se ha realizado la
estimación inicial, restringe lo que pueden hacer otros nodos: por ejemplo, un
nodo que está conectado al nodo azul en el primer gráfico debe corresponder a
un nodo que está conectado al nodo azul en el segundo gráfico. Para
realizar un seguimiento de estas restricciones, el algoritmo introduce nuevos
colores: puede pintar los nodos de color amarillo si están vinculados a un nodo
azul y un nodo rojo, o verde si están conectados a un nodo rojo y dos nodos
amarillos, y así sucesivamente. El algoritmo continúa introduciendo más
colores hasta que no quedan funciones de conectividad para capturar.
Babai demostró que los "gráficos de Johnson"
altamente simétricos eran el único caso que el esquema de pintura de su
algoritmo no cubría. Tilman Piesk
Una vez que los gráficos están coloreados, el
algoritmo puede descartar todos los emparejamientos que emparejan nodos de diferentes
colores. Si el algoritmo tiene suerte, el proceso de pintura dividirá los
gráficos en muchos trozos de diferentes colores, reduciendo en gran medida el
número de posibles isomorfismos que el algoritmo debe considerar. Si, en
cambio, la mayoría de los nodos terminan con el mismo color, Babai ha
desarrollado una forma diferente de reducir el número de posibles isomorfismos,
que funciona excepto en un caso: cuando los dos gráficos contienen una
estructura relacionada con un "gráfico de Johnson". Estos son
gráficos que tienen tanta simetría que el proceso de pintura y los
refinamientos posteriores de Babai simplemente no brindan suficiente
información para guiar el algoritmo.
En la primera de varias charlas sobre su nuevo algoritmo , el 10 de noviembre, Babai llamó a estos
gráficos de Johnson "una fuente de miseria indescriptible" para los
científicos informáticos que trabajan en esquemas de pintura para el problema
del isomorfismo de gráficos. Pero los gráficos de Johnson pueden manejarse
con bastante facilidad por otros métodos, por lo que al mostrar que estos
gráficos son el único obstáculo para su esquema de pintura, Babai pudo
dominarlos.
El enfoque de Babai es "una estrategia muy natural, muy limpia
en cierto sentido", dijo Janos Simon, un científico informático de
la Universidad de Chicago. "Es
muy probable que sea la correcta, pero todos los matemáticos son cautelosos".
A pesar de que el nuevo algoritmo ha
movido el isomorfismo gráfico mucho más cerca de P que nunca, Babai especuló en
su primera conversación de que el problema podría estar justo fuera de sus
fronteras, en los suburbios en lugar de en el centro de la ciudad.
“Esa
sería la posibilidad más interesante”,
dijo Trevisan, ya que haría del isomorfismo de grafos el primer problema
natural en tener un algoritmo casi polinomial pero no un algoritmo
polinómico.
"Mostraría
que el panorama de la teoría de la complejidad es mucho más rico de lo que
pensábamos", dijo.
Sin embargo, si este es el caso, no
espere una prueba en el corto plazo: probar que equivaldría a resolver el
problema P versus NP, ya que significaría que el isomorfismo del gráfico separa
los problemas en P de los problemas NP completos.
Muchos científicos informáticos
creen, en cambio, que el isomorfismo gráfico está ahora en una ruta de planeo
que eventualmente lo enviará hacia P.
“Es la trayectoria habitual”, dijo
Trevisan, una vez que se ha encontrado un algoritmo casi
polinómico. Entonces, nuevamente, "de
alguna manera este problema ha sorprendido a la gente muchas veces",
dijo. "Tal vez hay una sorpresa
más por venir".
Fuente: QUANTA Magazine 20.junio.2019
– Erica Klarreich Contributing Correspondent, su artículo del 14 de diciembre
de 2015 titulado “Landmark Algorithm Breaks 30-Year Impasse”
Glosario
No se sabe que el problema se pueda resolver en tiempo polinomial ni
que sea NP-completo y,
por lo tanto, puede estar en la clase de complejidad computacional
NP-intermedia. Se sabe que el problema de isomorfismo gráfico está en
la'jerarquía baja de la clase NP, lo que implica que no es NP completo a menos
que la jerarquía de tiempo polinomial colapse a su segundo nivel. Al mismo
tiempo, el isomorfismo para muchas clases especiales de gráficos se puede
resolver en tiempo polinomial, y en la práctica el isomorfismo gráfico a menudo
se puede resolver de manera eficiente. Wikipedia
Traducción
libre de Soca
