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

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

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

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

Abstract

Доказательство знаменитой теоремы Тода о том, что полиномиальная иерархия содержится в

, основано на лемме Вэлианта-Вазирани: существует вероятностное сведение

к

. В доказательстве этой леммы сначала предъявляется некоторое вероятностное сведение с вероятностью успеха

, а потом это сведение улучшается стандартным способом при помощи комбинирования полиномиального числа случайных величин. В докладе будет рассказано об алгебраическом сведении, которое сразу обеспечивает константную вероятность успеха и не нуждается в улучшении. Это сведение очень простое, и его анализ основан на свойствах символа Лежандра в конечных полях.