Laboratory of Mathematical Logic at PDMI

Пятница, 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)}$.