Алгоритм минимизации функционала, ассоциированного с задачей 3-SAT и его практические применения

Одной из наиболее интересных задач дискретной математики является задача поиска решающего набора в задаче ВЫПОЛНИМОСТЬ. После классической работы Кука [5] усилия многих исследователей были направлены на построение эвристических, переборных алгоритмов решения КНФ. Перспективным направлением представляется и сведение КНФ к непрерывному аналогу, к задаче поиска точек глобального минимума ассоциированного функционала. В данной работе обосновывается выбор функционала специального вида и предлагается применить к решению системы нелинейных алгебраических уравнений, определяющих стационарные точки функционала, модифицированный метод последовательных приближений. В работе также показано, что метод может быть с успехом применен к важным задачам криптографического анализа несимметричных шифров.