Статья посвящена проблемам доказательства полиномиальной вычислимости функций, другими словами, доказательства принадлежности функций классу 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.