109
правок
Изменения
м
→Утверждение 1
с таймером <math>in^i</math>. Тогда среди <math>{p_i}</math> встречаются
только программы из <math>P</math>, и для каждой полиномиальной программы
<math>\tilde{p_i}</math>, работающей за полином <math>q_ig_i(n)</math>, существуетномер <math>j</math> такой, что <math>jn^j > g_i(n)</math> для всех натуральных <math>n</math>,
и <math>\tilde{p_j}</math> делает то же самое, что и <math>\tilde{p_i}</math>.
Таким образом, <math>p_j</math> распознает тот же язык, что и <math>\tilde{p_i}</math>.
