Автор обращает внимание на то, что язык дискретной математики "более точно подходит для описаний, которые может преобразовывать компьютер", поэтому многие задачи и теоремы, которые раньше считались экзотическими, в последние несколько десятилетий привлекают больше внимания.

Статья написана в соавторстве с А.Н. Тереховым и С.М. Селеджи. Статья содержит краткий исторический обзор на тему компьютеризации факультета и, естественно, сведения о работе отделения информатики в последние годы, об успехах наших студентов на чемпионатах мира по информатике среди команд университетов, о перспективах выпускников отделения информатики. Пока журнал готовился к печати, из Атланты пришло сообщение, что команда математико-механического факультета СПбГУ заняла 2 место в финале чемпионата мира по программированию среди университетов. Никогда еще ни одна российская команда не добивалась такого успеха!

Статья посвящена проблемам доказательства полиномиальной вычислимости функций, другими словами, доказательства принадлежности функций классу FP. Доказательства могут производиться с помощью паскалевидных функций, которые более удобны программистам, чем модели вычислений, основанные на машине Тьюринга. Будет приведена идея доказательства теоремы, что если не только число шагов вычисления паскалевидной функции, но и размер записи всех промежуточных вычислений не превосходят полинома от длины записи исходных данных, то эта функция принадлежит классу FP и обратно.

The paper is devoted to the problem of proving that some function is in FP complexity class. Such proofs may use pascal-like functions, that are more easy for programmers, than computation models based on a Turing machine. It will be presented the idea of proof of the theorem, that if both the number of steps of pascal-like function evaluation and a size of all intermediate evaluations are not greater than some polynomial of the length of initial data, then this function is in FP and vice versa.

В [3] даны определения числа шагов и длины записи промежуточных вычислений паскалевидных функций. С их помощью было получено представление класса всех функций, вычислимых на машинах Тьюринга за число шагов, ограниченное сверху полиномом от длины записи исходных данных (класса FP), с помощью дважды полиномиальных (то есть полиномиальных по числу шагов и по длине записи промежуточных вычислений) паскалевидных функций. Для удобства доказательства принадлежности паскалевидной функции классу FP здесь введено понятие паскалевидных функций над списком S паскалевидный функций. Для этих функций даны определения числа шагов и длины записи промежуточных вычислений, наконец, определены дважды полиномиальные паскалевидные функции над списком S. (для каждой функции из S число шагов и длина записи промежуточных вычислений равны единице). Функции из S соответствуют базовым подпрограммам. Доказывается теорема о совпадении класса дважды полиномиальных паскалевидных функций над S и класса FP.

[3] gives definitions of time and space comlexity of pascal-like functions. Using this definitions it was obtained the representation of the class of all functions computable by Turing machine in time upper bounded by the polynomial of the length of the initial data (FP class) by means of double polynomial (i.e. polynomial in time and space) pascal-like functions. For the convinience of proving that a pascal-like function is in FP, we introduce the notion of the pascal-like functions over a list S of pascal-like functions. For such functions we give definitions of time and space complexities, finally, we define double polynomial pascal-like functions over a list S. (for every function in S, time and space complexity are equal to one). Functions from S correspond to basic subroutines. The theorem about the equality of the class of double polynomial pascal-like functions over S and the FP class is proved.

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

It is important for multiple-used programs that their run be sufficiently quick. Du D.Z. and Ko K.I. have formulated a extended Church thesis: В«A function computable in polynomial time in any reasonable computational model using a reasonable time complexity measure is computable by a deterministic Nuring machine in polynomial timeВ» (i.e. it belongs to the class FP. It is more natural to call this extended Church thesis as a polynomial Church thesis for Turing machine. Different researchers differently understand the term reasonable in consequence of which at the last time many В«proofsВ» (containing mistakes) of the famous problem whether P = FP appear. In such В«proofsВ» a step of different algorithm models treats intuitively. In the present work it is proved that reasonability of a recursive function step may be consisted in the use of such refal-5-sentenses from FP, for which the length of result notation (including the lenth of all stack) increases not more than by additive constant unique for all arguments. In such a sence a usual definition of a recursive function is not a reasonable calculation model. The count of recursive algorithm steps is rather difficult. Nesessary and sufficient conditions of time polynomiality of a function, realized by means of programming language refal-5, are proved in the present paper. This language is a practicaly realized generalization of such mathematical models of algorithm notion as normal algoritm and here introduced Markov-Post algorithm and recursive Markov-Post algorithm. That is why conditions of time polynomiality of these mathematical models (used in theoretical reseaches) are proved as corollaries of the main theorem. The question whether it is possible to prove that a refal-5 program realizes a polynomiall time function (i.e. function belonging to FP) is very actual. A notion of a double polynomial recursive refal-5 function call, which provides the solution of this question, is introduced in the paper.

Статья содержит два основных раздела. Первый из них (п. 2) отвечает на вопрос о том, как можно расширить понятие нормального алгоритма Маркова, включив, в частности, полиномиальные функции над длинами используемых слов и сохранив при этом объём вычислений в пределах полиномиального числа шагов. Ответом на этот вопрос является последовательность математических понятий алгоритма со всё более мощными вычислительными средствами, но тем не менее совпадающими с классом алгоритмов, полиномиальных по времени (с классом FP) при реализации их на машинах Тьюринга. Второй из основных разделов (п.3) отвечает на вопрос, каким образом можно, всё более расширяя понятие нормального алгоритма Маркова, вложить их в каждый из подклассов FP, алгоритмы которого используют промежуточную память, длина которой ограничена полиномом k-ой степени. Результаты второго раздела могут рассматриваться также и как подтверждение естественной формулировки тезиса Чёрча для последнего из классов алгоритмов, использованных в формулировках теорем этого раздела.

This paper contains two main sections. The first one (section 2) answers the question: В«How to extend the notion of Markov algorithm by inclusion of a polnomial function of a word length and to conserve computation inside polynomial number of steps?В». A sequence of mathematical notions of algorithm with more and more powerfull computational tools is presented. It is proved that every of them coinsides with the class of polynomial in time algorithms (class FP). The second one (section 3) answers the question: В«How to extend the notion of Markov algorithm in order to include it into subclass of FP containing only algorithms using intermediate memory with the length not more than a polynomial of k-th degree?В». The results of this section may be also regarded as a confirmation of the natural formulation of Church thesis for the last two classes of algoritmms used in the formulations of the theorems of this section.

Автор знакомит читателя с новой логической операцией - юнкцией, которая значительно расширяет традиционные логические операции. На ряде примеров демонстрируются условия, которые с введением этой операции допускают гораздо более доступную реализацию, чем в привычной математической логике.