Home

Пятница, 30 января, 18:00, к. 106

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

Докладчик: А. Калегин.

Тема: Повышение сложности в классе NP.

Abstract

Доклад по статье Luca Trevisan "On Uniform Amplification of Hardness in NP".

Доклад будет посвящён равномерному увеличение сложности в классе NP (uniform amplification of hardness). А именно, будет доказано следующее утверждение: если для каждого языка из NP существует вероятностный полиномиальный по времени алгоритм, успешно работающий с вероятностью $ \frac{1}{2} + \frac{1}{(\log n)^a} $ (вероятность берется по случайным битам и входам длины n), то для каждого языка из NP существует вероятностный полиномиальный по времени алгоритм, успешно работающий с вероятностью $ 1-\frac{1}{poly(n)} $.