Алгоритмы поиска решения задачи об F-выполнимости, основанные на приближении булевых функций к классам Шефера тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА

Поцелуевская Евгения Александровна

Алгоритмы поиска решения задачи об

Е-выпо лнимости, основанные на приближении булевых функций к классам Шефера

Специальность 01.01.09 - Дискретная математика и математическая кибернетика

УДК 519.712.2

На правах рукописи

005016793

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 0 мЛ~1

Москва - 2012

005016793

Работа выполнена на кафедре Математической теории интеллектуальных систем Механико-математического факультета Московского государственного университета имени М.В. Ломоносова.

Научный руководитель: кандидат физико-математических наук Носов Валентин Александрович

Официальные оппоненты: Кузюрин Николай Николаевич,

Защита состоится 25 мая 2012 г. в 16-45 на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М.В. Ломоносова по адресу: Российская Федерация, 119991, Москва, Ленинские горы, д.1, МГУ имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ (Главное здание, 14 этаж).

доктор физико-математических наук Институт системного программирования РАН заведующий отделом, профессор

Тарасов Алексей Вячеславович кандидат физико-математических наук Институт криптографии, связи и информатики Академии ФСБ России начальник кафедры

Ведущая организация: Национальный исследовательский университет «МЭИ»

Автореферат разослан 25 апреля 2012 г.

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ доктор физико-математических наук, профессор

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Проблема выполнимости булевых формул является одной из классических задач дискретной математики и формулируется следующим образом. Дана формула над булевыми переменными Xi,..., хп, имеющая вид:

(aft V • ■ ■ V V ■ ■ • V ... V ■ • • V х^),

где (a,, Pi,..., 7i - булевы константы). Необходимо определить, существует ли набор значений переменных Х\ = ai,...,xn = ап, обращающий формулу в единицу.

В 1971 году Стивеном Куком был доказан фундаментальный для теории сложности вычислительных систем результат1, заключающийся в том, что задача о выполнимости является NP-полной. Тем самым был поднят вопрос о равенстве классов сложности Р и NP, который остаётся открытым до сих пор.

Вскоре было установлено, что для некоторых классов функций существуют алгоритмы, позволяющие решить задачу за полиномиальное время, к таким классам, в частности, относятся функции, где в записи в конъюнктивной нормальной форме (КНФ) в каждой дизъюнкции задействовано не более 2 переменных (2-КНФ)2, класс функций, КНФ которых состоит из дизъюнктов Хорна3, а также ряд других классов4.

Алгоритмы для поиска решения задачи о выполнимости появлялись начиная с 60-х годов прошлого века и продолжают активно исследоваться вплоть до сегодняшнего дня. Обзор наиболее заметных результатов в этой области можно найти в монографиях Handbook of Satisfiability5,

1 Cook S. A. The Complexity of Theorem Proving Procedures // Proc. 3rd Ann. ACM Symp. on Theory of Computing (STOC 71). - 1971. - P. 151-158

2Even S., Itai A., Shamir A. On the complexity of timetable and multi-commodity flow problems // SIAM Journal of Computing. -No. 5(4). -1976

Aspvall В., Plass M.F., Tarjan R,.E. A linear-time algorithm for testing the truth of certain quantified boolean formulas // Information Processing Letters. - No. 8(3). - March 1979. - P. 121-123

3Dowling W.F., Gallier J.H. Linear-time algorithms for testing the satisfiability of prepositional Horn formulas//Journal of Logic Programming. - No. 1(3). - 1984. -P. 267-284

4Franco J., Gelder A.V. A perspective on certain polynomial-time solvable classes of satisfiability // Discrete Applied Mathematics. - Vol. 125. - Issues 2-3. -2003. - P. 177-214

Алексеев В.Б., Носов В.А. NP-палные задачи и их полиномиальные варианты. Обзор // Обозрение прикладной и промышленной математики. - 1997. - Т. 4. - Вып. 2. - С. 165-193

5Biere A., Heule М., van Maaren H., Walsh Т., eds. Handbook of Satisfiability. // Vol. 185 of Frontiers in Artificial Intelligence and Applications. - IOS Press, 2009. - 981 pp.

Introduction to mathematics of satisfiability, в работе Всемирнова M.A., Гирша Э.А., Данцина Е.Я. и Иванова С.В. «Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности»7, в сборнике Дингжу, Гу и Пардалоса Satisfiability problem: theory and applications8.

К наиболее распространенным техникам решения задачи относятся: детерминированные алгоритмы класса DPLL, основанные на на процедурах, описанных в работах Дэвиса и Патнема9 и Дэвиса, Лоджмана и Лавлэнда10; вероятностные алгоритмы класса PPSZ11; вероятностные алгоритмы, основанные на случайных блужданиях, и, в •частности, ал-.горитм Шонинга12; детерминированные алгоритмы, полученные деран-домизацией вероятностных алгоритмов13.

