TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Simplified proof of the Constraint Satisfaction Problem Dichotomy Conjecture

1 点作者 cevi大约 1 年前

1 comment

cevi大约 1 年前
In 2017, Andrei Bulatov and Dmitriy Zhuk independently proved that every CSP template defines a problem which is either NP-complete or can be solved in polynomial time (they shared best paper at FOCS for this). However, the number of people who actually understand either of their proofs is still tiny, and no one has managed reduce the (enormous) running times of their algorithms. Zhuk just put out a much simpler argument with a cleaner abstraction of the crucial algebraic properties which are used in his proof.<p>By the way, if anyone is interested in a slightly more comprehensive exposition of the background material, I have been working for several years on writing up notes on the topic: <a href="https:&#x2F;&#x2F;raw.githubusercontent.com&#x2F;notzeb&#x2F;all&#x2F;master&#x2F;csp-notes.pdf" rel="nofollow">https:&#x2F;&#x2F;raw.githubusercontent.com&#x2F;notzeb&#x2F;all&#x2F;master&#x2F;csp-note...</a>