부분 결과서지만 확인
A Dichotomy Theorem for Nonuniform CSPsAndrei A. Bulatov · 2017FOCS 2017 (58th Annual IEEE Symposium on Foundations of Computer Science), 319–330쪽 · arXiv:1703.03021Feder 와 Vardi 가 내놓은, 비균일 제약 충족 문제의 복잡도에 관한 이분 추측을 증명한 논문이다. 유한한 제약 언어로 정해지는 제약 충족 문제는 모두 P 이거나 NP-완전이라는 정리로, 같은 해 zhuk-2020 과 독립으로 증명되었다. schaefer-1978 에서 시작한 물음의 완결이며, P ≠ NP 여도 이 넓은 문제 족 안에는 중간 문제가 없다는 뜻이다.
확인:Crossref 의 DOI 등록 기록으로 제목·저자·학회·쪽을, arXiv 초록 페이지로 초록을 확인했다.