Также интерес представляет нахождение классов функций, для которых возможно полиномиальное решение задачи об F-выполнимости, которая является обобщением задачи выполнимости и частным случаем задачи выполнимости систем ограничений (constraint satisfaction problem, CSP). Задача формулируется следующим образом: дано F = F\,..., Fs - любое конечное множество формул (функциональных символов). F-формула определяется как конъюнкция Ftl(-)Fi,(-)... F,-((•) с переменными Х\,... ,хп, расставленными некоторым образом. Необходимо определить существует ли набор значений переменных, обращающий ^-формулу в единицу. Задача об F-выполнимости полиномиально сводится к задаче о выполнимости и основное её отличие от задачи о выполнимости заключается в том, что она имеет другую длину входа.

'Marek V. W. Introduction to mathematics of satisfiability. - CRC Press, 2009. - 365 p.

7Всемирнов M.A., Гирш Э.А., Данцин Е.Я., Иванов С.В. Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности // Теория сложности вычислений. VI, Зап. научн. сем. ПОМИ, 277, ПОМИ, СПб. - 2001

8Dingzhu Du, Лип Gu, Panos М. Pardalos. Satisfiability problem: theory and applications // Proceedings of a DIMACS workshop, March 11-13 1996. - 1996

'Davis M., Putman H. A computing procedure for quantification theory // Journal of the ACM. -I960. - No. 7(3). - P. 201-215

10Davis M., Logeman G., Loveland D. A machine program for theorem-proving // Communications of the ACM. - 1962. - No. 5(7). - P. 394-397

"Paturi R., PudlAk P., Saks M.E., Zane F. An improved exponential-time algorithm for k-SAT // Journal of the ACM. - Vol. 52. - No. 3. - 2005. - P. 337-36

12Shoning U. A probabilistic algorithm for k-SAT and constraint satisfaction problems // Proceedings of FOCS'99. - 1999. - P. 410-414

"Dantsin E., Goerdt A., Hirsch E. A., Kannan R., Kleinberg J., Papariimitriou C., Raghavan O., Schoning U. A deterministic (2 - 2/(fc + l))n algorithm for k-SAT based on local search // Theoretical Computer Science. - Vol. 289. - Issue 1. - P. 69-83. - 2002

В работе The complexity of satisfiability problems14 Шефер выделил следующие 6 классов булевых функций, для которых обобщенная проблема F-выполнимости решается за полиномиальное время:

• О-выполнимые функции (0-ВЫП): все функции J, для которых верно: /(О,..., 0) = 1;

• 1-вьшолнимые функци (1-ВЫП)и: все функции /, для которых верно /(1.....1) = 1;

• слабоотрицательные функции (CJ10): все функции /, для которых существует запись в КНФ, в которой каждый дизъюнкт содержит только переменные с отрицаниями кроме, быть может, одной (также известны как дизъюнкты Хорна), т.е. формула вида:

V V • ■ • V xik){xeh V xh V • ■ • V xJt).. - (xl V x-t2 V • • ■ V x~tt), где (a, /3,..., 7 - булевы константы).

• слабоположительные функции (СЛП): все функции /, для которых существует запись в КНФ, в которой каждый дизъюнкт содержит только переменные без отрицаний, кроме, быть может, одной, т.е. формула вида:

V xi2 V • ■ • V xh)(x^ V xh V • • • V xjt)... (xl V xt2 V ■ • • V xtk), где (a. /3,..., 7- булевы константы).

• мультиаффинные функции (МАФ): все функции /, которым соответствует формула, представляющая собой конъюнкцию линейных форм, т.е. формула вида:

(ai^i + ... а„хп + a0)(bixi + ... bnxn + bo).. ■ [с\Х\ + ... с„хп + со), где (aj,bi,...,Ci- булевы константы).

• биюнктивные функции (БИН): все функции /, для которых существует запись в КНФ, где каждая скобка содержит ровно две переменные, т.е. формула вида

,4Schaefer Т.Л. The complexity of satisfiability problems // Proceedings of the 10th ACM Symposium on Theory of Computing. - 1978. - P. 216-226

где (a*,Pi,... ,7г булевы константы).

Вопрос о размерах и свойствах классов Шефера глубоко изучался начиная с момента описания этих классов самим Шефером. В частности, значительный вклад в изучение данного вопроса внесли работы Алексеева В.В.,Горшкова С.П, Гизунова С.А, Носова В.А и Тарасова А.В.15. Среди зарубежных авторов наиболее весомый вклад в эту область внесли работы Нади Крейгноу, Стефана Рейта, Эльмара Бёлера, и других соавторов 16.

