Revision as of 10:26, 25 August 2025 edit Citation bot (talk \| contribs) Bots 5,864,335 edits Added bibcode. Removed URL that duplicated identifier. Removed access-date with no URL. Removed parameters. \| Use this bot. Report bugs. \| Suggested by Headbomb \| Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox \| #UCB_webform_linked 303/1032 ← Previous edit		Latest revision as of 05:39, 26 August 2025 edit undo Hhhguir (talk \| contribs) 80 edits m Punctuation Tags: Visual edit Mobile edit Mobile web edit Advanced mobile edit
Line 105: {{Main\|XOR-SAT}} Another special case is the class of problems where each clause contains XOR (i.e. [[exclusive or]]) rather than (plain) OR operators. This is in [[P (complexity class)\|P]], since an XOR-SAT formula can also be viewed as a system of linear equations mod 2, and can be solved in cubic time by [[Gaussian elimination]];.<ref>{{citation\|title=The Nature of Computation\|first1=Cristopher\|last1=Moore\|author1-link=Cristopher Moore\|first2=Stephan\|last2=Mertens\|publisher=Oxford University Press\|year=2011\|isbn=9780199233212\|page=366\|url=https://books.google.com/books?id=z4zMiZyAE1kC&pg=PA366}}.</ref> == Schaefer's dichotomy theorem ==

Boolean satisfiability problem: Difference between revisions