...М. Н. Вялый1
Работа
выполнена при поддержке фонда РФФИ (проект No 99-01-00122).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...
тему2
Она написана по материалам первой части
книги [4] и существенно опирается на
статью [7], помещенную в этом выпуске
"Математического Просвещения".
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...недетерминированными3
Мы не объясняем,
что это такое; нужный
нам класс
можно определить, не прибегая к недетерминированным
вычислениям.
машинами Тьюринга
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... сводится4
Ниже будут использоваться аналогичные
понятия полноты для других сложностных классов.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
... чисел5
Автор
благодарен А. Китаеву, обратившему его внимание на эту, известную
специалистам по теории сложности, интерпретацию
теоремы 7.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
