XOR-SAT — различия между версиями
(Новая страница: «{{Задача |definition = <b><tex>\mathrm {XORSAT}</tex></b> (XOR-satisfiability) выполнимость функции — задача распределе...») |
м (→Решения XOR-SAT задачи методом Гаусса) |
||
| Строка 11: | Строка 11: | ||
Это задача [[Класс 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 методом Гаусса].Такое представление возможно на основе [https://en.wikipedia.org/wiki/Boolean_algebra_(structure)#Boolean_rings связи между Булевой алгеброй и Булевым кольцом] и тот факт,что арифметика по модулю 2 образует [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 конечное поле]. | Это задача [[Класс 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 методом Гаусса].Такое представление возможно на основе [https://en.wikipedia.org/wiki/Boolean_algebra_(structure)#Boolean_rings связи между Булевой алгеброй и Булевым кольцом] и тот факт,что арифметика по модулю 2 образует [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 конечное поле]. | ||
| − | == | + | ==Решение XOR-SAT задачи методом Гаусса== |
{| align="center" class="wikitable collapsible collapsed" style="text-align:left; margin: 1em" | {| align="center" class="wikitable collapsible collapsed" style="text-align:left; margin: 1em" | ||
| Строка 238: | Строка 238: | ||
|} | |} | ||
|} | |} | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
==Вычислительная сложность== | ==Вычислительная сложность== | ||
Версия 19:30, 2 января 2017
| Задача: |
| (XOR-satisfiability) выполнимость функции — задача распределения аргументов в булевой КНФ функции, записанной в виде XOR-КНФ, таким образом, чтобы результат данной функции был равен . |
Содержание
Описание
Одним из особых случаев является класс задач, где каждый дизъюнкт содержит операции (т. е. исключающее или), а не (обычные) операторы.(Формально, обобщенная КНФ с тернарным булевым оператором R работает только если 1 или 3 переменные дают TRUE в своих аргументах. Дизъюнкт,имеющие более 3 переменных могут быть преобразованы в сочетании с формулой преобразования с сохранением выполнимости булевой функции(ссылка на книгу ниже), т. е. XOR-SAT может быть снижена до XOR-3-SAT)[1]
Это задача Р-класса,так как XOR-SAT формулу можно рассматривать как систему линейных уравнений по модулю 2,которая ,в свою очередь, может быть решена за методом Гаусса.Такое представление возможно на основе связи между Булевой алгеброй и Булевым кольцом и тот факт,что арифметика по модулю 2 образует конечное поле.
Решение 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.
См. также
Примечания
- ↑ Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley.; здесь: Thm.10.4
Источники информации
- Википедия — Boolean satisfiability problem
- Cook, Stephen A. (1971). Proceedings of the 3rd Annual ACM Symposium on Theory of Computing: 151–158.
