На базе позиционной нотации доказано, что классы 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) В результате выполненной реструктуризации выполняющие наборы будут срабатывать по мере поступления запроса на них, т.е. полностью исключается время обработки холостых или подготовительных вычислений, какие имели бы место в исходном варианте. А это уже даст многократный прирост скорости работы по сравнению с исходным вариантом.
В завершении отметим, что описанный подход, полностью оформившийся к концу второго тысячелетия, не имеет аналога в мировой теории и практике. Для такого вывода имеются все основания: до сих пор различные исследователи, занимающиеся задачей ВЫП, публикуют свои примеры так называемых критериев (benchmarks), в которых имеются тысячи переменных и десятки тысяч дизъюнкций или даже десятки тысяч переменных и сотни тысяч дизъюнкций, для желающих попробовать свои силы в распознавании выполнимости. И здесь подходы за последние двадцать лет существенно не изменились по сравнению с тем, что имелось на старте японского проекта ЭВМ пятого поколения (см. [8], [9], [15]). Теперь можно питать надежды, что в третьем тысячелетии проблематика существенно изменится.