Омский государственный университет им. Ф.М.Достоевского

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

Литература:

1. Беспалов Д.В., О логических выражениях для задачи 2-ФАКТОРИЗАЦИЯ // Беспалов Д.В. Семёнов А.А.Вычислительные технологии. – 2002. – Т.7 – Ч.2.
2. Файзуллин Р.Т. О решении нелинейных алгебраических систем гидравлики // Сибирский журнал индустриальной математики. -1999.-№2. –С. 176-184.
3. Файзуллин Р.Т., Алгоритм минимизации функционала, ассоциированного с задачей 3-SAT и его практические применения, // Файзуллин Р.Т., Хныкин И.Г., Дулькейт В.И., Салаев Е.В.- г.Челябинск, 2007.
4. Хныкин И.Г., Модификация КНФ, эквивалентных задачам криптоанализа асимметричных шифров
   методом резолюции // ИТМУ № 8, 2007.
5. Cook S.A. The Complexity of Theorem Proving Procedures. Proceedings Third Annual ACM Symposium on Theory of Computing, May 1971.

---

© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846 2) 332-56-22, факс: +7 (846 2) 332-56-20