XOR-SAT

Материал из Викиконспекты
Версия от 19:29, 2 января 2017; Павел Хужин (обсуждение | вклад) (Новая страница: «{{Задача |definition = <b><tex>\mathrm {XORSAT}</tex></b> (XOR-satisfiability) выполнимость функции — задача распределе...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск
Задача:
[math]\mathrm {XORSAT}[/math] (XOR-satisfiability) выполнимость функции — задача распределения аргументов в булевой КНФ функции, записанной в виде XOR-КНФ, таким образом, чтобы результат данной функции был равен [math] 1 [/math].


Описание

Одним из особых случаев [math]\mathrm {SAT}[/math] является класс задач, где каждый дизъюнкт содержит операции [math]\oplus[/math] (т. е. исключающее или), а не (обычные) [math]\lor[/math] операторы.(Формально, обобщенная КНФ с тернарным булевым оператором R работает только если 1 или 3 переменные дают TRUE в своих аргументах. Дизъюнкт,имеющие более 3 переменных могут быть преобразованы в сочетании с формулой преобразования с сохранением выполнимости булевой функции(ссылка на книгу ниже), т. е. XOR-SAT может быть снижена до XOR-3-SAT)[1]


Это задача Р-класса,так как XOR-SAT формулу можно рассматривать как систему линейных уравнений по модулю 2,которая ,в свою очередь, может быть решена за [math]O(n^3)[/math] методом Гаусса.Такое представление возможно на основе связи между Булевой алгеброй и Булевым кольцом и тот факт,что арифметика по модулю 2 образует конечное поле.

Решения XOR-SAT задачи методом Гаусса




Вычислительная сложность

Формула с 2-мя дизъюнктами может быть неудовлетворена(красный),3-SAT(зелёный),XOR-3-SAT(синий) ,ИЛИ/И 1-in-3-SAT, в зависимости от количества переменных со значением TRUE в 1-м (горизонтальном) и втором (вертикальном) дизъюнкте.

Поскольку 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.







См. также

Примечания

  1. Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley.; здесь: Thm.10.4

Источники информации