15Алексеев В.Б. О числе семейств подмножеств, замкнутых относительно пересечения // Дискретная математика. - 1989. - Т. 1. - Вып. 2. - С. 129-136.

Алексеев В.Б., Носов В.А. NP-полные задачи и их полиномиальные варианты. Обзор // Обозрение прикладной и промышленной математики. - 1997. - Т. 4. - Вып. 2. - С. 165-193. Гтаунов С.А., Носов В.А. Сложность распознавания классов Шефера // Вестник МГУ. - 1995.

- Сер. 1.

Гизунов С.А., Носов В.А. О классификации всех булевых функций 4-х переменных по классам Шефера // Обозрение прикладной и промышленной математики. - 1995. - Т. 1. - Вып. 3. -С. 440-467

Горшков С.П. Применение теории NP-полных задач для оценки сложности решения систем булевых уравнений // Обозрение прикладной и промышленной математики. - 1995. - Т. 1. - Вып. 3.

- С. 325-398

Горшков С. П. О сложности распознавания мультиаффинности, биюнктивности, слабой положительности и слабой отрицательности булевых функций // Обозрение прикладной и промышленной математики. Серия «Дискретная математика». - 1997. - Т. 4. - Вып. 2. - С. 216-237

Горшков С.П. О сложности задачи нахождения числа решений систем булевых уравнений // Дискретная математика. - 1996. - Т. 8. - Вып. 1. - С. 72-85

Горшков С.П. О пересечении классов мультиаффинньгх, биюнктивных, слабо положительных и слабо отрицательных булевых функций // Обозрение прикладной и промышленной математики. Серия «Дискретная математика». ТВП. - 1997. - Т. 4. - Вып. 2. - С. 238-259

Горшков С.П., Тарасои А.В. О максимальных группах инвариантных преобразований мультиаф-финных, биюнктивных, слабо положительных и слабо отрицательных булевых функций // Дискретная математика. - 2009. - Т. 21. - Вып. 2. - С. 94-101

'"Bohler Б., Creignou N., Reith S., Vollmer H. Playing with Boolean blocks, part I: Post's lattice with applications to complexity theory // SIGACT News, Complexity Theory. - 2003. - Column 42, 34(4).

- P. 38-52

Bohler E., Creignou N., Reith S., Vollmer H. Playing with Boolean blocks, part II: Constraint satisfaction problems // SIGACT News, Complexity Theory. - 2004. - Column 43, 35(1). - P. 2235

Creignou N., Hermann J. Complexity of generalized satisfiability counting problems // Information and Computation. - 1996. - V. 125 - No. 1. - P. 1-12

Creignou N., Hebrard J. On generating all satisfying truth assignments of a generalized CNF-formula // Theoretical Informatics and Applications. - 1997. - V. 31. - No. 6. - P. 499-511

Creignou N., Hermann M. Complexity of constraint satisfaction problems// Survey Document for CP 2001 Tutorial. - 2001. - 33 pp

Creignou N., Khanna S., Sudan M. Complexity classifications of Boolean constraint satisfaction problems // SIAM Monographs on Discrete Mathematics and Applications/ SIAM, Philadelphia. -2001. - 106 pp

Поиск случаев, когда задачи выполнимости и F-выполнимости решаются за полиномиальное время, важен и для многих прикладных задач. В частности, тесты, основанные на проблеме выполнимости сегодня широко применяются для автоматизации проектирования, а также для проверки разрабатываемых программ. К прикладным задачам, для решения которых применяется данная проблема, также относятся: определение перекрестных помех в интегральных схемах17, верификация моделей для параллельных систем с конечным числом состояний18, вывод гаплотипа в биоинформатике19, а также многие другие задачи20. С другой стороны, выявление сложных случаев задачи о выполнимости, представляет интерес для построения эффективных систем защиты информации.

В диссертации рассматривается вопрос изучения некоторых частных свойств классов Шефера, которые могли бы быть полезными для быстрого решения задачи об F-выполнимости или, напротив, для формирования задач, сложных для решения, а также вопрос построения алгоритмов поиска решения задачи об F-выполнимости, основанных на свойствах классов Шефера.

Актуальность диссертационной работы определяется теоретической значимостью задачи о выполнимости для области дискретной математики, а также широким практическим применением задачи о выполнимости, что делает востребованными алгоритмы, позволяющие для некоторых классов функций решать данную задачу за полиномиальное время.

Цель работы и задачи исследования. Цель диссертации состоит в разработке новых алгоритмов решения задачи о выполнимости, основанных на классах Шефера, и в изучении свойств классов Шефера.

