Słynny papier P = BPP Impagliazzo i Wigdersona

11

Czytam słynny artykuł Impagliazzo i Wigdersona w 1997 roku. Ponieważ jestem nowy w tej dziedzinie, a artykuł jest zwięzłą wersją konferencji, mam trudności z podążeniem za nimi. W szczególności niektórym z ich nowych twierdzeń brakuje dowodów. Według mojej najlepszej wiedzy nie opublikowano wersji czasopisma.P.=bP.P.

Szukam zasobów, z których mogę dowiedzieć się o ich wynikach, najlepiej tych z dowodami formalnymi. Byłbym bardzo wdzięczny, gdybyś mógł mi powiedzieć o takich zasobach.

Pteromys
źródło

Odpowiedzi:

16

Zobacz rozdział 7 monografii Salila Vadhana . Następstwem 7,64 jest wynik Impagliazzo i Wigdersona.

Sasho Nikolov
źródło