最优Max-Cut硬度的直接证明
A Direct Proof of Optimal Max-Cut Hardness
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究简单无权图上Max-Cut的近似硬度。作者声称证明：将Max-Cut近似到任何大于Goemans–Williamson常数的固定因子都是NP困难的。该结论若成立，将以直接证明方式确立Max-Cut的最优近似阈值，属于组合优化与计算复杂性中的经典问题；但作为AI产生的研究手稿，尚未经独立审查或同行评议，摘要也未给出归约或证明细节。
- 研究对象为简单无权图上的Max-Cut近似
- 作者声称任何大于Goemans–Williamson常数的固定因子均NP困难
- 摘要称给出直接证明，未展开归约细节
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We prove that approximating Max-Cut on simple unweighted graphs within any fixed factor greater than the Goemans–Williamson constant is NP-hard.
用户标记：未标记
固定编号：506a4785197ba715
原文来源