Изменения

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