← 研踪 PaperTrailarXiv:2611.09764 · v1
The k-Clique hypothesis is dead, for good
k-Clique 假设已死,且是彻底地死了
首次提交 2026-11-07 01:28
版本更新 2026-11-07 01:28
雷达观测 2026-11-09 13:22
摘要
We present an algorithm that solves the -Clique problem for any large enough and any -vertex graph in time, where is the matrix multiplication exponent and is a positive constant independent of both and . This refutes the long-standing -Clique conjecture, regardless of the value of the matrix multiplication constant, even if . In fact, our algorithm solves the more general problem of counting weighted -Cliques.
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-07 01:28 · 最新观测版本
The k-Clique hypothesis is dead, for good
We present an algorithm that solves the -Clique problem for any large enough and any -vertex graph in time, where is the matrix multiplication exponent and is a positive constant independent of both and . This refutes the long-standing -Clique conjecture, regardless of the value of the matrix multiplication constant, even if . In fact, our algorithm solves the more general problem of counting weighted -Cliques.
查看此版本解读 →查看此版本原文 ↗