Creignou N. Boolean CSP. - Universite de la Mediterranee, 2006. - 82 pp

Reith S., Wagner K.W. The Complexity of Problems Defined by Subclasses of Boolean Functions // Technical Report 218, Lehrstuhl für Theoretische Informatik. - Universität Würzburg. - January 1999 ,7Chen P., Keutzer K. Towards true crosstalk noise analysis // International Conference on Computer-Aided Design. - November 2009. - P. 132-138

18Biere A., Cimatti A., Clarke E., Zhu Y. Symbolic model checking without BDDs // Tools and Algorithms for the Construction and Analysis of Systems. - May 2009. - P. 193-207

Sheeran M., Singh S., Stalmarck G. Checking safety properties using induction and a SAT solver // Formal Methods in Computer-Aided Disign. - 2000. -P. 108-125

Mcmillan K.L. Interpolation and SAT-based model checking // Computer-Aided Verification. - 2003. - P. 1-13

19Lynce I., Marques-Silva J. Efficient, haplotype inference with Boolean satisfiability // National Conference on Artificial Intelligence. - July 2006

20Marques-Silva, J. Practical Applications of Boolean Satisfiability // Workshop on Discrete Event Systems (WODES'08), Goteborg, Sweden. - May 2008

К задачам, подлежащим исследованию в рамках диссертации, относятся:

' 1. Анализ существующих результатов (как теоретических, так и практических) в области решения задачи о выполнимости булевых формул.

2. Исследование свойств классов Шефера с точки зрения возможности использования этих свойств для решения задачи об ^-выполни -мости.

3. Разработка алгоритмов решения задачи об Р-выполнимости с использованием свойств классов Шефера.

4. Практическая реализация алгоритмов решения задачи об Р-выполнимости и сбор статистической информации о времени работы программ для различных входных данных с целью проверки быстродействия разработанных алгоритмов.

Методы исследования. В работе используются методы теории булевых функций, теории графов, теории вероятностей и теории сложности. Разработанные алгоритмы основаны на сочетании перебора значений для определенного подмножества 5 переменных х¡, задействованных в ^-формуле, и решении при каждом фиксированном наборе из 5 полиномиальной подзадачи для соответствующего класса Шефера. Также для одного из алгоритомов для ускорения работы была рассмотрена модификация классического метода «разделяй и властвуй» для решения сложных задач путем разбиения на простые подзадачи.

Научная новизна. Результаты работы являются новыми. В диссертации получены следующие основные результаты:

1. Установлены свойства классов Шефера, которые могу быть использованы для решения задачи об ^выполнимости. В частности, определена классификация по принадлежности функций к различным классам Шефера для функций из классов, получаемых путем расширения классов слабоотрицательных, слабоположительных, мультиаффинных и биюнктивных функций. Расширение осуществлялось путем добавления к классу Шефера произвольной функции и замыкания полученного множества. Данный результат

предоставляет метод для построения сложных случаев задачи об Р-выполнимости.

2. Разработаны алгоритмы решения задачи об Р-выполнимости булевых формул, основанные на приближении функций к классам БИН, СЛО, СЛП и МАФ (в зависимости от способа задания исходной формулы), а также алгоритм решения задачи об Р-выполнимости, основанный на применении метода «разделяй и властвуй». Для всех алгоритмов разработаны программы, результаты работы которых свидетельствуют об эффективности алгоритмов.

Теоретическая и практическая ценность результатов. Работа имеет теоретический характер. Её результаты работы могут найти применение в теории булевых функций в вопросе дальнейшего исследования свойств классов Шефера. Практические результаты диссертации также могут найти применение в областях, где имеет значение быстрое решение задачи о выполнимости (в частности, для автоматизации проектирования и проверки программ), а также в области защиты информации (предложена криптосистема с открытым ключом на базе задачи об ^-выполнимости). Конкретные программные реализации алгоритмов не претендуют на место универсальных решателей задач о выполнимости, так как их быстродействие основано только на близости функций к классам Шефера. Однако в сочетании с другими алгоритмами, которые быстро работают для других классов задач, использованные подходы могут быть задействованы в программных решателях задачи о выполнимости, которые широко применяются на практике.

Апробация и внедрение результатов. Результаты диссертации докладывались на следующих конференциях и семинарах:

• Международная конференция студентов, аспирантов и молодых ученых «Ломоносов 2011» (апрель 2011);

• Международный семинар «Дискретная математика-2010» (февраль 2010);

• Международная конференция студентов, аспирантов и молодых ученых «Ломоносов 2009» (апрель 2009);

• Международная конференция «Современные проблемы математики, механики и их приложения», посвященная 70-летию ректора МГУ академика В.А. Садовничего (апрель 2009);

