Изменения

Перейти к: навигация, поиск

XOR-SAT

6 байт добавлено, 00:06, 5 января 2017
Описание
Это задача [[Класс P|Р-класса]],так как <b><tex>\mathrm {XOR}</tex></b>-<b><tex>\mathrm {SAT}</tex></b> формулу можно рассматривать как систему линейных уравнений по модулю 2,которая ,в свою очередь, может быть решена за <tex>O(n^3)</tex> методом Гаусса<ref>12213|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 задачи методом Гаусса==
62
правки

Навигация