Программный продукт на принципах позиционной алгебры логики
На базе позиционной нотации создан программный продукт «Палитра» (ПП), который позволяет эффективно решать задачи из класса NP, но с трудностями, присущими уже классу P. А класс NP охватывает очень большой круг задач дискретной математики и информатики: от задач, связанных с проектированием электронных устройств, их оптимизации и верификации и до игровых задач; задачи логики, логического вывода, графов, математического программирования, алгебры, теории чисел, кодирования и т.д.
Задача из вышеперечисленных областей вне зависимости от своего происхождения (и области) для решения с помощью ПП должна быть представлена таблично в виде КНФ (конъюнктивной нормальной формы). Сказанное означает, что переменные X_1, X_2, X_3, … , X_n двоичные. Из k литералов (где k — целое положительное переменное, заключённое между 1 и n ) этих переменных (литерал — это сама переменная или её отрицание) строится дизъюнкт. Один дизъюнкт — это одна строка таблицы. Таких дизъюнктов строится m штук (значит. в таблице имеется m строк). Подразумевается, что все дизъюнкты соединены конъюнктивно.
Так сформулированная задача носит название ВЫПОЛНИМОСТЬ (ВЫП).
Если имеется набор для переменных, который при подстановке в эту табличную форму даёт 1, то он называется выполняющим, иначе задача ВЫП противоречива.
Известно, что задача ВЫП является NP-полной (для проверки выполнимости может потребоваться перебрать 2 в степени n наборов и проверить каждый на заданной таблице).
ПП позволяет решать такую задачу за полиномиальное время как задачу ВЫП, т.е. распознавать её противоречивость или выдавать выполняющий набор в случае его наличия.
Однако, с ростом размерности задачи даже наш полиномиальный алгоритм требует достаточно много времени. И здесь найден великолепный выход из такой коллизии. Это — суперприведение.
ПП выполняет суперприведение, т.е. такое эквивалентное преобразование таблицы, при котором, если задача ВЫП противоречива, то её текст вырождается (грубо — текст превращается в одну пустую строку), а если выполнима, то выполняющий набор извлекается за линейное время от размерности таблицы.
Значит, ПП представляет новую технологию обработки текстов задач, суть которой — оптимальная структуризация их содержания, т.е. удаление из этих текстов то, что не является носителем фундаментальной информации.
Из сказанного следует, что ПП должен использоваться уже на этапе постановки задачи ВЫП для выполнения суперприведения. При таком подходе не будем получать труднорешаемые задачи. Иносказательно говоря, труднорешаемые задачи — это результат неразумной постановки или результат неуправляемого усложнения.
Разумная деятельность требует такой подход.
Всякое сложное устройство состоит из частей ( агрегатов, блоков, модулей, … ) и для этих частей нужно ставить и суперприводить её логическую схему, а затем из суперприведённых частей получать объединённый блок, над которым и выполнять окончательное суперприведение.
Вот простой пример. Допустим спроектировано электронное устройство, состоящее из трех блоков, каждый из которых содержит 5000 элементов и соединен с последующим посредством трех общих элементов. Представим данное устройство в логическом виде в форме задачи ВЫП.
Задача ВЫП состоит из следующих трёх блоков (КНФ) с переменными: I блок от 0 до 4900; II блок от 4700 до 9600; III блок от 9400 до 14300 (т.е. перекрытие учитывается). В первом и третьем блоках по 21500 строк, во втором 21400 строк. Общая задача, которая получается, имеет 14301 переменных и 64400 строк.
Каков результат применения суперприведения?
1) Сокращен размер исходной КНФ более, чем в 2 раза, а значит и размер самого электронного устройства. При этом выполняющие наборы не изменились, т.е. не изменился проектный замысел устройства.
2) В результате выполненной реструктуризации выполняющие наборы будут срабатывать по мере поступления запроса на них, т.е. полностью исключается время обработки холостых или подготовительных вычислений, какие имели бы место в исходном варианте. А это уже даст многократный прирост скорости работы по сравнению с исходным вариантом.
В данном изложении не рассматриваются конкретные алгоритмы работы ПП «Палитра».