15.12.2015 Генерация трудных примеров для алгоритмов, рещающих задачу выполнимости (Дмитрий Соколов)

Доклад по статьям:
D. Gutfreund, R. Shaltiel, A. Ta-Shma. If NP languages are hard on the worst-case then it is easy to find their hard instances.
N. Vereschagin. Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case then it is Easy to Find Their Hard Instances".

Доказывая нижние оценки на время работы алгоритмов, мы обычно рассматриваем "худший случай". Но на практике нас часто интересует, чтобы в среднем все было хорошо. Например, мы пользуемся алгоритмом быстрой сортировки, хотя знаем, квадратичную нижнюю оценку на данный алгоритм.

Возможно ли, что если трудные примеры для конкретного алгоритма существуют ($P \neq NP$), но их "трудно" найти? В докладе мы покажем один из способов, как получать искомые трудные примеры.