Изменения

|definition = <b><tex>\mathrm {XORSAT}</tex></b> (англ. ''XOR-satisfiability'') выполнимость функции — задача распределения аргументов в булевой [[КНФ|КНФ]] функции, записанной в виде XOR-КНФ, таким образом, чтобы результат данной функции был равен <tex> 1 </tex>.

Одним из особых случаев <b><tex>\mathrm {SAT}</tex></b> является класс задач, где каждый дизъюнкт конъюнкт содержит операции <tex>\oplus</tex> (т. е. исключающее или), а не (обычные) <tex>\lor</tex> операторы.(Формально, обобщенная КНФ с тернарным булевым оператором <tex> R </tex> работает только если <tex> 1 </tex> или <tex> 3 </tex> переменные дают <b><tex>\mathrm mathtt {TRUEtrue}</tex></b> в своих аргументах. ДизъюнктКонъюнкты,имеющие более <tex> 3 </tex> переменных могут быть преобразованы в сочетании с формулой преобразования с сохранением выполнимости булевой функции(ссылка на книгу ниже), т. е. <b><tex>\mathrm {XOR}</tex></b>-<b><tex>\mathrm {SAT}</tex></b> может быть снижена до <b><tex>\mathrm {XOR}</tex></b>-<b><tex>\mathrm {3}</tex></b>-<b><tex>\mathrm {SAT}</tex></b>)<ref>''Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). ''The Design and Analysis of Computer Algorithms. Addison-Wesley.; здесь: Thm.10.4, 1974.</ref>

