Две вещи:
Да, $x_1$ это первый бит. Идея в том, что если $x_1 = 0$ (что происходит с вероятностью 1/2), несложно найти прообраз $г(х) = 0$ --- любая строка $х'$ с $х'_1 = 0$ будет достаточно. Это показывает, что $г$ не может быть $\альфа$-OWF для любого $\альфа <1/2$. Чтобы показать, что это $\альфа$-OWF для $\альфа\leq 2/3$, вам нужно будет сократить до сильной безопасности OWF $f$, что я оставлю вам сделать.
Выбор $2/3$ это просто социальное соглашение для «подходящей константы». Есть много классы сложности $\mathcal{C}$ которые зависят от некоторого параметра $\альфа$ (которое я буду обозначать $\mathcal{C}(\alpha)$), где вы можете показать некоторый результат формы
Для любой $\альфа$ ограниченный * от $1/2$ и $1$, классы сложности $\mathcal{C}(\alpha)$ эквивалентны.
Здесь «отскочил» означает, что $\frac{1}{2}+\frac{1}{n^c} \leq \alpha \leq 1 - \frac{1}{n^d}$ для констант $с, д$ --- в частности, $\альфа$ не может быть пренебрежимо близко (в зависимости от размера входных данных) ни к 1/2, ни к 1. Для таких классов социальное соглашение выбирать $\mathcal{C}(2/3)$ поскольку «стандартный» пример для связи вещей является обычным явлением.
Есть много примеров вышеупомянутого феномена, например большинство рандомизированных классов сложности, но, возможно, $BPP$ в частности, это самый известный пример.
Важность $\альфа$ быть ограниченным от 1/2 и 1 можно увидеть по разнице между классами $BPP$ (который имеет это ограничение), и класс $ПП$ (которого нет и есть много более могущественный).
Во всяком случае, этот раздел связанных заметок, по сути, показывает, что односторонние функции представляют собой класс, аналогичный таким вещам, как $BPP$ (по их зависимости от параметра $\альфа$).
