Laboratory of Mathematical Logic at PDMI

Пятница, 25 ноября, комната 106. Начало в 17:30.

Докладчик: А. Куликов.

Тема: Эффективное нахождение трудных входов в NP-языках.

Abstract

Доклад по статье Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma ``If NP-languages are hard on the worst-case then it is easy to find their hard instances''.

Будет показано, что если NP не лежит в BPP (``некоторый NP-полный язык является сложным в худшем случае''), то для любого вероятностного алгоритма существует сложное полиномиально вычислимое распределение на его входах (алгоритм часто ошибается на входах, выбранных согласно этом распределению). Это первое известное worst-case to average-case сведение для NP.

Наличие такого сведения, однако, не означает, что существует одно конкретное распределение, являющееся сложным для любого вероятностного полиномиального алгоритма (что является необходимым, хотя и не достаточным, условием существования односторонних функций и криптографии). Тем не менее, будет показано, что существует конкретное распределение примеров NP-полных задач, вычислимое за квазиполиномиальное время и являющееся сложным для всех вероятностных полиномиальных алгоритмов.

Полученные результаты базируются на следующей лемме: по данному ``эвристически эффективному'' полиномиальному алгоритму, не решающему SAT в худшем случае, можно эффективно построить три формулы, хотя бы на одной из которых алгоритм даст неправильный ответ.