Изменения
→Доказательство:
Рассмотрим язык <tex> L = \{\langle a,y \rangle ~|~ \exists x, a </tex> - префикс <tex> x, f(x) = y \} </tex>.
<tex> L \in NP </tex>и, так как по условию <tex> NP = P </tex>, то <tex> L \in P </tex>. Заметим, что подбирая по одному биту, однако <tex> x </tex> легко восстанавливается за полином, а значит вероятность <tex> P_{A} </tex> из определения односторонних функций не является пренебрежимо малой и, следовательно, односторонних функций существовать не может.
== Определение ==
