• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Мероприятия

Семинар лаборатории теоретической информатики: Вадим Гринберг (TTIC) "Полуслучайная задача о скрытой клике"

Мероприятие завершено

11 сентября на семинаре лаборатории теоретической информатики состоится доклад Вадима Гринберга"(TTIC) "Полуслучайная задача о скрытой клике".

Задача о поиске клики максимального размера в графе является одной из ключевых в современной теоретической информатике. Она NP-трудна, более того, не известно даже хороших аппроксимационных алгоритмов (а приблизить лучше O(n^delta) для некоторого delta вообще невозможно, если P != NP). Эти обстоятельства намекают на то, что в общей постановке задача является неразрешимой за полиномиальное время. Естественным шагом будет перейти от произвольных графов к случайным, и придумывать алгоритмы, решающие задачу с большой вероятностью по распределению на графах. Одними из наиболее популярных являются распределения на графах со скрытой кликой G(n, p, k). Устроены они так: сначала берётся случайный граф на n вершинах и вероятностью появления ребра p = p(n) — G(n, p). Затем выбирается случайное подмножество его вершин размера k = k(n), из которого делается клика (проводятся недостающие рёбра). Возникает вопрос: при каких значениях параметров p и k существует полиномиальный алгоритм, с вероятностью стремящейся к 1 находящий максимальную клику в G(n, p, k)? В 1998 году был представлен полиномиальный алгоритм поиска максимальной клики в G(n, p, k) для любого константного p и k >= Omega(sqrt(np/q)), где q = 1 - p. После этого было создано ещё несколько лучших полиномиальных алгоритмов, обобщающих результат для практически всех возможных функций p = p(n). Однако, неизвестно, существует ли полиномиальный алгоритм, находящий максимальную клику в G(n, p, k) при k = o(sqrt(np/q)), даже в случае константного p. Есть множество результатов, показывающих неработоспособность тех или иных подходов при данных p и k (например, спектральных методов или метода сумм квадратов). Для конкретных p и k >= Omega(sqrt(np/q)) рассмотрим граф со скрытой кликой размера k. Если исходных граф и скрытую клику брать не случайными, а произвольными, задача очевидно становится NP-трудной, но если граф и скрытая клика оба случайные, задача решается за полином (почти для всех p). Насколько важную роль играет случайность? Попытки ответить на этот вопрос приводят к полуслучайной постановке задачи о скрытой клике. Рассмотрим распределение AG(n, p, k). Как и раньше, сначала генерируется случайный граф G(n, p). Затем некий всесильный противник (adversary) выбирает произвольное подмножество из k вершин на своё усмотрение, и делает из него клику. Можно ли гарантировать существование полиномиального алгоритма поиска максимальной клики в AG(n, p, k), вне зависимости от действий противника? В докладе речь пойдёт о результатах, полученных в ходе совместной работы с Dr. Uriel Feige из Weizmann Institute of Science. Будет доказано, что для любых функций p = p(n), НЕ стремящихся к 1 с ростом n, существует полиномиальный алгоритм, с вероятностью стремящейся к 1 находящий максимальную клику в AG(n, p, k) при k >= Omega(sqrt(np/q)), вне зависимости от действий противника. В случае же, когда p = p(n) стремится к 1, поиск максимальной клики в AG(n, p, k) является трудной задачей. Мы докажем, что если существует алгоритм, с константной вероятностью находящий максимальную клику в AG(n, p, k) с p = 1 - 1/poly(n) при k >= Omega(sqrt(np/q)), то NP = RP.


Семинар пройдет с 18:10 до 19:30 в аудитории D109, Покровский бульвар, 11.
Заказ пропуска: dchernyshova@hse.ru