부분 결과서지만 확인
A Proof of the CSP Dichotomy ConjectureDmitriy Zhuk · 2020Journal of the ACM 67(5), 2020 (논문별 쪽 1–78) · 학회 발표 FOCS 2017 (58th Annual IEEE Symposium on Foundations of Computer Science), 331–342쪽 — 학회판 제목은 「A Proof of CSP Dichotomy Conjecture」 · arXiv:1704.01914약한 근사 만장일치 다형성(weak near unanimity polymorphism)을 가진 제약 언어의 제약 충족 문제를 다항 시간에 푸는 알고리즘을 내놓아 CSP 이분 추측의 남은 절반을 증명한 논문이다. 그런 다형성이 없으면 NP-완전임은 이미 알려져 있었으므로, 이로써 유한 제약 언어의 CSP 는 모두 P 이거나 NP-완전임이 확정되었다. bulatov-2017 과 독립으로 얻은 증명이며 두 편을 함께 인용한다.
확인:학술지판과 학회판은 Crossref 등록 기록으로, 초록은 Crossref 와 arXiv 초록 페이지로 확인했다.