Это задача [[Класс P|Р-класса]],так как ==Пример решения XORSAT=====Пример===<font color='red'>Красные пункты<b/font>могут быть добавлены для возможности представления КНФ-функции в виде <tex>\mathrm {XOR}</tex></b>-<b><tex>\mathrm {SAT}</tex>.{| class="wikitable"!<tex>(a \oplus b \oplus c) \land (b \oplus \neg c \oplus d) \land (a \oplus b \oplus \neg d) \land (a \oplus \neg b \oplus \neg c)</btex> формулу можно рассматривать как систему линейных уравнений по модулю 2,которая ,в свою очередь, может быть решена за ! style="background: #ffdddd;" |<tex>O\land (n^3\neg a \oplus b \oplus c)</tex> |}{| class="wikitable"|+!colspan="2"|Решение XOR-SAT задачи методом Гаусса|-align="center"!<refcenter>https{| class="wikitable" align="center" style="color:blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="2"|Система уравнений|-align="center"!Переменные|! width="20%" | Значение|-align="center"! <tex> a </tex> <tex>\oplus</tex> <tex> c </tex> <tex>\oplus</tex> <tex> d </tex> |<tex>=1</tex>|-align="center"! <tex> b </tex> <tex>\oplus</tex> <tex>\neg c </tex> <tex>\oplus</tex> <tex> d </tex> |<tex>=1</tex>|-align="center"! <tex> a </tex> <tex>\oplus</tex> <tex> b </ru.wikipedia.orgtex> <tex>\oplus</tex> <tex>\neg d </tex> |<tex>=1</tex>|-align="center"! <tex> \neg a </tex> <tex>\oplus</tex> <tex> \neg b </wikitex> <tex>\oplus</%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%93%D0%B0%D1%83%D1%81%D1%81%D0%B0 ,kf,kftex> <tex>\neg c </reftex>.Такое представление возможно на основе связи между Булевой алгеброй и Булевым кольцом |<reftex>https=1</tex>|-align="center"! style="background:#ffdddd;" |<tex> \neg a </tex> <tex>\oplus</en.wikipedia.orgtex> <tex> b </tex> <tex>\oplus</tex> <tex> c </tex>! style="background: #ffdddd;" |<tex> =1 </wikitex>|}</Boolean_algebra_center>!(structure«<tex>1</tex>» означает «<tex> \mathtt {true}</tex>», «<tex>0</tex>» означает «<tex> \mathtt {false}</tex>»)Каждый конъюнкт ведет к одному уравнению.|-align="center"!<center>{| class="wikitable" align="center" style="color: blue; background-color:#Boolean_ringsffffcc;" cellpadding="10"|+!colspan="2"|Нормированная система уравнений|-align="center"!Переменные|! width="20%" | Значение|-align="center"! <tex> a </tex> <tex>\oplus</reftex> и том факте,что арифметика по модулю 2 образует конечное поле <reftex> c </tex> <tex>\oplus</tex> <tex> d </tex> |<tex>=1</tex>|-align="center"! <tex>https:b </tex> <tex>\oplus</ru.wikipedia.orgtex> <tex> c </wikitex> <tex>\oplus</%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D0%BE%D0%B5_%D0%BF%D0%BE%D0%BB%D0%B5tex> <tex> d </reftex>.|<tex>=0</tex>|-align="center"! <tex> a </tex> <tex>\oplus</tex> <tex> b </tex> <tex>\oplus</tex> <tex> d </tex> |<tex>=Решение XOR0</tex>|-align="center"! <tex> a </tex> <tex>\oplus</tex> <tex> b </tex> <tex>\oplus</tex> <tex> c </tex> |<tex>=1</tex>|-SAT задачи методом Гауссаalign="center"! style="background: #ffdddd;" |<tex> a </tex> <tex>\oplus</tex> <tex> b </tex> <tex>\oplus</tex> <tex> c </tex>! style="background: #ffdddd;" |<tex> =0 </tex>|}</center>!Используя свойства Булевых [[Определение кольца, подкольца, изоморфизмы колец|колец]] (<tex>\neg x=1 \oplus x</tex>, <tex>x \oplus x=1</tex>),<br>избавимся от отрицаний в нашей системе{| -align="center" !<center>{| class="wikitable collapsible collapsed" align="center" style="textcolor: blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="6"|Матрица соответствующих коэффициентов|-align="center" !class="dark"| <tex>a</tex> !class="dark"| <tex>b</tex> !class="dark"| <tex>c</tex> !class="dark"| <tex>d</tex> !class="green" style="font-weight:leftnormal" style="background: #ddffdd; margin"||Строка|-align="center" !class="dark" style="font-weight: 1emnormal"| <tex>1</tex> !class="dark" style="font-weight:normal"|<tex>0</tex> !class="dark" style="font-weight:normal"| <tex>1</tex> ! Solving an XORclass="dark" style="font-SAT exampleweight:normal"| <BRtex>1</tex>by Gaussian elimination !class="green" style="font-weight:normal" style="background: #ddffdd;"|-<tex>1</tex>|<tex>A</tex>{| -align="center" !class="collapsible collapseddark" style="textfont-alignweight:normal"| <tex>0</tex> !class="dark" style="font-weight:leftnormal"| <tex>1</tex> !class="dark" style="font-weight:normal"|<tex>1</tex> !class="dark" style="font-weight:normal"| <tex>1</tex> ! Given formulaclass="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>| <tex>B</tex>|-align="center" !class="dark" style="font-weight:normal"| (<tex>1</tex> !class="dark" style="⊕font-weight:normal" means XOR, the | <tex>1</tex> !class="dark" style="font color-weight:normal"| <tex>0</tex> !class="dark" style=red"font-weight:normal"| <tex> red clause 1</tex> !class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>| <tex>C</tex> is optional)|-align="center" !class="dark" style="font-weight:normal"| <tex>1</tex> !class="dark" style="font-weight:normal"| (''a''⊕''c''⊕''d'') ∧ (''b''⊕¬''c''⊕''d'') ∧ (''a''⊕''b''⊕¬''d'') ∧ (''a''⊕¬''b''⊕¬''c'') <tex>1</tex> !class="dark" style="font color-weight:normal"| <tex>1</tex> !class="dark" style=red"font-weight:normal"| <tex> ∧ (¬''a''⊕''b''⊕''c'') 0</tex> !class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>| <tex>D</tex>

</center>!Составим матрицу по следующему правилу:Если переменная присутствовала в данном конъюнкте<br>ставим в ячейку <tex>1</tex>, иначе <tex>0</tex>|-align="center"|!<center>{| alignclass="leftwikitable" classalign="collapsible collapsedcenter" style="textcolor: blue; background-aligncolor:left#ffffcc;" cellpadding="10"|-+! colspan="96" | Equation systemПреобразования, чтобы сформироватьверхнюю треугольную матрицу|-align="center"| colspan !class="9dark" | (<tex>a</tex> !class="1dark" means TRUE, | <tex>b</tex> !class="0dark" means FALSE)|-<tex>c</tex>| colspan !class="9dark" | Each clause leads to one equation.<tex>d</tex>|-| ''a'' ⊕ ''c'' ⊕ ''d'' !class="green" style= 1|"font-| ''b'' ⊕ ¬ ''c'' ⊕ ''d'' weight:normal" style= 1"background: #ddffdd;"|-| ''a'' ⊕ ''b'' ⊕ ¬ ''d'' = 1Операция|-align="center"| ''a'' ⊕ ¬ ''b'' ⊕ ¬ ''c'' !class="dark" style= 1|"font-weight:normal"| <font color=redtex> ¬ 1</fonttex> !class="dark" style="font-weight:normal"| <font color=redtex> ''a'' 0</fonttex> <font color!class="dark" style=red> ⊕ </"font> -weight:normal"| <font color=redtex> ''b'' 1</fonttex> !class="dark" style="font-weight:normal"| <font color=redtex> ⊕ 1</fonttex> <!class="green" style="font color-weight:normal" style=red"background: #ddffdd;"| <tex> ''c'' 1</fonttex>| <font color=redtex> ≃ 1 A</fonttex>|-|{| align="leftcenter" !class="collapsible collapseddark" style="textfont-alignweight:leftnormal"|-<tex>1</tex> ! colspanclass="dark" style="6font-weight:normal" | Normalized equation system<tex>1</tex> !class="dark" style="font-weight:normal"|-<tex>0</tex>| colspan !class="6dark" | using properties of [[Boolean rings]] (¬''x''style=1⊕''x'', ''x''⊕''x''=0)|"font-weight:normal"| ''a'' || ⊕ || ''c'' || ⊕ || ''d'' || = '''<tex>1'''</tex>| !class="green" style="font-weight:normal" style="background: #ddffdd;"| ''b'' || ⊕ || ''c'' || ⊕ || ''d'' || = '''<tex>0'''</tex>|-<tex>C</tex>| ''a'' || ⊕ || ''b'' || ⊕ || ''d'' || -align= '''0'''"center"| !class="dark" style="font-weight:normal"| ''a'' || ⊕ || ''b'' || ⊕ || ''c'' || = '''<tex>1'''</tex>| !class="dark" style="font-weight:normal"| <font color=redtex> ''a'' 1</tex> !class="dark" style="font> |-weight:normal"| <font color=redtex> ⊕ 1</tex> !class="dark" style="font> || |-weight:normal"| <font color=redtex> ''b'' 0</tex> !class="green" style="font> |-weight:normal" style="background: #ddffdd;"| <font color=redtex> ⊕ 1</fonttex> || || <font color=redtex> ''c'' D</fonttex> |-align="center" !class="dark" style="font-weight:normal"| <font color=redtex> ≃ ''0'' </fonttex>|-| colspan !class="dark" style="6font-weight:normal" | (If the <font color=redtex> red equation 1</tex> !class="dark" style="font> is present, -weight:normal"| <font color=redtex> it 1</fonttex> contradicts|-| colspan !class="dark" style="6font-weight:normal" | the last black one, so the system is unsolvable.<tex>1</tex>|-| colspan !class="6green" style=" | Therefore, Gauss' algorithm is|font-| colspanweight:normal" style="6background: #ddffdd;" | used only for the black equations.)<tex>0</tex>| <tex>B</tex>

</center>!Поменяем местами строки <tex>B,\ C,\ D</tex>,<br>чтобы упростить получение верхней треугольной матрицы.|-align="center"|!<center>{| alignclass="leftwikitable" classalign="collapsible collapsedcenter" style="textcolor: blue; background-aligncolor:left#ffffcc;"cellpadding="10"|+|-align="center" ! colspanclass="dark" style="6font-weight:normal" | Associated coefficient matrix<tex>1</tex> !class="dark" style="font-weight:normal"|<tex>0</tex> !class="dark" style="font-weight:normal"| &nbsp;<tex>1</tex> !class="dark" style="font-weight:normal"|-<tex>1</tex> ! ''a'' !! ''b'' !! ''c'' !! ''d'' !! !! lineclass="green" style="font-weight:normal" style="background: #ddffdd;"|-<tex>1</tex>| &nbsp;<tex>A</tex>|-align="center" !class="dark" style="font-weight:normal"| 1 || <tex>0 </tex> !class="dark" style="font-weight:normal"|<tex>1</tex> !class="dark" style="font-weight:normal"| <tex>1 </tex> !class="dark" style="font-weight:normal"|| 1<tex>0</tex> ! class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>| <tex>E=C \oplus A</tex>|-align="center" !class="dark" style="font-weight:normal"| <tex>0 </tex> !class="dark" style="font-weight:normal"|| 1 || <tex>1 </tex> !class="dark" style="font-weight:normal"|<tex>0</tex> !class="dark" style="font-weight:normal"| <tex>1</tex> ! class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>| B<tex>F=D \oplus A</tex>|-align="center" !class="dark" style="font-weight:normal"| 1 || 1 || <tex>0 </tex> !class="dark" style="font-weight:normal"|| <tex>1</tex> ! 0class="dark" style="font-weight:normal"| C<tex>1</tex>| !class="dark" style="font-| 1 || 1 |weight:normal"| <tex>1 </tex> !class="green" style="font-weight:normal" style="background: #ddffdd;"|| <tex>0! 1</tex>| D<tex>B</tex>

</center>!Т.к. операция <tex>\oplus</tex> даёт <tex>0</tex> при одинаковых аргументах,применим её для строк <tex>A,\ C=E</tex> и <tex>A,\ D=F</tex>,<br>чтобы получить <tex>0</tex> в <tex>1</tex>-м столбце.|-align="center"!|<center>{| alignclass="leftwikitable" classalign="collapsible collapsedcenter" style="textcolor: blue; background-aligncolor:left#ffffcc;"|-! colspancellpadding="610" |Transforming to echelon form|-| &nbsp;+|-align="center" ! ''a'' !! ''b'' !! ''c'' !! ''d'' !! !! operation|class="dark" style="font-weight:normal"| &nbsp;<tex>1</tex>| !class="dark" style="font-| 1 |weight:normal"| <tex>0 || 1 || 1</tex> ! 1| A|class="dark" style="font-| 1 || 1 || 0 |weight:normal"| <tex>1</tex> ! 0| C|class="dark" style="font-| 1 || 1 |weight:normal"| <tex>1 || 0</tex> ! class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>| D<tex>A</tex>|-align="center" !class="dark" style="font-weight:normal"| <tex>0 || 1 || 1 || 1</tex> ! 0| B (swapped)|class="dark" style="font-weight:normal"| &nbsp;<tex>1</tex>| !class="dark" style="font-| 1 || 0 || 1 |weight:normal"| <tex>1</tex> ! 1| A|class="dark" style="font-| 0 || 1 || 1 |weight:normal"| <tex>0</tex> ! class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>| <tex>E = C⊕A</tex>|-align="center" !class="dark" style="font-weight:normal"| <tex>0 || 1 || 0 || 1</tex> ! 0| F class="dark" style= D⊕A|"font-weight:normal"| <tex>0 || 1 || 1 || 1</tex> ! 0| B|class="dark" style="font-weight:normal"| &nbsp;<tex>1</tex>| !class="dark" style="font-| 1 || 0 || 1 |weight:normal"| <tex>1</tex> ! class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>| A<tex>G=F \oplus E</tex>|-align="center" !class="dark" style="font-weight:normal"| <tex>0 </tex> !class="dark" style="font-weight:normal"|| 1 || 1 || <tex>0</tex> ! 1| E|class="dark" style="font-weight:normal"| <tex>0 || 0 || 1 || 1</tex> ! 1| G class="dark" style= F⊕E|"font-| 0 || 0 || 0 |weight:normal"| <tex>1</tex> ! class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>| <tex>H = B⊕EB \oplus E</tex>

</center>!Теперь применим <tex>\oplus</tex> для строк <tex>E,\ F=G</tex> и <tex>B,\ E=H</tex>,<br>чтобы получить <tex>0</tex> в <tex>2</tex>-м и <tex>3</tex>-м столбцах.|-align="center"!|<center>{| alignclass="leftwikitable" classalign="collapsible collapsedcenter" style="textcolor: blue; background-aligncolor:left#ffffcc;" cellpadding="10"|-+! colspan="6" | Transforming to diagonal formПреобразования, чтобы сформировать|-| &nbsp;диагональную матрицу|-align="center" ! ''class="dark"| <tex>a'' </tex> !! ''class="dark"| <tex>b'' </tex> !! ''class="dark"| <tex>c'' </tex> !! ''class="dark"| <tex>d'' </tex> !! !! operationclass="green" style="font-weight:normal" style="background: #ddffdd;"|-| &nbsp;Операция|-align="center" !class="dark" style="font-weight:normal"| <tex>1 </tex> !class="dark" style="font-weight:normal"|| <tex>0 </tex> !class="dark" style="font-weight:normal"|| <tex>1 </tex> !class="dark" style="font-weight:normal"|| <tex>0</tex> ! class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>0</tex>| <tex>I = A⊕HA \oplus H</tex>|-align="center" !class="dark" style="font-weight:normal"| <tex>0 </tex> !class="dark" style="font-weight:normal"|| <tex>1 </tex> !class="dark" style="font-weight:normal"|| <tex>1 </tex> !class="dark" style="font-weight:normal"|| <tex>0</tex> ! class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>| <tex>E</tex>|-align="center" !class="dark" style="font-weight:normal"| <tex>0 </tex> !class="dark" style="font-weight:normal"|| <tex>0 </tex> !class="dark" style="font-weight:normal"|| <tex>1 </tex> !class="dark" style="font-weight:normal"|| <tex>0</tex> ! 0| J class="green" style= G⊕H|"font-| 0 || 0 |weight:normal" style="background: #ddffdd;"| <tex>0 || 1! 1</tex>| <tex>J=G \oplus H</tex>|-align="center"| &nbsp;| !class="dark" style="font-| 1 || 0 || 0 |weight:normal"| <tex>0</tex> ! 0| K class="dark" style= I⊕J|"font-| 0 || 1 || 0 |weight:normal"| <tex>0</tex> ! 1| L class="dark" style= E⊕J|"font-| 0 || 0 || 1 |weight:normal"| <tex>0</tex> ! 0| J|class="dark" style="font-| 0 || 0 || 0 |weight:normal"| <tex>1</tex> ! class="green" style="font-weight:normal" style="background: #ddffdd;"| <tex>1</tex>| <tex>H|-</tex>

</center>!Чтобы получить основную диагональную матрицу,<br>сделаем <tex>\oplus</tex> <tex>A,\ H=I</tex> и <tex>G,\ H=J</tex>,<br>чтобы получить <tex>0</tex> в <tex>4</tex>-м столбце выше диагонали.|-align="center"|!<center>{| alignclass="leftwikitable" classalign="collapsible collapsedcenter" style="textcolor: blue; background-aligncolor:left#ffffcc;" cellpadding="10"|+|-align="center" ! Solutionclass="dark" style="font-weight:normal"| <tex>1</tex> !class="dark" style="font-weight:normal"|<tex>0</tex> !class="dark" style="font-weight:normal"| <tex>0</tex> !class="dark" style="font-weight:normal"| If the <tex>0</tex> !class="green" style="font color-weight:normal" style=red"background: #ddffdd;"| <tex> red clause 0</fonttex> is present: || Unsolvable<tex>K=I \oplus J</tex>|-align="center" !class="dark" style="font-weight:normal"| Else<tex>0</tex> !class="dark" style="font-weight: normal"|<tex>1</tex> !class="dark" style="font-weight:normal"| ''a'' <tex>0</tex> !class="dark" style= "font-weight:normal"| <tex>0 </tex> !class= FALSE"green" style="font-weight:normal" style="background: #ddffdd;"|-<tex>1</tex>| || ''b'' <tex>L= 1 = TRUEE \oplus J</tex>|-align="center"| || ''c'' !class= 0 "dark" style= FALSE"font-weight:normal"|-<tex>0</tex>| || ''d'' !class= 1 "dark" style= TRUE"font-weight:normal"|-<tex>0</tex>| colspan !class="2dark" | '''As a consequencestyle="font-weight:'''normal"|-<tex>1</tex>| colspan !class="2dark" style="font-weight:normal" | ''R''(''a'',''c'',''d'') ∧ ''R''(''b'',¬''c'',''d'') ∧ ''R''(''a'',''b'',¬''d'') ∧ ''R''(''a'',¬''b'',¬''c'')<tex>0</tex> !class="green" style="font color-weight:normal" style=red"background: #ddffdd;"| <tex> ∧ ''R''(¬''a'',''b'',''c'') 0</tex>| <tex>J</fonttex>|-align="center"| colspan !class="2dark" style=" | is not 1font-in-3-satisfiable,weight:normal"|-<tex>0</tex>| colspan !class="dark" style="2font-weight:normal" | while (''a''∨''c''∨''d'') ∧ (''b''∨¬''c''∨''d'') ∧ (''a''∨''b''∨¬''d'') ∧ (''a''∨¬''b''∨¬''c'')<tex>0</tex> !class="dark" style="font-weight:normal"|-<tex>0</tex>| colspan !class="dark" style="2font-weight:normal" | <tex>1</tex> is 3-satisfiable with ''a''!class=''c''"green" style=FALSE and ''b''"font-weight:normal" style=''d''=TRUE."background: #ddffdd;"| <tex>1</tex>| <tex>H</tex>

[[Файл:Булева выполнимость.png|400px|thumb|down|Формула с <tex>2</tex>-мя дизъюнктами может быть неудовлетворена(красный),<btex>3</tex>-<tex>\mathrm {3-SAT}</tex></b>(зелёный),<b><tex>\mathrm {XOR}</tex>-<tex>3</tex>-<tex>\mathrm {SAT}</tex></b>(синий) ,ИЛИили/И и <btex>1</tex>-<tex>\mathrm {1-in}</tex>-<tex>3</tex>-<tex>\mathrm {SAT}</tex></b>, в зависимости от количества переменных со значением TRUE <tex> \mathtt {true}</tex> в <tex>1</tex>-м (горизонтальном) и втором (вертикальном) дизъюнктеконъюнкте.]]Поскольку <b><tex>a \oplus b \mathrm {a}oplus c</tex></b> <b>принимает значение <tex>\mathrm mathtt {XORtrue}</tex></b> <b>, если и только если <tex>\mathrm {b}1</tex></b> <b>из <tex>\mathrm {XOR}3</tex></b> <b>переменных <tex>\mathrm {a,\ b,\ c\}</tex></b> принимает значение <b><tex>\mathrm mathtt {TRUEtrue}</tex>, каждое решение в </btex>,если и только если 1 из 3 переменных {a,b,c} принимает значение <b/tex>-<tex>\mathrm {TRUEin}</tex>-</btex> ,каждое решение в 3<b/tex>-<tex>\mathrm {1-in-3-SAT}</tex></b> задачи для данной КНФ-формулы является также решением <b><tex>\mathrm {XOR}</tex>-<tex>3</tex>-<tex>\mathrm {SAT}</tex></b> задачи, и ,в свою очередь,обратное также верно. <br>Как следствие, для каждой КНФ-формулы, можно решить <b><tex>\mathrm {XOR}</tex></b>-<b><tex>\mathrm {3}</tex></b>-<b><tex>\mathrm {SAT}</tex></b> -задачу и на основании результатов сделать вывод, что либо <btex>3</tex>-<tex>\mathrm {3-SAT-задача}</tex></b> задача решаема или, что <btex>1</tex>-<tex>\mathrm {1-in}</tex>-<tex>3</tex>-<tex>\mathrm {SAT-задача}</tex>-задача нерешаема.</bbr> нерешаема.При условии ,что <tex>\mathrm {P}</tex>- и <tex>\mathrm {NP}</tex>-классы не равны,ни <tex>2</tex>-,ни Хорн-,ни <b><tex>\mathrm {XOR-SAT}</tex>-<tex>\mathrm {SAT}</btex> не являются задачи [[Класс NP|<tex>\mathrm {NP}</tex>-класса]],в отличии от <tex>\mathrm {SAT}</tex>.

* ''Cook, Stephen A. (1971). ''Proceedings of the 3rd Annual ACM Symposium on Theory of Computing: 151–158, 1971.

[[Категория: Булевы функции ]]