Talk:Schaefer's dichotomy theorem
Appearance
![]() | This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
|
Untitled
[edit]I replaced the reference to the Bulatov-Dalmau paper with the reference to the Creignou-Hermann paper, where dichotomy result for counting boolean CSP appears first. — Preceding unsigned comment added by 193.55.176.1 (talk) 15:28, 7 March 2013 (UTC)
- That’s right. However, the section needs more reorganization: the Creignou and Hermann #SAT dichotomy is simply that the affine case is in P, and everything else is #P-complete. The stuff about Mal'tsev polynomials (which comes from the Bulatov and Dalmau paper) is only relevant for non-Boolean CSP’s, but then it is no longer a sufficient condition.—Emil J. 16:58, 7 March 2013 (UTC)
- I've taken a crack at this reorganization, splitting into binary and nonbinary paragraphs and citing the relevant paper in each. Erik Demaine (talk) 00:01, 17 November 2023 (UTC)