Jump to content

Talk:Schaefer's dichotomy theorem

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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)[reply]

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)[reply]
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)[reply]