Существование OWF против $\mathbf{EXP} \neq \mathbf{BPP}$

$\mathsf{EXP}\neq \mathsf{BPP}$ является типичным предположением, используемым в литературе по дерандомизации. Слова для поиска: «Нисан-Виджерсон» и «Импальяццо-Виджерсон». Например, реферат Импальяццо-Виджерсон читает:

Докажем, что если $\mathsf{BPP}\neq \mathsf{EXP}$, то каждая задача в $\mathsf{BPP}$ может быть решена детерминистически за субэкспоненциальное время почти на каждом входе (на каждом выборочном ансамбле для бесконечного множества входные размеры). Это первый результат дерандомизации для $\mathsf{BPP}$ на основе однородных, не криптографических предположений о стойкости. Это подразумевает следующий разрыв в средней сложности задач в $\mathsf{BPP}$ : либо эти сложности всегда субэкспоненциальны, либо они содержат сколь угодно большие экспоненциальные функции.

В целом, при изучении новой области докторская диссертация может быть немного легче читать, чем статьи, поэтому, если вам интересно, подробнее Диссертация Марко Кармосино может быть полезно.