用Weisfeiler–Leman精化识别图的复杂性
The complexity of identifying a graph by Weisfeiler–Leman refinement
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
该稿件研究Weisfeiler–Leman精化识别图问题的计算复杂性。作者声称：判定给定维数的Weisfeiler–Leman精化是否识别输入图是EXPTIME完全的。摘要说明输入为非空有限简单无权图（邻接矩阵形式）与正二进制编码维数，识别量化对所有比较图进行。该结果刻画了图识别问题的复杂度上界与下界，属于组合数学与图论中的算法复杂性研究。
- 声称判定WL精化是否识别给定图是EXPTIME完全的
- 输入为邻接矩阵图与二进制编码维数
- 识别定义量化对所有比较图
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We prove that deciding whether Weisfeiler–Leman refinement of an input dimension identifies a given graph is EXPTIME-complete. The input is a nonempty finite simple uncolored graph in adjacency-matrix form and a positive binary-encoded dimension. Identification quantifies over every comparison graph.
用户标记：未标记
固定编号：d4ace159a7e4a30a
原文来源