Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары






Математический кружок
12 марта 2013 г. 18:30, г. Долгопрудный, 115 КПМ МФТИ
 


PCP теорема и трудность приближенного решения задач оптимизации. Часть 1

М. Н. Вялыйab

a Московский физико-технический институт (государственный университет)
b Вычислительный центр им. А. А. Дородницына РАН, г. Москва
Материалы:
Adobe PDF 1.3 Mb

Количество просмотров:
Эта страница:410
Youtube Video:





Аннотация: Хорошо известно, что структурная теория сложности доставляет аргументы в пользу трудности многих алгоритмических задач, в том числе и комбинаторных задач оптимизации. Свидетельством трудности является NP-полнота соответствующей задачи разрешения.
Оказывается, аналогичные доводы можно привести и в пользу трудности приближенного решения таких задач. В этом случае нужно доказывать трудность задач с априорной информацией (про вход известно, что либо все условия можно удовлетворить, либо не более некоторой доли всех условий).
Доказательства трудности таких задач основаны на анализе вероятностно проверяемых доказательств (PCP). Знаменитая PCP теорема гарантирует существование NP-полной задачи указанного выше вида и играет в теории трудности приближенных алгоритмов ту же роль, что и теорема Кука-Левина в анализе трудности задач разрешения.
В серии из двух докладов будут даны более подробные объяснения роли PCP теоремы в теории сложности, а также будет рассказано о наиболее простом ее доказательстве, предложенном Ирит Динур в 2005 году.

Материалы: pcp1_Вялый.pdf (1.3 Mb)
Цикл докладов

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021