Идея продолжения принципа позиционности возникла давно: в первой половине 1978 года. Первые программы по распознаванию выполнимости были написаны И.В.Петровым по алгоритмам, использовавшими идею позиционности, и относятся к середине 1987 г. Исследования, проводившиеся в то время, частично отражены в Пр-1612 Ордена Ленина Института космических исследований АН СССР: О.М.Москаленко, И.В.Петров, М.И.Тельпиз, В.И.Шевченко. Разработка на базе позиционной алгебры логики алгоритмов задачи о выполнимости и их статистическое исследование. - 1990. - 36 стр.
Большей частью теоретическое, но частично отраженный в программный продукт исследование, направленное на выяснение перспективных возможных путей развития идеи позиционности, стало складываться в достаточно стройную теорию к 1995 году, когда стал накапливаться материал, составивший основу книги [ПП]. И тогда была сформулирована основная цель книги, заключающаяся в разработке системы счисления и исчисления функций, базирующейся на позиционном принципе.
Для начала были выбраны функции алгебры логики и для их представления разработана такая система продукций (образующих правил), которая позволяет достаточно просто (с линейной сложностью) записывать классические формулы логики высказываний через позиционные операторы, построенные из продукций. Для выполнения преобразований над позиционными операторами введена система копродукций (это название принято для композиции продукций) и система комбинаторов (комбинаций продукций).
Копродукции и комбинаторы являются расширением системы продукций и позволяют достаточно просто выполнять преобразования над позиционными операторами.
Особо большое внимание уделено преобразованиям, в особенности эквивалентным преобразованиям (эквивалентными мы называем преобразования над формулами логики высказываний, которые не изменяют истинности таблиц этих формул).
Разработка расширенной системы продукций, позволяющей не только записывать операторы, но и эффективно выполнять эквивалентные преобразования над ними, составляет одно из направлений развития позиционности. Другое связано с разработкой такой позиционной нотации, которую можно рассматривать как предельное расширение или как полная позиционность для представления логических функций. Оба этих направления образуют целостную систему, которая составляет основное содержание книги и является тем искомым открытием, о котором идет речь в приведенной в п.2 цитате из [15].
Основанием для такого утверждения может служить содержащееся в книге [ПП] конструктивное доказательство того, что NP-полные задачи решаются полиномиальным алгоритмом. Такой конструктивный алгоритм приведен для задачи ВЫП (выполнимости). Как известно (см. [13] или [15]) по теореме Кука задача ВЫП является NP-полной. Еще о теореме NP = P см. п. 4.
В книге [ПП] содержится и еще более интересный алгоритм. Он с полиномиальной временной сложностью выполняет суперприведение над задачей ВЫП (суперприведение задачи - это такое ее эквивалентное преобразование, в результате которого текст задачи вырождается, если она противоречива, или становится таким, что выполняющий набор строится с линейной временной сложностью).
Когда мы говорим о задаче ВЫП, что она суперприведена,
то следует под этим понимать, что задача стала сверхлегкой.
Еще о суперприведении см. п.
5.
Оценка последствий такого рода результатов и тех, которые могут появиться на базе уже разработанной теории, в полной мере в настоящее время вряд ли возможна. Можно лишь сказать, что для осуществления многих грандиозных проектов снято главное препятствие. Например, японский проект реализуем в полной мере и даже реализуемы более смелые проекты, которые могут ожидаться.
Одно бесспорно. Тематика научных исследований в информатике должна резко измениться. Должна измениться концепция, лежащая в основе проектирования как элементной базы компьютеров, так и самих компьютеров.
Должна измениться концепция языков программирования в том плане, что такие языки станут языками компьютеров и будут отчуждены от человека. Они в свой состав, я надеюсь, будут включать как один из важных элементов: позиционный язык операторов, излагаемый в книге.
И, наконец, самое главное. Эта книга, содержащая позиционный язык счисления и исчисления операторов и позволяющая решать указанные выше задачи, не является последним словом в развитии позиционности, а скорее это лишь начало. А для того, чтобы это было действительно началом, надо полученные результаты усвоить и распространить, а книга должна этому способствовать.
Книга находится в стадии завершения (такое завершение должно было состояться уже больше, чем полгода назад), но поскольку некоторые идеи и результаты остаются ею не охваченными, а объем растет, то решено их изложение перенести во второй том. Первый том завершен в конце 2000-го года.