Computing & AI · the experiment
Beat the limit
A network, a group of people who all know each other, a 1985 shortcut through matrix multiplication, and a hypothesis that held for decades. Four questions, from beginner to expert, on the end of the k-Clique Hypothesis.
1 · State what was proved
Beginner
What does the article show about the k-Clique Hypothesis?
2 · Compute the 1985 cost
The Nešetřil–Poljak method finds a k-clique in about n^(ωk/3) steps. Take k = 9 and ω = 2, the lowest value ω could have.
Intermediate
What exponent of n does the 1985 method give?
3 · Explain the "even if ω = 2"
The hypothesis predicts a cost of n^(ωk/3). The exact value of ω is unknown: it is at least 2, and the article cites an upper bound of 9/4.
Expert
Why does it matter that the new saving holds whatever ω is, even ω = 2?
4 · Carry the gain over
Max-2-CSP, which includes Max-Cut and Max-2-SAT, on n Boolean variables, was solved in about 2^(ωn/3) steps. Split the variables into nine groups and each group's assignment becomes a vertex of a weighted nine-clique problem.
Expert
What does the new clique algorithm give for these problems?
Limit beaten
—