Оптимальные алгоритмы для $\mathbf{co}\mathscr{NP}$-множеств и проблема $\mathscr{EXP}\stackrel{?}{=}\mathscr{NEXP}$

В 1987 г. чешскими математиками Пудлаком и Крайчеком получен результат: в предположении $\mathscr{EXP}=\mathscr{NEXP}$ справедливо некоторое утверждение о существовании оптимальных алгоритмов для $\mathrm{co}\mathscr{NP}$-множеств. В статье показано, что первое утверждение является более сильным, чем второе: построен оракул $A$, для которого $\mathscr{NEXP^A}\ne\mathscr{EXP^A}$, но тем не менее справедливо релятивизованное к $A$ утверждение, согласно которому для любого $\mathscr{NP}$-множества $X$ существует распознающая $X$ детерминированная машина Тьюринга $M$ такая, что для любой другой детерминированной машины $M'$, распознающей $X$, существует такой полином $p$, что $\forall\,\omega t_M(\omega)\leqslant p(|\omega|,t_{M'}(\omega))$. Рассмотрен также недетерминированный случай.
Библиогр. 4 назв.