Уважаемый Кирилл Владимирович

Краткое сообщение для Института высоких технологий

Российской академии естественных наук

Мы занимаемся исследованиями в области решения NP-полных (труднорешаемых) задач и проблем Выполнимости (SAT-проблем). М.И.Тельпиз разрабатывает эту тему свыше 20 лет. Этими проблемами занимаются научные коллективы (НК) в США, Европе, Японии, а в России, насколько нам известно, – ничтожно мало.

Но наш подход совершенно отличается от подхода других НК. Вкратце (и грубо) его можно изложить как теоретическая разработка и использование принципа позиционности при работе с математическими функциями, а не только с числами. Пример работы с числами, в отличие от функций, общеизвестен: древние математики испытывали затруднения при умножении XXV на XLV (в римской системе счисления), не зная принципа позиционности представления чисел. Сейчас же ребенок еще в начальной школе умеет умножать 25 х 45 = 1125 (столбиком) без особого труда.

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

Каких результатов мы добились?

Разработана методология построения алгоритмов для решения определенных классов труднорешаемых задач. Мировые достижения при решении подобного класса задач обеспечивают работу с 500 переменных (на станциях SUN). Этот результат по классической схеме можно улучшить только за счет внедрения нового прогрессивного hardware. Мы на IBM PC - 100 Mhz Pentium processor достигли уже результатов с 200 переменных. Для работы с большим числом переменных нам предстоит запрограммировать некоторые алгоритмы. Главное, что мы знаем, как это делать. И полагаем, что работа даже с 1500 переменных это далеко не предел.

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

N	Переменных	Строк	h.min.sec
1	30	129	0.0.11
2	40	172	0.0.21
3	50	215	0.0.25
4	115	495	0.26.15
5	120	516	0.10.36
6	125	538	0.30.54
7	130	559	1.00.02
8	150	645	1.40.33

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

Каким ‘‘know how’’ мы обладаем?

Не вдаваясь в подробности, в отличие от других коллективов, которые строят решения, мы преобразуем текст КНФ, приводя его к некоей суперприведенной форме (в случае противоречивости КНФ происходит полное вырождение текста). Из КНФ, приведенной к такой форме, решения извлекаются моментально, так как суперприведение – это такое преобразование КНФ, которое превращает труднорешаемую задачу в эквивалентную (то есть сохраняющую выполняющие наборы) ей легкорешаемую задачу. Суперприведение позволяет не только отвечать на вопросы ‘‘Да?’’ или ‘‘Нет?’’, но и при проектировании аппаратуры определять минимальный ее объем. Исходный текст SAT после его суперприведения может рассматриваться как новый способ решения задачи SAT с полным предъявлением, чего нельзя добиться, если непосредственно строить выполняющие наборы, так как их может быть очень много.

Ниже представлен пример суперприведения. Дана исходная таблица из 24 строк, где переменные a и ā связаны дизъюнктивно, а строки конъюнктивно:

1) 2ā 4ā 5a 9) 0a 4a 5ā 17) 1ā 2a 5ā2) 0ā 1ā 5a 10) 1ā 2ā 4ā 18) 0ā 1a 3ā3) 0a 2a 4a 11) 0a 2a 4ā 19) 2a 3ā 5ā

4) 1ā 2ā 3ā 12) 1a 2a 3ā 20) 1ā 4a 5a

5) 0a 4ā 5ā 13) 2ā 3ā 5a 21) 1ā 3ā 5ā

6) 1ā 3ā 4ā 14) 1ā 3a 5a 22) 1a 3ā 4a

7) 0a 2ā 4ā 15) 0ā 1ā 2ā 23) 0ā 3ā 4a

8) 1a 2a 3a 16) 0a 2ā 5a 24) 0a 3a 5ā

В результате суперприведения эта таблица преобразована в эквивалентную ей таблицу (из 5 строк), дающую те же выполняющие наборы:

1) 0a

2) 1ā

3) 2a

4) 3ā

5) 4ā 5a

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

N	Переменных до суперприведения	Переменных до суперприведения	Строк до суперприведения	Строк после суперприведения
1	30	30	129	57
2	30	29	345	29
3	30	29	444	41
4	30	30	203	72

Где можно использовать результаты наших исследований?

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

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

В чем мы заинтересованы?

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