Иерархии по времени с неравномерной подсказкой для криптографического обращения функций

Доказана иерархия по времени для обращения функций, вычислимых за полиномиальное время с небольшой подсказкой, зависящей от длины входа. В частности, доказано, что из существования сильно односторонней функции следует, что для всякого $k$ и всякого полинома $p$ существует функция $f$, вычислимая за линейное время с одним битом подсказки, такая, что существует вероятностный полиномиальный противник, обращающий $f$ с вероятностью $\ge1/p(n)$ для бесконечно многих длин входов, в то время, как всякий вероятностный противник, работающий время $O(n^k)$ с логарифмическим количеством битов подсказки, обращает $f$ с вероятностью, меньшей $1/p(n)$, для почти всех длин входов.
Также доказана аналогичная теорема для сложности в наихудшем случае, т.е., если $\mathbf P\neq\mathbf{NP}$, то для всяких $l>k\ge1$
$$ (\mathbf{DTime}[n^k]\cap\mathbf{NTime}[n])/1\subsetneq(\mathbf{DTime}[n^l]\cap\mathbf{NTime}[n])/1. $$
Библ. – 16 назв.