The complexity of inversion of explicit Goldreich's function by DPLL algorithms

Функция Голдрейха отображает бинарную строку длины $n$ в бинарную строку длины $n$. Каждый бит выхода зависит от $d$ битов входа и вычисляется по фиксированному $d$-местному предикату. Каждая функция Голдрейха задается графом зависимостей $G$ и предикатом $P$. В 2000 году О. Голдрейх выдвинул гипотезу, что если граф зависимости является экспандером, а предикат случайный, то такая функция является односторонней. В этой статье мы приводим простое доказательство экспоненциальной нижней оценки на сложность обращения функции Голдрейха близорукими DPLL алгоритмами. Граф зависимости $G$ в нашей конструкции может быть основан на произвольном экспандере, в частности возможно использовать явную конструкции экспандера, в то время как все предыдущие результаты были основаны на случайном графе зависимости. Предикат $P$ может быть линейным или немного нелинейным. Наша конструкция может быть использована и для доказательства нижней оценки для “пьяных” DPLL алгоритмов. Библ. – 18 назв.