Home

Семинар 19 декабря 2008 года

Пятница, 19 декабря, комната 106. Начало в 17:55.

Докладчик: И. Монахов.

Тема: Простое вероятностное сведение NP к ParityP.

Abstract

Доказательство знаменитой теоремы Тода о том, что полиномиальная иерархия содержится в $ P^{PP} $, основано на лемме Вэлианта-Вазирани: существует вероятностное сведение $ NP $ к $ UP $. В доказательстве этой леммы сначала предъявляется некоторое вероятностное сведение с вероятностью успеха $ 1/poly(n) $, а потом это сведение улучшается стандартным способом при помощи комбинирования полиномиального числа случайных величин. В докладе будет рассказано об алгебраическом сведении, которое сразу обеспечивает константную вероятность успеха и не нуждается в улучшении. Это сведение очень простое, и его анализ основан на свойствах символа Лежандра в конечных полях.