Эта публикация цитируется в
3 статьях
The complexity of inversion of explicit Goldreich's function by DPLL algorithms
[Сложность обращения явной функции Голдрейха DPLL алгоритмами]
D. M. Itsykson,
D. O. Sokolov St. Petersburg Department of the Steklov Mathematical
Institute, St. Petersburg, Russia
Аннотация:
Функция Голдрейха отображает бинарную строку длины
$n$ в бинарную строку длины
$n$. Каждый бит выхода зависит от
$d$ битов входа и вычисляется по фиксированному
$d$-местному предикату. Каждая функция Голдрейха задается графом зависимостей
$G$ и предикатом
$P$. В 2000 году О. Голдрейх выдвинул гипотезу, что если граф зависимости является экспандером, а предикат случайный, то такая функция является односторонней. В этой статье мы приводим простое доказательство экспоненциальной нижней оценки на сложность обращения функции Голдрейха близорукими DPLL алгоритмами. Граф зависимости
$G$ в нашей конструкции может быть основан на произвольном экспандере, в частности возможно использовать явную конструкции экспандера, в то время как все предыдущие результаты были основаны на случайном графе зависимости. Предикат
$P$ может быть линейным или немного нелинейным. Наша конструкция может быть использована и для доказательства нижней оценки для “пьяных” DPLL алгоритмов. Библ. – 18 назв.
Ключевые слова:
одностронние функции, DPLL алгоритм, экспандер, нижние оценки сложности.
УДК:
510.52 Поступило: 31.07.2011
Язык публикации: английский