Impagliazzo и знаменитая статья Вигдерсона P = BPP

11

Я читаю знаменитую статью Impagliazzo и Wigderson в 1997 году. Так как я новичок в этой области, и эта статья является краткой версией конференции, мне трудно следить за их доказательствами. В частности, некоторые из их новых теорем не имеют доказательств. Насколько мне известно, не было опубликовано ни одной версии журнала.P=BPP

Я ищу ресурсы, из которых я могу узнать их результат, предпочтительно те, которые имеют формальные доказательства. Буду очень признателен, если вы расскажете мне о таких ресурсах.

Pteromys
источник

Ответы:

16

Проверьте главу 7 монографии Салила Вадхана . Следствие 7.64 - результат Импальяццо и Вигдерсона.

Сашо Николов
источник