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