Talk:Schaefer's dichotomy theorem: Difference between revisions
Appearance
Content deleted Content added
No edit summary |
Reply |
||
Line 3: | Line 3: | ||
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. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/193.55.176.1|193.55.176.1]] ([[User talk:193.55.176.1|talk]]) 15:28, 7 March 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot--> |
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. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/193.55.176.1|193.55.176.1]] ([[User talk:193.55.176.1|talk]]) 15:28, 7 March 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot--> |
||
: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.—[[User:EmilJ|Emil]] [[User talk:EmilJ|J.]] 16:58, 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.—[[User:EmilJ|Emil]] [[User talk:EmilJ|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. [[User:Edemaine|Erik Demaine]] ([[User talk:Edemaine|talk]]) 00:01, 17 November 2023 (UTC) |
Revision as of 00:01, 17 November 2023
![]() | Mathematics Stub‑class Low‑priority | |||||||||
|
![]() | Computer science Stub‑class Low‑importance | ||||||||||||||||
|
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)