# playlist (click the video's upper-left icon)
source: Лекториум 2013年7月24日
Подписывайтесь на канал: https://www.lektorium.tv/ZJA
Следите за новостями:
https://vk.com/openlektorium
https://www.facebook.com/openlektorium
Вероятностно проверяемые доказательства (Probabalistically Checkable Proofs или PCP) - это одно из самых ярких достижений теоретической информатики 90-х годов. PCP-теорема утверждает, что любое доказательство (в том числе математическое) можно переделать за полиномиальное время в такое, которое можно вероятностно проверить, прочитав лишь константное число битов этого доказательства, при этом алгоритм проверки доказательства использует лишь логарифмическое число случайных битов. Утверждение PCP-теоремы интересно и само по себе, но оно имеет важнейшее применение в теории приближенных алгоритмов для оптимизационных задач. Для многих оптимизационных задач с помощью PCP-теоремы было найдено точное значение параметра с, что существует c-приближенный полиномиальный алгоритм, но для всех c'>c существование c'-приближенного алгоритма влечет P=NP. В курсе планируется подробно разобраться со всей используемой техникой и полностью доказать PCP-теорему и ее усиленные варианты, используемые в приложениях.
План курса:
Доказательство PCP-теоремы, придуманное Динур.
3-х битная версия PCP-теоремы Хастада и следствия про трудность приближения.
Unique Game Conjecture - гипотеза, к которой сводятся очень многие вопросы о существовании приближенного алгоритма.
Страница курса на сайте Computer Science клуба.
1. Clicking ▼&► to (un)fold the tree menu may facilitate locating what you want to find. 2. Videos embedded here do not necessarily represent my viewpoints or preferences. 3. This is just one of my several websites. Please click the category-tags below these two lines to go to each independent website.
No comments:
Post a Comment