计算机与人工智能 · 实验
打破极限
一个网络,一群彼此全都认识的人,一条1985年借道矩阵乘法的捷径,以及一个维持了几十年的假设。四个问题,从初级到高级,讲的是k-团假设的终结。
1 · 结论2 · 指数3 · 靶子4 · 团之外
1 · 说出被证明的结论
初级
关于k-团假设,文章表明了什么?
2 · 计算1985年方法的代价
Nešetřil–Poljak方法大约用n^(ωk/3)步找到一个k-团。取k = 9和ω = 2,即ω可能取的最小值。
中级
1985年的方法给出的n的指数是多少?
3 · 解释“即使ω = 2”
这一假设预测的代价是n^(ωk/3)。ω的确切值未知:它至少为2,文章引用了一个9/4的上界。
高级
为什么新的节省无论ω是多少、即使ω = 2都成立,这一点很重要?
4 · 把增益推广出去
Max-2-CSP包括Max-Cut和Max-2-SAT,对于n个布尔变量,它此前大约需要2^(ωn/3)步求解。把变量分成九组,每组的一种赋值就成为一个加权九顶点团问题中的一个顶点。
高级
新的团算法为这些问题带来了什么?
极限已打破
—