XOR-SAT — различия между версиями
м (→Решения XOR-SAT задачи методом Гаусса) |
(→Описание) |
||
| Строка 6: | Строка 6: | ||
== Описание == | == Описание == | ||
| − | Одним из особых случаев <b><tex>\mathrm {SAT}</tex></b> является класс задач, где каждый дизъюнкт содержит операции <tex>\oplus</tex> (т. е. исключающее или), а не (обычные) <tex>\lor</tex> операторы.(Формально, обобщенная КНФ с тернарным булевым оператором R работает только если 1 или 3 переменные дают TRUE в своих аргументах. Дизъюнкт,имеющие более 3 переменных могут быть преобразованы в сочетании с формулой преобразования с сохранением выполнимости булевой функции(ссылка на книгу ниже), т. е. XOR-SAT может быть снижена до XOR-3-SAT)<ref>Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley.; здесь: Thm.10.4</ref> | + | Одним из особых случаев <b><tex>\mathrm {SAT}</tex></b> является класс задач, где каждый дизъюнкт содержит операции <tex>\oplus</tex> (т. е. исключающее или), а не (обычные) <tex>\lor</tex> операторы.(Формально, обобщенная КНФ с тернарным булевым оператором R работает только если 1 или 3 переменные дают <b><tex>\mathrm {TRUE}</tex></b> в своих аргументах. Дизъюнкт,имеющие более 3 переменных могут быть преобразованы в сочетании с формулой преобразования с сохранением выполнимости булевой функции(ссылка на книгу ниже), т. е. <b><tex>\mathrm {XOR}</tex></b>-<b><tex>\mathrm {SAT}</tex></b> может быть снижена до <b><tex>\mathrm {XOR}</tex></b>-<b><tex>\mathrm {3}</tex></b>-<b><tex>\mathrm {SAT}</tex></b>)<ref>Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley.; здесь: Thm.10.4</ref> |
| − | Это задача [[Класс P|Р-класса]],так как XOR-SAT формулу можно рассматривать как систему линейных уравнений по модулю 2,которая ,в свою очередь, может быть решена за <tex>O(n^3)</tex> [https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%93%D0%B0%D1%83%D1%81%D1%81%D0%B0 | + | Это задача [[Класс P|Р-класса]],так как <b><tex>\mathrm {XOR}</tex></b>-<b><tex>\mathrm {SAT}</tex></b> формулу можно рассматривать как систему линейных уравнений по модулю 2,которая ,в свою очередь, может быть решена за <tex>O(n^3)</tex> методом Гаусса<ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%93%D0%B0%D1%83%D1%81%D1%81%D0%B0]</ref>.Такое представление возможно на основе связи между Булевой алгеброй и Булевым кольцом <ref>[https://en.wikipedia.org/wiki/Boolean_algebra_(structure)#Boolean_rings]<\ref> и тот факт,что арифметика по модулю 2 образует конечное поле <ref>[https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D0%BE%D0%B5_%D0%BF%D0%BE%D0%BB%D0%B5]<\ref>. |
==Решение XOR-SAT задачи методом Гаусса== | ==Решение XOR-SAT задачи методом Гаусса== | ||
Версия 02:09, 3 января 2017
| Задача: |
| (XOR-satisfiability) выполнимость функции — задача распределения аргументов в булевой КНФ функции, записанной в виде XOR-КНФ, таким образом, чтобы результат данной функции был равен . |
Содержание
Описание
Одним из особых случаев является класс задач, где каждый дизъюнкт содержит операции (т. е. исключающее или), а не (обычные) операторы.(Формально, обобщенная КНФ с тернарным булевым оператором R работает только если 1 или 3 переменные дают в своих аргументах. Дизъюнкт,имеющие более 3 переменных могут быть преобразованы в сочетании с формулой преобразования с сохранением выполнимости булевой функции(ссылка на книгу ниже), т. е. - может быть снижена до --)[1]
Это задача Р-класса,так как - формулу можно рассматривать как систему линейных уравнений по модулю 2,которая ,в свою очередь, может быть решена за методом Гаусса[2].Такое представление возможно на основе связи между Булевой алгеброй и Булевым кольцом <ref>[2]<\ref> и тот факт,что арифметика по модулю 2 образует конечное поле <ref>[3]<\ref>.
Решение XOR-SAT задачи методом Гаусса
| Solving an XOR-SAT example by Gaussian elimination | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Вычислительная сложность
Поскольку a XOR b XOR c принимает значение TRUE,если и только если 1 из 3 переменных {a,b,c} принимает значение TRUE,каждое решение в 1-in-3-SAT задачи для данной КНФ-формулы является также решением XOR-3-SAT задачи,и ,в свою очередь,обратное также верно. Как следствие, для каждой КНФ-формулы, можно решить XOR-3-SAT -задачу и на основании результатов сделать вывод, что либо 3-SAT-задача решаема или, что 1-in-3-SAT-задача нерешаема. При условии ,что P- и NP-классы не равны,ни 2-,ни Хорн-,ни XOR-SAT не являются задачи NP-класса,в отличии от SAT.
См. также
Примечания
Источники информации
- Википедия — Boolean satisfiability problem
- Cook, Stephen A. (1971). Proceedings of the 3rd Annual ACM Symposium on Theory of Computing: 151–158.
