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