• Международная конференция студентов, аспирантов и молодых ученых «Ломоносов 2008» (апрель 2008);

• Научно-исследовательский семинар кафедры Математической теории интеллектуальных систем «Теория автоматов» (2008-2012, неоднократно) .

Кроме того, разработка алгоритма решения задачи об F-выполни-мости функций, заданных в КНФ и зависящих не более, чем от трех переменных, осуществлялась в рамках исследовательского проекта по государственному контракту. Работа была успешно принята заказчиком с целью дальнейшего практического применения.

Публикации. Результаты диссертации опубликованы в 5 работах автора, перечень которых приведен в конце автореферета [1-5].

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы из ТО наименований (включая работы автора). Общий объем диссертации - 135 страниц. В работе содержится 8 рисунков и 12 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Во Введении приводится общая постановка задачи, а также краткое описание результатов диссертации.

В Главе 1 приведен обзор различных формулировок задачи о выполнимости, а также известных алгоритмов её решения, включая результаты последних лет. Обзор основан на результатах работы Алексеева В.Б. и Носова В.А «NP-полные задачи и их полиномиальные варианты» по проблеме NP-полноты, обзоре дискретных алгоритмов решения задачи Всемирнова М.А., Гирша Э.А., Данцина Е.Я. и Иванова С.В «Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности», на статьях из сборника Дингжу, Гу и Пардалоса Satisfiability problem: theory and, applications, монографиях Handbook of Satisfiability, Introduction to mathematics of satisfiability и других работах. Из обзора следует, что несмотря на то, что основные методы решения задачи

пропозициональной выполнимости были заложены ещё в 60-70х годах прошлого века, эта тема имеет активное развитие и сегодня, в частности ежегодно проводятся соревнования для программных решателей задачи21. Статистические данные о практической работе этих программ показывают, что для значительной части формул задача всё же может быть решена за полиномиальное время.

В Главе 2 исследуются некоторые частные свойства классов Шефе-ра, которые могли бы быть полезными для быстрого решения задачи об ^-выполнимости или, напротив, для формирования задач, сложных для решения, а также раскрывается вопрос сведения произвольных булевых функций к классам Шефера путем фиксации переменных.

Если рассмотреть оператор замыкания относительно операций, используемых для составления Р-формул [•] (переименование переменных, склеивание переменных, конъюнкция), то классы Шефера будут замкнуты относительно этого оператора. Для этого оператора приводится доказательство следующей теоремы:

Теорема 2.1 Пусть С - один из классов Шефера (0-ВЫП, 1-ВЫП, СЛП, СЛО, МАФ, БИН), д С. Тогда существует Н е [Си{д}], /г ^ 0, такая что К £ {0-ВЫЛи1-ВЫПиСЛЮСЛ(Х)МАФиБИН}.

Далее в главе рассматривается вопрос классификации булевых функций, получаемых из классов Шефера путем добавления к соответствующему классу произвольной функции и замыкания данного множества относительно оператора [.]. Каждой булевой функции / сопоставляется вектор распределения этой функции по четырем классам Шефера <У'=(<М, где:

