На базе позиционной нотации доказано, что классы P и NP совпадают, создан программный продукт (ПП) «Палитра», который позволяет практически решать задачи из класса NP, но с трудностями, присущими уже классу P. А класс NP охватывает очень большой круг задач дискретной математики и информатики: от задач, связанных с проектированием электронных устройств, их оптимизации и верификации и до игровых задач; задачи логики, логического вывода, графов, математического программирования, алгебры, теории чисел, кодирования и т.д.
Задача из вышеперечисленных областей вне зависимости от своего происхождения (и области) для решения с помощью ПП должна быть представлена таблично в виде КНФ(конъюнктивной нормальной формы). Сказанное означает, что переменные X_1, X_2, X_3, … , X_n двоичные. Из k литералов (где k — целое положительное переменное, заключённое между 1 и n ) этих переменных (литерал — это сама переменная или её отрицание) строится дизъюнкт. Один дизъюнкт — это одна строка таблицы. Таких дизъюнктов строится m штук (значит. в таблице имеется m строк). Подразумевается, что все дизъюнкты соединены конъюнктивно.
Так сформулированная задача носит название ВЫПОЛНИМОСТЬ (ВЫП).
Если имеется набор для переменных, который при подстановке в эту табличную форму даёт 1, то он называется выполняющим, иначе задача ВЫП противоречива.
Известно, что задача ВЫП является NP-полной (для проверки выполнимости может потребоваться перебрать 2 в степени n наборов и проверить каждый на заданной таблице).
ПП позволяет решать такую задачу за полиномиальное время как задачу ВЫП, т.е. распознавать её противоречивость или выдавать выполняющий набор в случае его наличия.
Однако, с ростом размерности задачи даже наш полиномиальный алгоритм требует достаточно много времени. И здесь найден великолепный выход из такой коллизии. Это —суперприведение.
ПП выполняет суперприведение, т.е. такое эквивалентное преобразование таблицы, при котором, если задача ВЫП противоречива, то её текст вырождается (грубо — текст превращается в одну пустую строку), а если выполнима, то выполняющий набор извлекается за линейное время от размерности таблицы.
Значит, ПП представляет новую технологию обработки текстов задач, суть которой — оптимальная структуризация их содержания, т.е. удаление из этих текстов то, что не является носителем фундаментальной информации.
Из сказанного следует, что ПП должен использоваться уже на этапе постановки задачи ВЫП для выполнения суперприведения. При таком подходе не будем получать труднорешаемые задачи. Иносказательно говоря, труднорешаемые задачи — это результат неразумной постановки или результат неуправляемого усложнения.
Разумная деятельность требует такой подход.
Всякое сложное устройство состоит из частей ( агрегатов, блоков, модулей, … ) и для этих частей нужно ставить и суперприводить её логическую схему, а затем из суперприведённыхчастей получать объединённый блок, над которым и выполнять окончательное суперприведение.
Вот простой пример. Допустим спроектировано электронное устройство, состоящее из трех блоков, каждый из которых содержит 50 элементов и соединен с последующим посредством трех общих элементов. Представим данное устройство в логическом виде в форме задачи ВЫП.
Задача ВЫП состоит из следующих трёх блоков (КНФ) с переменными: I блок от 0 до 49; II блок от 47 до 96; III блок от 94 до 143 (т.е. перекрытие учитывается). В первом и третьем блоках по 215 строк, во втором 214 строк. Общая задача, которая получается, имеет 144 переменных и 644 строк. Суперприведение общей задачи (144 переменных / 644 строки) выполняется за 6 мин 45 секунд (Pentium-866). Однако, суперприведение каждого отдельного I, II и III блоков соответственно составляют: 5, 6 и 3 сек. Суперприведение итоговой КНФ, состоящей из трех уже суперприведенных блоков, составляет 22 сек. Всего затрачено время на процедуру приведения четырех КНФ (трех исходных и одной общей) 36 сек и итоговая суперприведённая КНФ имеет 144 переменных и 281 строку (сравните с исходной: 144 переменных и 644 строки).
Полный текст описанного примера находится здесь.
Каков результат применения суперприведения? 1) Сокращен размер исходной КНФ более, чем в 2 раза, а значит и размер самого электронного устройства. При этом выполняющие наборы не изменились, т.е. не изменился проектный замысел устройства. 2) В результате выполненной реструктуризации выполняющие наборы будут срабатывать по мере поступления запроса на них, т.е. полностью исключается время обработки холостых или подготовительных вычислений, какие имели бы место в исходном варианте. А это уже даст многократный прирост скорости работы по сравнению с исходным вариантом.
Суперприведение, как инструмент позиционной алгебры логики, охватывает большое число NP—полных задач, а поэтому можно его применять:
- при проектировании чипов (СБИС) для электронной промышленности [1], [2];
- при осуществлении логического анализа в самых разных сферах [3], [4];
- для проектирования эффективных компиляторов различных языков программирования и в первую очередь для языков логического программирования типа Пролог [5];
- для анализа последовательностей ДНК [6] и во многих других случаях, начиная от теории переключательных схем и кончая теорией графов. Даже перечень NP-полных задач трудно осуществим, поскольку он составляет тысячи наименований.
Прорыв, обусловленный суперприведением, открывает труднообозримые возможности. В самом деле, как уже говорилось в п. 3, названия «суперприведенная» и «сверхлегкая» задача могут рассматриваться как синонимы и, таким образом, задача, считавшаяся труднорешаемой, алгоритмом суперприведения превращается в сверхлегкую задачу. Такое преобразование задачи может рассматриваться как процесс ее структуризации. Задача была (или казалась) труднорешаемой, пока она не была структуризирована. Значит, процесс преобразования, в результате которого некоторые операторы были исключены, а другие заменены вновь образованными из тех, что входили в текст задачи, может рассматриваться как процесс структуризации.
Такой процесс структуризации сродни процессу обучения, где по-видимому происходят аналогичные явления. Поэтому к суперприведению применяются приемы, аналогичные приемам обучения. Имеется ввиду, что для суперприведения всей задачи вначале выполняется ее сегментация. Затем применяется суперприведение каждого сегмента. Потом применяется суперприведение всей задачи, где уже каждый сегмент суперприведен.
Сама задача сегментации представляет определенный интерес. Но имеются и естественные процессы сегментации. Они возникают в процессе поблочного логического описания проектируемого устройства. Применение программ суперприведения позволяет на этапе проектирования системами CAD (computer-aided design) получать лишь задачи сверхлегкорешаемые.
Теперь, не умаляя интереса к квантовым компьютерам и квантовым вычислениям, следует обратить внимание на возможности разработки принципиально новых компьютеров, для которых задачи распознавания являются главными и не возможны вирусные беды. Но дальнейшее описание возможностей без предъявления конкретики будут напоминать фантастику, а это здесь ни к чему.
Области применения суперприведения
Ссылки
[1]. Лебедев А. Современные методы цифровой подписи. Компьютерра № 13 [342], 200, стр. 20 — 23.
[2]. Киносита К., Асада К., Карацу О. Логическое проектирование СБИС: Пер. с япон. — М.: Мир, 1988. — 309 с.
[3]. Кун С. Матричные процессоры на СБИС: Пер. с англ. — М.: Мир, 1991. — 672 с.
[4]. Логическое программирование: Пер. с англ. и фр. — М.: Мир, 1988. — 368 с.
[5]. Лорьер Ж.-Л. Системы искусственного интеллекта: Пер. с фр. — М.: Мир, 1991. — 568 с.
[6]. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог: Пер. с англ. — М.: Мир, 1990. — 235 с.