Полиномиальный тезис Чёрча для рефал-5-функций, нормальных алгоритмов и их обобщений

Abstract

При разработке многократно используемых программ важно, чтобы их выполнение было достаточно быстрым. В книге Ду Д.З. и Ко К.И. сформулирован обобщенный тезис Чёрча: «Функция, вычислимая за полиномиальное время на разумной вычислительной модели, использующей разумное измерение временной сложности, вычислима на детерминированной машине Тьюринга за полиномиальное время» (то есть принадлежит классу FP). Этот расширенный тезис Чёрча более естественно называть полиномиальным тезисом Чёрча для машин Тьюринга. «Разумность» вычислительной модели разными исследователями понимается по-разному, вследствие чего в последнее время всё чаще появляются «доказательства» (содержащие ошибки) знаменитой проблемы: верно ли, что P = NP? При этом шаг различных моделей алгоритмов трактуется интуитивно. В настоящей работе доказано, что «разумность» шага вычисления рекурсивной функции может заключаться в использовании таких рефал-5-предложений из класса FP, длина записи результата выполнения которых (включая длину записи всего изменяемого стека) увеличивается не более чем на константу, единую для всех исходных данных. В этом смысле обычное определение общерекурсивной функции не является «разумной» вычислительной моделью. Достаточно сложным является подсчет числа шагов рекурсивного алгоритма. В настоящей статье доказаны необходимые и достаточные условия полиномиальности по времени функции, реализованной на языке программирования рефал-5. Этот язык является практически реализованным обобщением таких математических моделей алгоритма как нормальные алгоритмы, а также вводимые здесь алгоритмы Маркова-Поста и рекурсивные алгоритмы Маркова-Поста. Поэтому в качестве следствий основной теоремы доказаны условия полиномиальности по времени и этих математических моделей, применимых в теоретических исследованиях. Весьма актуальным является вопрос о возможности доказательства того, что программа, написанная на языке рефал-5, задает полиномиально быструю функцию, то есть функцию, принадлежащую классу FP. В статье вводится понятие дважды полиномиальных рекурсивных вызовов рефал-5-функции, обеспечивающее решение этого вопроса.