62
правки
Изменения
→Вычислительная сложность
Поскольку <tex>a\ XOR\ b\ XOR\ c</tex> принимает значение <tex> \mathtt {true}</tex>,если и только если <tex>1</tex> из <tex>3</tex> переменных {<tex>a</tex>,<tex>b</tex>,<tex>c</tex>} принимает значение <tex> \mathtt {true}</tex> ,каждое решение в <tex>1</tex>-<tex>\mathrm {in}</tex>-<tex>3</tex>-<tex>\mathrm {SAT}</tex> задачи для данной КНФ-формулы является также решением <tex>\mathrm {XOR}</tex>-<tex>3</tex>-<tex>\mathrm {SAT}</tex> задачи, и ,в свою очередь,обратное также верно.<br>
Как следствие, для каждой КНФ-формулы, можно решить <tex>\mathrm {XOR}</tex>-<tex>3</tex>-<tex>\mathrm {SAT}</tex>-задачу и на основании результатов сделать вывод, что либо <tex>3</tex>-<tex>\mathrm {SAT}</tex> задача решаема или, что <tex>1</tex>-<tex>\mathrm {in}</tex>-<tex>3</tex>-<tex>\mathrm {SAT}</tex>-задача нерешаема.<br>
При условии ,что P- и NP-классы не равны,ни <tex>2</tex>-,ни Хорн-,ни <tex>\mathrm {XOR}</tex>-<tex>\mathrm {SAT}</tex> не являются задачи [[Класс NP|NP-класса]],в отличии от <tex>\mathrm {SAT}</tex>.
== См. также ==