• б{ = 1 при / 6 СЛО, б{ = О при / $ СЛО;

• 5{ = 1 при / 6 СЛП, ¿2=0 при / $ СЛП;

• = 1 при / е МАФ, 5{ = 0 при / ^ МАФ;

• б{ = 1 при / е БИН, б{ = 0 при / £ БИН.

Теорема 2.2 Пусть для ненулевых функций /ид известны векторы распределения по классам Шефера 5? и б9 соответственно. Тогда:

21 http://www.satcompetition.org

1. Если (6?,б{) 6 {(0,0), (0,1), (1,0)}, то существует Ь е [{/,5>]\([{/>] такую что 5? = 0.

2. Если (6?,б{) = (1,1), то для всех Н € {{/,д}]: 51} = 1.

Следствие 2.1 Пусть С - класс Шефера (один из классов СЛО, СЛП, МАФ, БИН). Для ненулевой функциид известен вектор ее распределения по классам Шефера 5я. Тогда:

1. Если существует / е С, такая что (59{ ,б{) € {(0,0), (0,1), (1,0)}, то существует Н 6 [Си{<7}]\[{<7}]; $ = 0; есть К не принадлежит классу, соответствующему номеру г.

2. Если существует / € М, такая что (5%,б{) = (1,1), то существует Н £ [Си{5,}]\[{^}]; $ = то есть К принадлежит классу, соответствующему номеру г.

Исходя из этого, а также из результатов, изложенных в работе «Сложность распознавания классов Шефера» С.А. Гизунова и В.А. Носова, была проведена классификация функций Л, получаемых путем расширения классов Шефера.

Далее пусть для булевой функции ¡{х\,..., хп) известно, к каким классам Шефера она принадлежит. Выясним, к каким классам Шефера будет принадлежать функция д, полученная из / фиксацией переменных. Без потери общности, будем считать, что зафиксированы переменные XI — (71, . . . , Хи = СГк-

Теорема 2.3 Если / е 0-ВЫП, то:

• при ((71,..., (Тк) — (0,..., 0), функция д еО-ВЫП;

• при ((71,..., а к) ф (0,..., 0) функция д € 0-ВЫП тогда и только тогда, когда /(<71,..., <Тк, 0,..., 0) = 1;

• В случае, если известен набор фиксируемых переменных и их значения: (xil,... ,Х{к) = (<71,... ,(Тк), вероятность того, из произвольной функции / € 0-ВЫП указанной фиксацией переменных можно получить д £ 0-ВЫП равна

22"-*-1 р0 - 22П_1 ■

и

• Вероятность получить из О-выполнимой функции веса ||/|| = N О-выполнумую функциюд произвольной фиксацией переменных составляет

ок у>лг-2 ,

^ ~ Гг '

Для класса 1-ВЫП верна аналогичная теорема.

Теорема 2.5 Пусть / е С, где С - эт,о один из классов, СЛО, СЛП, МАФ или БИН. Тогда при любой фиксации переменных полученная функция д £ С.

Теорема 2.6 Пусть про функцию / известно, что / где С - это один из классов, СЛО, СЛП, МАФ или БИН. Пусть д получена из f фиксацией переменных (а^,..., х= (<тх,..., Тогда верно следующее:

• Если среди всевозможных наборов а,/?,7, на которых для функции / нарушается условие принадлежности классу Шефера С:

СЛО: Уа, /3 £ {0,1}" : Да Л 0)/(а)/(0) = 0;

СЛП: V«, /3 е {0,1}" : Да V /?) Д а) Д/Э) = 0;

МАФ: Уа, 0,-у € {0,1}'г : /(а ф /3 © 7)/(а)/(/3) Дт) = 0;

БЯЯ: Уа, /3,7 6 {0,1}" : /М ф /37 Ф а*7) Да) Д/3) Д7) = 0;

естгъ такие наборы а',/?',7', что

' а'1= 01=11 = <ПШ, < ...

, а'к = Рк = 7к = <*к\

то д

• Я противном случае д 6 С.

В заключение приводится алгоритм, который по функции, не принадлежащей классу Шефера, и по наборам значений переменных, где нарушаются условия принадлежности этому классу, позволяет найти переменные, которые необходимо зафиксировать, чтобы перевести функцию в класс Шефера, и фиксируемый набор. При этом количество фиксируемых переменных минимально.

Теорема 2.10 Пусть функция / задана таблицей истинности, I - длина входа алгоритма. Тогда алгоритм заканчивает работу менее чем за I2 + Пс^2(I) шагов.

В Главе 3 приводятся три алгоритма решения задачи о выполнимости, основанные на сведений функций к классам Шефера (ВИН, СЛО или СЛП, МАФ), и алгоритм решения задачи о выполнимости, основанный на методе «разделяй и властвуй». Задача о выполнимости рассматривается в следующих модификациях:

1. Все функции заданы таблицами истинности или КНФ. Для данного варианта задания функций рассматриваются два случая:

(a) Все функции зависят не более, чем от трех переменных. В этом случае задача решается приближением к классу ВИН.

(b) Нет ограничений на число переменных. В этом случае задача будет решается приближением к классу СЛО или СЛП (выбор класса осуществляется в ходе работы алгоритма).

2. Все функции заданы в форме полиномов Жегалкина. Тогда задача решается приближением к классу МАФ.

Первые три алгоритма имеют схожую структуру. Для исходной ^-формулы рассматриваются следующие множества элементов, входящих в Р-формулу:

• для ВИН: Б - множество дизъюнкций, зависящих от 3 переменных;

• для СЛО/СЛП: Б - множество дизъюнкции, где число переменных без отрицаний/с отрицаниями больше 1;

• для МАФ: Р - множество нелинейных полиномов и С> - множество нелинейных мономов с учетом кратности.

Будем говорить, что множество переменных М покрывает множество £> если фиксация переменных из М приводит соответствующие элементы к виду, который требуется классом Шефера (для ВИН - не более 2 переменных в дизъюнктах, для СЛО/СЛП - не более одного литерала с без отрицания/с отрицанием, для МАФ - линейность). Алгоритмы основаны на поиске наименьшего по мощности множества Б переменных, покрывающего все элементы ^-формулы. Общий порядок действий алгоритмов следующий:

1. Для БИН и СЛО/СЛП: Упрощение путем удаления единичных дизъюнктов и чистых литералов.

2. По КНФ функции Р', полученной в результате упрощения Р, строится множество Б {Р и О).

3. Для СЛО/СЛП вычисляется число переменных в дизъюнктах, где нарушается условие для соответствующего класса. Далее приближаем формулу к классу, которому соответствует меньшее количество переменных.

4. Определяется множество М переменных, покрывающих дизъюнкты/мономы, которые не соответствуют требованиям класса Шефе-ра.

5. Множество М, фиксация переменных из которого позволяет перевести £> (Р) в класс Шефера, не обязательно является наименьшим по мощности. По этому множеству строится минимальное множество 5.

6. 5 разбивается на непересекающиеся по дизъюнкциям/полиномам подмножества ¿¿.

7. В соответствии с разбиением множества 5 на S¡ множество Б (Р) оказывается разбито на £>' (Р1), такие что каждое О1 (Р1) зависит от своего набора переменных, которые не встречаются в других множествах разбиения. Далее проверка выполнимости формулы осуществляется независимо для каждого такого подмножества £>! (Р®). Для каждого 5; осуществляется перебор значений переменных, входящих в Si.

8. При фиксированных значениях переменных из решается полиномиальная подзадача об Р-выполнимости для соответствующего класса Шефера.

9. Если для какого-то 5,- была установлена невыполнимость, то искомая формула невыполнима. Если же для каждого соответствующие формулы выполнимы, то искомая формула выполнима.

Сложность алгоритма решения задачи об ^-выполнимости булевых фор-

к

мул приближением к классам Шефера не превосходит ^

¿=1

где - длина ^-формулы.

Однако приведенные алгоритмы по сути являются решением задачи о выполнимости для ^-формулы. Они позволяют искать решение задачи для ^-выполнимости, но относительно исходной длины входных данных для задачи об ^-выполнимости они могут иметь большую сложность, чем относительно длины -Р-формулы. В связи с этим далее в главе приводится модификация данных алгоритмов, которая ориентирована на работу с исходной постановкой задачи об Р-пыполпимости. Данная модификация не всегда обеспечит более быстрое решение задачи об ^-выполнимости, однако в случае, когда длина входа задачи об ^-выполнимости существенно меньше длины ^-формулы, она позволит решать задачу эффективнее. Например, если множество Р = {Р(х, у, г)} включает одну функцию, зависящую от трех переменных и не принадлежащую классам Шефера, запись которой состоит из т дизъюнкций, при этом каждая из переменных входит в запись одинаковое количество раз. Р-формула имеет вид Р(х\, х2, хз)Р(х4, ... Р(х1, хр^,хр) - в каж-

дое из £ вхождений функции Р входит переменная х\, которая находится на первом или втором месте, остальные переменные различны для всех вхождений Тогда общая сложность исходного алгоритма приближения к классу ВИН не превосходит ро1у(тЛ). При этом, в частности, при каждом фиксированном значении Х\ метод резолюций потребует 0(тЧ3) операций. Тогда как для модифицированного алгоритма сложность можно оценить как ро1у(1)+ро1у(т)-\-1-ро1у(т). При этом метод резолюций при каждом фиксированном XI потребует 0(т3£) операций, что меньше, чем без модификации.

Далее в главе приведено описание алгоритма приближения к классу ВИН с использованием метода «разделяй и властвуй». В основе алгоритма лежит поиск множества переменных ^-формулы, после фиксации которых формула окажется разбита на непересекающиеся подмножества дизъюнкций, после чего задача решается рекурсивно для каждого из получившихся непересекающихся подмножеств. Для поиска подмножества переменных для фиксации используется модифицированный алгоритм

Штор-Вагнера22 нахождения глобального минимального разреза в графе (для этого в ходе работы алгоритма F-формуле сопоставляется неориентированный граф). Для модифицированного таким образом алгоритма приближения к классу ВИН верны следующие утверждения:

Утверждение 3.6 Пусть Т{БИН) - сложность решения задачи об F-выполнимости приближением к классу БИН, T(DC) - сложность решения той же задачи приближением к классу БИН с использованием мет,ода «разделяй и властвуй». ТогдаТ(БС) < T(BHH)+poly(\F\), где |F| - длина F-формулы.

Следствие 3.4 В случае если для всех i = 1..k |Si| < log2(poij/(|a;|)) сложность алгоритма будет полиномиальной величиной относительно длины F-формулы.

Утверждение 3.7 В лучшем случае на соответствующем шаге рекурсии сложность работы алгоритма не превышает2~%~ро1у(\Р\), где |F| - длина F-формулы.

В Главе 4 рассматриваются результаты практического применения алгоритмов, а также приводится описание криптографической системы с открытым ключом, которая может быть построена на базе задачи об ^-выполнимости.

Практические результаты работы алгоритмов проверялись на случайно генерируемых наборах функций, не содержащих единичных дизъюнкций и чистых литералов, то есть рассматривались только случаи, для которых только лишь упрощение F-формулы стандартными методами не приводило к ответу, и для нахождения решения использовались непосредственно соответствующие алгоритмы приближения к классам Ше-фера. Из полученных статистических данных о работе программ видно, что несмотря на то, что в общем случае алгоритмы приближения к классам Шефера имеют экспоненциальную сложность, степень экспоненты в

к

оценке сложности алгоритма (J2 2ls%0/?/(|F|)) растет медленнее, чем об-

i=1

щее число переменных (соответствующее сложности перебора), что делает алгоритмы эффективными. Так, для решения задачи приближением

22Stoer M., Wagner F. A Simple Min-Cut Algorithm // Journal of the ACM, Vol. 44, No. 4. - 1997, P. 585-591

к классу БИН для 100 переменных при ограничении на число функции в Р-формуле в = 10 и число дизъюнкций для записи каждой функции ктах — 5, максимальное время работы составило 273 секунды. Кроме того, приведено сравнение результатов использования алгоритма приближения к классу БИН без использования метода «разделяй и властвуй» и с его использованием, которое показывают, что использование метода «разделяй и властвуй» позволяет добиться намного более высокой скорости работы.

Далее в главе рассматривается асимметричная криптосистема с открытым ключом, основанная на алгоритме приближения к классу БИН, для которой можно было бы изучить вопрос использованися в случае распространения квантовых методов криптоанализа. Криптосистема функционирует следующим образом. Основным параметром криптографической системы с открытым ключом на основе задачи об Р-выполнимости служит количество различных переменных, задействованных в Р-формуле (п). Для формирования ключевой пары выбирается п булевых функций Р1,...,РП, удовлетворяющих условиям критерия Хаффмана, для которых задача о выполнимости решается приближением к классу БИН за полиномиальное время. Далее функции записываются в форме полиномов Жегалкина и осуществляется замена переменных в соответствии с матрицей Р = 04|Ь) {А - невырожденная п х п-матрица) размера п х (п + 1), которая представляет собой закрытый ключ. Функции РЬ...,Р„ также преобразовываются с использованием закрытого ключа, так что на выходе имеем функции зависящие от п2 переменных, которые и служат открытым ключом. Для шифрования данных отправитель подставляет биты сообщения в функции открытого ключа, при этом стойкость системы базируется на сложности нахождения всех имеющихся выполняющих наборов для задачи выполнимости, в то время как получатель сообщения, обладая закрытым ключом, имеет возможность перейти к формулировке задачи, которая решается за полиномиальное время и имеет единственный выполняющий набор (соответствующий исходному тексту).

В Заключении отражены общие выводы из проделанной работы.

Автор выражает благодарность своему научному руководителю кандидату физико-математических наук, ведущему научному сотруднику Валентину Александровичу Носову за постановку задач и постоянное внимание к работе. Также благодарю коллектив кафедры Математической теории интеллектуальных систем за внимание к работе и ценные замечания.

СПИСОК ОСНОВНЫХ РАБОТ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1. Поцелуевская Е.А. Полиномиальные случаи решения задачи об F-выполнимости булевых формул // Интеллектуальные системы. -2008. - Т. 12. - Вып. 1-4. - С. 351-362.

2. Поцелуевская Е.А. Криптосистема с открытым ключом на основе задачи об F-выполнимости булевых формул // Фундаментальная и прикладная математика. - 2009. Т. 15. - Вып. 5. - С. 199-208. Перевод: Potseluevskaya Е. Public-key cryptographic system based on generalized satisfiability problem // Journal of Mathematical Sciences -2011. - Vol. 172. -No. 5 -P. 751-758, - DOI: 10.1007/sl0958-011-0217-x.

3. Поцелуевская Е.А. Алгоритмы решения задачи об F-выполнимости приближением к классам Шефера // Интеллектуальные системы. - 2010. Т. 14. - Вып. 1-4. - С. 471-490.

4. Поцелуевская Е.А. О некоторых свойствах классов Шефера // Интеллектуальные системы. -2011. - Т. 15. -Вып. 1-4. -С. 265-280.

5. Поцелуевская Е.А. Приближение булевых функций к классам Шефера // Фундаментальная и прикладная математика. - 2010. -Т. 16. - Вып. 7. - С. 197-204.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ ; Тираж |0 0 экз. Заказ № 1§