Czy jednolity RNC jest zawarty w przestrzeni polilogu?

Logarytmiczna jednolita NC jest zawarta w deterministycznej przestrzeni polilogu (czasami zapisywanej jako PolyL). Czy RNC o jednolitej przestrzeni logów również należy do tej klasy? Standardowa losowa wersja PolyL powinna być w PolyL, ale nie widzę, aby (jednolity) RNC był w randomizowanym-PolyL.

Trudność, jaką widzę, polega na tym, że w RNC obwód może „patrzeć na losowe bity” tyle, ile chce; tzn. losowe dane wejściowe mogą mieć dowolne rozwinięcie. Ale w losowej wersji PolyL nie jest tak, że dostajesz taśmę losowych bitów, na które patrzysz tyle, ile chcesz; raczej możesz rzucić monetą tylko za każdym razem.

Dzięki!

Być może większość ludzi myśli, że R N C ⊆ D S P A C E ( p o l y l o g ) (lub nawet że R N C = N C ), ale jestem sceptyczny co do tego (patrz druga część mojego odpowiedź poniżej). Jeśli R N C jest rzeczywiście zawarty w D S P A C E ( p o l y l o g ) , to jest również zawarty w $\mathsf{RNC}\subseteq \mathsf{DSPACE(polylog)}$$\mathsf{RNC}=\mathsf{NC}$$\mathsf{RNC}$$\mathsf{DSPACE(polylog)}$T I M E ( 2 s O l a L O g ) (bardziej szczegółowo, w D T I M E ( 2 s O l a L O g ) przez wyczerpującego poszukiwania).$\mathsf{NTIME(2^{polylog})}$$\mathsf{DTIME(2^{polylog})}$

Valentine Kabanets wyjaśniono mi następujące (folklor) argument z jego papieru Russell Impagliazzo który wyjaśnia dlaczego R N C ⊆ N T I M E ( 2 s O l a L O g ), jest mało prawdopodobne.$\mathsf{RNC} \subseteq \mathsf{NTIME(2^{polylog})}$

Twierdzenie: Jeżeli R N C ⊆ N T I M E ( 2 p o l y l o g ) , to ani N E X P nie jest obliczalna przez obwody boolowskie o wielkości o ( 2 n / n ) (tj. Sub-maks. Shannon; nieistotny, ale spójność patrz Lupanowa), lub Stała nie jest obliczalna na podstawie wzorów arytmetycznych (bez podziału) na Z o wielkości quasipolynomialnej.$\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$$\mathsf{NEXP}$$o(2^n/n)$${\mathbb Z}$

Dowód: załóż R N C ⊆ N T I M E ( 2 p o l y l o g ) . Jeśli Permanent ma formułę wielkości quasipolynomial, możemy zgadnąć i zweryfikować taką formułę dla Permanent przy użyciu quasipolynomial wielomianowego testera tożsamości z założenia. Spowoduje to umieszczenie opcji Permanent w N T I M E ( 2 p o l y l o g ) .$\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$$\mathsf{NTIME(2^{polylog})}$

O tw toda, w Σ 2 jest wówczas również w N T I M E ( 2 s O l a L O g ) . Przez napawanie liniowa wykładniczej wersji czasu Ď 5 jest również N E X P . Zatem wersja liniowo-wykładnicza Σ 5 ma obwód o wielkości o ( 2 n / n ) (tj. Submaks.). Ale prostym argumentem diagonalizacji można wykazać, że liniowo-wykładnicza wersja Σ $\Sigma_2$$\mathsf{NTIME(2^{polylog})}$$\Sigma_5$$\mathsf{NEXP}$$\Sigma_5$$o(2^n/n)$$\Sigma_5$wymaga maksymalnego rozmiaru obwodu, co jest sprzecznością (nawiasem mówiąc, jest to wariant pytania średniego poziomu dla absolwentów na poziomie złożoności; dobrze, może udowodnienie, że E X P S P A C E wymaga obwodów o maksymalnych rozmiarach jest prostszy). CO BYŁO DO OKAZANIA.$\mathsf{EXPSPACE}$

Teraz niepopularny kierunek.

Wiemy już, że losowość czytana wiele razy może zrobić coś nieoczywistego. Ciekawy przykład można znaleźć w „ Making Unondeterminism jednoznaczny ” Reinhardta i Allendera (podają to w kategoriach niejednorodności, ale w zasadzie chodzi o użycie losowej wielokrotności odczytu). Innym interesującym przykładem (mniej bezpośrednio powiązanym) jest „ Losowość kupuje głębokość do przybliżonego liczenia ” Emanuele Violi. Chyba wszystko mówię, że nie będę zaskoczony, jeśli derandomization z R N C nie jest to, co większość ludzi będzie oczekiwać, że będzie.$\mathsf{RNC}$

(Jest też kilka innych artykułów, takich jak wspaniały artykuł Noama Nisana o losowości „jeden raz do odczytu” i „wiele do odczytu”, które pokazują, jak kupić błąd dwustronny z błędem jednostronnym.)

Nawiasem mówiąc, zrozumienie, jak skonstruować PRG oszukiwać modele obliczeniowe ograniczone przestrzenią z wieloma dostępami do ich danych wejściowych (np. Długości liniowe Bps) jest również bardzo związane z tym pytaniem.

- Periklis