Это задача [[Класс P|Р-класса]],так как <b><tex>\mathrm {XOR}</tex></b>-<b><tex>\mathrm {SAT}</tex></b> формулу можно рассматривать как систему линейных уравнений по модулю 2,которая ,в свою очередь, может быть решена за <tex>O(n^3)</tex> методом Гаусса<ref>https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%93%D0%B0%D1%83%D1%81%D1%81%D0%B0 ,kf,kf</ref>.Такое представление возможно на основе связи между Булевой алгеброй и Булевым кольцом <ref>https://en.wikipedia.org/wiki/Boolean_algebra_(structure)#Boolean_rings</ref> и том факте,что арифметика по модулю 2 образует конечное поле <ref>https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D0%BE%D0%B5_%D0%BF%D0%BE%D0%BB%D0%B5</ref>.
==Решение XOR-SAT задачи методом Гаусса== {| alignclass="centerwikitable" classalign="wikitable collapsible collapsedcenter" style="textcolor: blue; background-aligncolor:left#ffffcc; margin: 1em"cellpadding="10"|+!colspan="5"|Система уравнений|-align="center"! Solving an XOR-SAT example("<tex>1</tex>" означает «истинно», "<tex>0<BR/tex>by Gaussian elimination" означает «ложно»)|-Каждый конъюнкт ведет к одному уравнению.
|
{| -align="center" class!Переменные|! width="collapsible collapsed20%" style="text-align:left"|-! Given formulaЗначения|-| (align="⊕center" means XOR, the ! <font color=redtex> a </tex> <tex> red clause \oplus</fonttex> <tex> is optional)|-| (''a''⊕''c''⊕''d'') ∧ (''b''⊕¬''c''⊕''d'') ∧ (''a''⊕''b''⊕¬''d'') ∧ (''a''⊕¬''b''⊕¬''c'') <font color=red/tex> <tex>\oplus</tex> <tex> ∧ (¬''a''⊕''b''⊕''c'') d </fonttex>|}<tex>=1</tex>|-|{| align="left" class="collapsible collapsed" style="text-align:leftcenter"|-! colspan="9" | Equation system|-| colspan="9" | ("1" means TRUE, "0" means FALSE)|-| colspan="9" | Each clause leads to one equation.|-| ''a'' ⊕ ''c'' ⊕ ''d'' = 1|-| ''b'' ⊕ ¬ ''c'' ⊕ ''d'' = 1|-| ''a'' ⊕ ''b'' ⊕ ¬ ''d'' = 1|-| ''a'' ⊕ ¬ ''b'' ⊕ ¬ ''c'' = 1|-| <font color=redtex> ¬ b </fonttex> <font color=redtex> ''a'' \oplus</fonttex> <font color=redtex> ⊕ \neg c </fonttex> <font color=redtex> ''b'' \oplus</fonttex> <font color=redtex> ⊕ d </fonttex> <font color=red> ''c'' |</fonttex><font color=red> ≃ 1 </fonttex>|-|{| align="left" class="collapsible collapsed" style="text-align:leftcenter"|-! colspan="6" | Normalized equation system|-| colspan="6" | using properties of [[Boolean rings]] (¬''x''=1⊕''x'', ''x''⊕''x''=0)|-| ''a'' || ⊕ || ''c'' || ⊕ || ''d'' || = '''1'''|-| ''b'' || ⊕ || ''c'' || ⊕ || ''d'' || = '''0'''|-| ''a'' || ⊕ || ''b'' || ⊕ || ''d'' || = '''0'''|-| ''a'' || ⊕ || ''b'' || ⊕ || ''c'' || = '''1'''|-| <font color=redtex> ''a'' </fonttex> || <font color=redtex> ⊕ \oplus</fonttex> || || <font color=redtex> '' b'' </fonttex> || <font color=redtex> ⊕ \oplus</fonttex> || || <font color=redtex> ''c'' \neg d </fonttex> || <font colortex>=red> ≃ ''0'' 1</fonttex>|-| colspanalign="6center" | (If the ! <font color=redtex> red equation \neg a </fonttex> is present, <font color=redtex> it \oplus</fonttex> <tex> contradicts|-| colspan="6" | the last black one, so the system is unsolvable.|-| colspan="6" | Therefore, Gauss' algorithm is|-| colspan="6" | used only for the black equations.)|}|-|{| align="left" class="collapsible collapsed" style="text-align:left"|-! colspan="6" | Associated coefficient matrix|-| |-! ''a'' !! ''\neg b'' !! ''</tex> <tex>\oplus</tex> <tex>\neg c'' !! ''d'' !! !! line|-| |-</tex> | <tex>=1 || 0 || 1 || 1! 1| A|-| 0 || 1 || 1 || 1! 0| B|-| 1 || 1 || 0 || 1! 0| C|-| 1 || 1 || 1 || 0! 1| D|}</tex>|-|{| align="left" class="collapsible collapsed" style="text-align:left"|-! colspan="6center" |Transforming to echelon form|-| |-! ''a'' !! ''b'' !! ''c'' !! ''d'' !! !! operation|-| |-| 1 || 0 || 1 || 1! 1| A|-| 1 || 1 || 0 || 1! 0| C|-| 1 || 1 || 1 || 0! 1| D|-| 0 || 1 || 1 || 1! 0| B (swapped)|-| |-| 1 || 0 || 1 || 1! 1| A|-| 0 || 1 || 1 || 0! 1| E = C⊕A|-| 0 || 1 || 0 || 1! 0| F = D⊕A|-| 0 || 1 || 1 || 1! 0| B|-| |-| 1 || 0 || 1 || 1! 1| A|-| 0 || 1 || 1 || 0! 1| E|-| 0 || 0 || 1 || 1! 1| G = F⊕E|-| 0 || 0 || 0 || 1! 1| H = B⊕E|}|-|{| align="left" class="collapsible collapsed" style="text-alignbackground:left#ffdddd;"|-! colspan="6" | Transforming to diagonal form|-| |-! ''<tex> \neg a'' !! ''</tex> <tex>\oplus</tex> <tex> b'' !! ''c'' !! ''d'' !! !! operation|-| |-| 1 || 0 || 1 || 0! 0| I = A⊕H|-| 0 || 1 || 1 || 0! 1| E|-| 0 || 0 || 1 || 0! 0| J = G⊕H|-| 0 || 0 || 0 || 1! 1| H|-| |-| 1 || 0 || 0 || 0! 0| K = I⊕J|-| 0 || 1 || 0 || 0! 1| L = E⊕J|-| 0 || 0 || 1 || 0! 0| J|-| 0 || 0 || 0 || 1! 1| H|-|}|-|{| align="left" class="collapsible collapsed" style="text-align:left"|-! Solution:|-| If the <font color=red/tex> <tex> red clause \oplus</fonttex> <tex> is present: || Unsolvable|-| Else: || ''a'' = 0 = FALSE|-| || ''b'' = 1 = TRUE|-| || ''c'' = 0 = FALSE</tex>|-| || ''d'' = 1 = TRUE|-| colspan! style="2" | '''As a consequencebackground:'''|-| colspan="2#ffdddd;" | ''R''(''a'',''c'',''d'') ∧ ''R''(''b'',¬''c'',''d'') ∧ ''R''(''a'',''b'',¬''d'') ∧ ''R''(''a'',¬''b'',¬''c'')<font color=redtex> ∧ ''R''(¬''a'',''b'',''c'') \cong 1 </fonttex>|-| colspan="2" | is not 1-in-3-satisfiable,|-| colspan="2" | while (''a''∨''c''∨''d'') ∧ (''b''∨¬''c''∨''d'') ∧ (''a''∨''b''∨¬''d'') ∧ (''a''∨¬''b''∨¬''c'')|-| colspan="2" | is 3-satisfiable with ''a''=''c''=FALSE and ''b''=''d''=TRUE.|}
|}
