Computação e IA · o experimento
Supere o limite
Uma rede, um grupo de pessoas que se conhecem todas, um atalho de 1985 pela multiplicação de matrizes e uma hipótese que resistiu por décadas. Quatro perguntas, de iniciante a avançado, sobre o fim da Hipótese da k-Clique.
1 · Diga o que foi provado
Iniciante
O que o artigo mostra sobre a Hipótese da k-Clique?
2 · Calcule o custo de 1985
O método de Nešetřil–Poljak encontra uma k-clique em cerca de n^(ωk/3) passos. Tome k = 9 e ω = 2, o menor valor que ω poderia ter.
Intermediário
Que expoente de n o método de 1985 dá?
3 · Explique o “mesmo se ω = 2”
A hipótese prevê um custo de n^(ωk/3). O valor exato de ω é desconhecido: vale pelo menos 2, e o artigo cita um limite superior de 9/4.
Avançado
Por que importa que a nova economia valha qualquer que seja ω, mesmo ω = 2?
4 · Transfira o ganho
Max-2-CSP, que inclui Max-Cut e Max-2-SAT, com n variáveis booleanas, era resolvido em cerca de 2^(ωn/3) passos. Divida as variáveis em nove grupos, e a atribuição de cada grupo vira um vértice de um problema de clique ponderada de tamanho nove.
Avançado
O que o novo algoritmo de cliques dá para esses problemas?
Limite superado
—