Weisfeiler–Leman 等价的无条件时间下界
Unconditional time lower bounds for Weisfeiler–Leman equivalence
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究判定两个 n 顶点图是否 k-Weisfeiler–Leman 等价的计算复杂度。作者声称，对每个充分大的固定 k，最坏情况下需要 n^{Ω(k)} 确定性顺序时间，且该界对每个充分大的图阶成立，即使对直径至多二的简单连通无着色图，无需复杂性假设。输入为显式邻接矩阵，模型为多带图灵机和顺序对数词 RAM。
- 对充分大的固定 k，判定 k-WL 等价需 n^{Ω(k)} 确定性顺序时间。
- 下界对直径至多二的简单连通无着色图成立，无需复杂性假设。
- 覆盖多带图灵机和顺序对数词 RAM 模型及两种替换约定。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
For every sufficiently large fixed k, deciding whether two n-vertex graphs are k-Weisfeiler–Leman equivalent requires $`n^{\Omega(k)}`$ deterministic sequential time in the worst case. The bound holds at every sufficiently large graph order, even for simple connected uncolored graphs of diameter at most two, without a complexity assumption. Inputs are explicit adjacency matrices; the models are multitape Turing machines and sequential logarithmic-word RAMs with fixed polynomial-bit-time instructions. Both joint and separate replacement conventions are covered.
用户标记：未标记
固定编号：be7ef433059b443d
原文来源