Я выложенную выше статью не перечитывал (времени нет), могу лишь навскидку по памяти... Задача заключается в том, что есть некое булево уравнение вроде
(a and b) or (c xor d) = 1.
Его надо решить, т.е. найти такие значения переменных a, b, c и d, для которых оно истинно. Аналитически задача решается только в ограниченных и очень простых случаях, в реальных ситуациях либо полный перебор (а это 2^n шагов, где n - число переменных), либо хитрости. Задача кстати, также как и моя (разбиения), из класса NP. Хитрости заключаются в том, что разными способами можно ограничивать перебор. В данном случае уравнение можно разбить на два более простых:
a and b = 1 => решение a=1, b=1;
c xor d = 1 => решения c=0, d=1 и c=1, d=0.
Ну а дальше их нужно объединить:
a=1, b=1, c=*, d=*;
a=*, b=*, c=0, d=1;
a=*, b=*, c=1, d=0 ("*" - любое значение аргумента).
В реальных задачах число подуравнений (там у них в оригинале это как-то по другому называлось - то ли термы, то ли еще как-то, не помню) может быть очень велико и не влезть в ОЗУ - возникает еще одна непростая задачка: как влезающим в ОЗУ ограниченным числом уравнений максимально упростить перебор. Надеюсь понятно объяснил
Насчет практических применений затрудняюсь привести конкретный пример. Имхо к поиску простых чисел эта задача не имеет отношения, ко взлому некоторых криптосистем - вполне может (выводы о полезности проекта делайте сами, сам пока активно считать не планирую). Но я вполне могу ошибаться и авторы проекта скорее всего могут дать более интересное описание своего видения перспектив для полученных результатов. Спросил у них в
форуме, ждем реакции...
См. также:
ru.wikipedia.org/wiki/За...олнимости_булевых_формул
kvt.kurskstu team founder
separator application developer
