Изменения

Перейти к: навигация, поиск

XOR-SAT

603 байта убрано, 17:09, 7 января 2017
→‎Следствие
<tex>c=0=\mathtt {false}</tex><br>
<tex>d=1=\mathtt {true}</tex><br>
===Следствие===
{| class="wikitable"
!<tex>R(a,\ b,\ c) \land R(b,\ \neg c ,\ d) \land R(a,\ b ,\ \neg d) \land R(a ,\ \neg b ,\ \neg c)</tex>
! style="background: #ffdddd;" |<tex> \land (\neg a,\ b ,\ c) </tex>
|} Не является решением <tex>1</tex>-<tex>\mathrm {in}</tex>-<tex>3</tex>-<tex>\mathrm {SAT}</tex>,a <tex>(a \lor c \lor d) \land (b \lor \neg c \lor d) \land (a \lor b \lor \neg d) \land (a \lor \neg b \lor \neg c)</tex> является решением <tex>3</tex>-<tex>\mathrm {SAT}</tex> с <tex>a=c=\mathtt {false}</tex> и <tex>b=d=\mathtt {true}</tex>.
 
==Вычислительная сложность==
[[Файл:Булева выполнимость.png|400px|thumb|down|Формула с <tex>2</tex>-мя дизъюнктами может быть неудовлетворена(красный), <tex>3</tex>-<tex>\mathrm {SAT}</tex>(зелёный), <tex>\mathrm {XOR}</tex>-<tex>3</tex>-<tex>\mathrm {SAT}</tex>(синий), или/и <tex>1</tex>-<tex>\mathrm {in}</tex>-<tex>3</tex>-<tex>\mathrm {SAT}</tex>, в зависимости от количества переменных со значением <tex> \mathtt {true}</tex> в <tex>1</tex>-м (горизонтальном) и втором (вертикальном) конъюнкте.]]
Павел Хужин
62
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/59091»

Навигация