Laboratory of Mathematical Logic at PDMI

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

Докладчик: Д. Ицыксон.

Тема: Полная задача в классе HeurBPP.

Abstract

Класс BPP состоит из языков, для которых существует распознающий вероятностный полиномиальный алгоритм, который выдает правильный ответ с вероятностью не менее, чем 3/4. Для класса BPP неизвестно полных задач. В докладе будет рассмотрен эвристический аналог класса BPP: язык с заданным распределением на входах принадлежит классу HeurBPP, если существует алгоритм, который выдает правильный ответ с вероятностью не менее, чем 3/4 на всех входах, кроме множества вероятности eps, время работы алгоритма ограничено полиномом относительно n/eps. Будет построена полная задача в классе HeurBPP с распределениями, которые могут быть сгенерированны из равномерного с помощью полиномиальных алгоритмов.