跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

We present an algorithm that solves the kk-Clique problem for any large enough kk and any nn-vertex graph in n(ω3−c)kn^{\left(\fracω{3}-c\right)k} time, where ω≥2ω\geq 2 is the matrix multiplication exponent and c>0c>0 is a positive constant independent of both ωω and kk. This refutes the long-standing kk-Clique conjecture, regardless of the value of the matrix multiplication constant, even if ω=2ω=2. In fact, our algorithm solves the more general problem of counting weighted kk-Cliques.

AI 论文解读

基于摘要 · 非全文审阅

作者提出一个对足够大的 k 在 n^{(ω/3−c)k} 时间内求解(并计数加权)k-Clique 的算法,据此声称推翻了长期存在的 k-Clique 猜想。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-07 01:28 · 最新观测版本

The k-Clique hypothesis is dead, for good

We present an algorithm that solves the kk-Clique problem for any large enough kk and any nn-vertex graph in n(ω3−c)kn^{\left(\fracω{3}-c\right)k} time, where ω≥2ω\geq 2 is the matrix multiplication exponent and c>0c>0 is a positive constant independent of both ωω and kk. This refutes the long-standing kk-Clique conjecture, regardless of the value of the matrix multiplication constant, even if ω=2ω=2. In fact, our algorithm solves the more general problem of counting weighted kk-Cliques.

查看此版本解读 →查看此版本原文 ↗