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> задачи, и ,в свою очередь,обратное также верно. <br>Как следствие, для каждой КНФ-формулы, можно решить <b><tex>\mathrm {XOR}</tex></b>-<b><tex>\mathrm {3}</tex></b>-<b><tex>\mathrm {SAT}</tex></b> -задачу и на основании результатов сделать вывод, что либо <b><tex>\mathrm {3}</tex></b>-<b><tex>\mathrm {SAT-задача}</tex></b> решаема или, что <b><tex>\mathrm {1-in-3-SAT-задача}</tex></b> нерешаема.<br>
При условии ,что P- и NP-классы не равны,ни 2-,ни Хорн-,ни <b><tex>\mathrm {XOR-SAT}</tex></b> не являются задачи [[Класс NP|NP-класса]],в отличии от SAT.
