"Записки научных семинаров ПОМИ"
Том 399, стр. 88-108
Сложность обращения явной функции Голдрейха DPLL алгоритмами
Д. М. Ицыксон, Д. О. Соколов
Санкт-Петербургское отделение
Математического института им. В. А. Стеклова РАН,
Фонтанка 27, Санкт-Петербург 191023, Россия
dmitrits@pdmi.ras.ru, sokolov.dmt@gmail.com
- Аннотация: Функция Голдрейха отображает бинарную строку длины $n$ в бинарную строку
длины $n$. Каждый бит выхода зависит от $d$ битов входа и вычисляется по
фиксированному $d$-местному предикату. Каждая функция Голдрейха задается
графом зависимостей $G$ и предикатом $P$.
В 2000 году О.~Голдрейх выдвинул гипотезу, что если граф
зависимости является экспандером, а предикат случайный, то такая
функция является односторонней.
В этой статье мы приводим простое доказательство экспоненциальной нижней оценки на
сложность обращения функции Голдрейха близорукими DPLL алгоритмами.
Граф зависимости $G$ в нашей конструкции может быть основан на произвольном экспандере, в частности возможно использовать
явную конструкции экспандера, в то время как все предыдущие результаты
были основаны на случайном графе зависимости.
Предикат $P$ может быть линейным или немного нелинейным.
Наша конструкция может быть использована и для доказательства нижней оценки для ``пьяных'' DPLL алгоритмов.
Библ. -- 18 назв.
- Ключевые слова: одностронние функции, DPLL алгоритм, экспандер, нижние оценки сложности
[DPLL algorithm, expander, one-way function, lower bounds]
Полный текст(.pdf)