Informática e IA · el experimento
Supera el límite
Una red, un grupo de personas que se conocen todas entre sí, un atajo de 1985 a través de la multiplicación de matrices y una hipótesis que se sostuvo durante décadas. Cuatro preguntas, de principiante a experto, sobre el final de la hipótesis del k-clique.
1 · Enuncia lo que se demostró
Principiante
¿Qué muestra el artículo sobre la hipótesis del k-clique?
2 · Calcula el coste de 1985
El método de Nešetřil–Poljak encuentra un k-clique en unos n^(ωk/3) pasos. Toma k = 9 y ω = 2, el valor más bajo que podría tener ω.
Intermedio
¿Qué exponente de n da el método de 1985?
3 · Explica el «incluso si ω = 2»
La hipótesis predice un coste de n^(ωk/3). El valor exacto de ω se desconoce: vale al menos 2, y el artículo cita una cota superior de 9/4.
Experto
¿Por qué importa que el nuevo ahorro se mantenga sea cual sea ω, incluso si ω = 2?
4 · Traslada la ganancia
Max-2-CSP, que incluye Max-Cut y Max-2-SAT, con n variables booleanas, se resolvía en unos 2^(ωn/3) pasos. Divide las variables en nueve grupos y cada asignación de un grupo se convierte en un vértice de un problema de clique ponderado de nueve vértices.
Experto
¿Qué da el nuevo algoritmo de cliques para estos problemas?
Límite superado
—