Laboratory of Mathematical Logic at PDMI

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

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

Тема: Полная задача в классе HeurBPP - продолжение.

Abstract

На прошлом семинаре на самом деле к содержанию доклада мы не приступили. Слайды с прошлого семинара см. на http://logic.pdmi.ras.ru/~dmitrits/talks/heur1.pdf Так что abstract старый... Класс BPP состоит из языков, для которых существует распознающий вероятностный полиномиальный алгоритм, который выдает правильный ответ с вероятностью не менее, чем 3/4. Для класса BPP неизвестно полных задач. В докладе будет рассмотрен эвристический аналог класса BPP: язык с заданным распределением на входах принадлежит классу HeurBPP, если существует алгоритм, который выдает правильный ответ с вероятностью не менее, чем 3/4 на всех входах, кроме множества вероятности eps, время работы алгоритма ограничено полиномом относительно n/eps. Будет построена полная задача в классе HeurBPP с распределениями, которые могут быть сгенерированны из равномерного с помощью полиномиальных алгоритмов.