Czy dowody, że permanent nie jest w mundurze

Jest to kontynuacja tego pytania i jest związana z tym pytaniem Shivy Kinali.

Wydaje się, że dowody w tych dokumentach ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) używają twierdzeń hierarchicznych. Chcę wiedzieć, czy dowody są „ czystymi ” twierdzeniami o diagonalizacji, czy też używają czegoś więcej niż zwykła diagonalizacja. Więc moje pytanie brzmi

czy istnieje uzasadniona relatywizacja, która powoduje, że permanentna staje się jednolita ? $\mathsf{TC^0}$

Zauważ, że nie jestem pewien, jak zdefiniować dostęp do wyroczni dla jednolitego , wiem, że znalezienie poprawnej definicji dla małych klas złożoności nie jest łatwe. Inną możliwością jest to, że permanent nie jest kompletny dla w relatywizowanym wszechświecie, w którym to przypadku powinienem użyć jakiegoś kompletnego problemu dla w relatywizowanym wszechświecie zamiast tego i myślę, że powinien mieć kompletny problem w jakimkolwiek rozsądnym przypadku relatywizowany wszechświat. $\mathsf{TC^0}$ $\mathsf{\#P}$ $\mathsf{\#P}$ $\mathsf{\#P}$

cc.complexity-theory lower-bounds relativization permanent Kaveh
źródło

Jak zdefiniować relatywną wersję permanentu? A może szukasz relatywizowanego świata, w którym PP⊆TC ^ 0?

Tsuyoshi Ito,

@Tsuyoshi: Problemem jest to, nie jestem pewny dowód, że stały skompletowany dla

. Wydaje mi się, że dowód na to, że permanent nie jest w mundurze

działa również na każdy inny kompletny problem. Rozsądna relatywizacja, która umieszcza

wewnątrz

, odpowiedziałaby na moje pytanie.

s h a r p P

$sharpP$

T C^{0}

$TC^0$

s h a r p P

$sharpP$

T C^{0}

$TC^0$

Kaveh

Nie jestem pewien, co rozumiesz przez „rozsądną” relatywizację. Dla dowolnych dwóch klas złożoności można je wyrównać, biorąc wystarczająco silną wyrocznię, prawda? Np

. (Pierwsza klasa to

z „bramkami QBF”.)

A C 0^{P S P A C E} = P S P A C E = P S P A C E^{P S P A C E}

$AC0^{PSPACE} = PSPACE = PSPACE^{PSPACE}$

A C 0

$AC0$

Ryan Williams

@ Ryan: Pomyślałem, że sposób definiowania dostępu do wyroczni jest ważny, a jeśli definicja nie jest odpowiednia, mogą się zdarzyć dziwne rzeczy. Na przykład zobacz to cs.toronto.edu/~sacook/homepage/rel-web.ps . (uwaga: nie pamiętałem, że oni również dyskutować

). Maszyna z więcej środków może zapytać bardziej skomplikowanych pytań niż mniejszego jednej postaci taką samą wyrocznię i to jest powodem, że nie mamy a (rozsądne ) relatywizacja, która sprawiłaby, że DTime (n) = DTime (

), więc wydaje mi się, że nie jest tak proste, jak mówisz, prawda?

T C^{0}

$TC^0$

n^{2}

$n^2$

Kaveh

(logarytmiczna hierarchia czasu)

, więc nie powinno być rozsądnej relatywizacji, która spowodowałaby, że

. Wydaje mi się, że coś jest nie tak z moim rozumowaniem w poprzednim wierszu. Czy wiemy, że

A C^{0} = L H

$AC^0 = LH$

\subset P H \subseteq P S p a c e

$\subset PH \subseteq PSpace$

A C^{0} = P S p a c e

$AC^0 = PSpace$

L H \subset P H

$LH \subset PH$

Kaveh

Odpowiedzi:

Każde rozdzielenie klas zamkniętych w ramach „zasobów wielomianowych” ma wyrocznię, która je wyrówna. (Pod warunkiem, że mechanizm wyroczni jest sprawiedliwy i pozwala obu modelom maszyn na wykonywanie zapytań o wielomian długości i nie więcej.)

Niech będzie „ z bramkami dla wyroczni ”. Pozwalając być kompletnym językiem przy redukcjach , mamy , gdzie w mechanizmie Oracle dla $TC0^{O}$ $TC0$ $O$ $O$ $PSPACE$ $TC0$ $TC0^{O} = PSPACE = PSPACE^{O} = PP^{O}$ , liczymy użycie miejsca na taśmie Oracle wraz z resztą pamięci. (Tak więc zadawane są tylko kwerendy o długości wielomianowej.) Taka równość obowiązuje dla wielu klas „zamkniętych pod zasobami wielomianowymi”, w tym sensie, że mogą one zadawać kwerendy o długości wielomianowej do wyroczni, ale nie większe. Klasy te obejmują rzeczy takie jak , , (pod innym mechanizmem wyroczni, który nie liczy zapytań wyroczni w kierunku ograniczonej przestrzeni), , , i $PSPACE$ $AC0$ $TC0$ $LOGSPACE$ $P$ $NP$ $PH$ . Tak więc każde oddzielenie klas na tej liście musi koniecznie wykorzystywać jakiś argument „nierelatywizujący”. Oznacza to również (na przykład), że naturalne dowody rzeczy takich jak Parytet nie w nie są relatywistyczne (ale jest to jeszcze łatwiejsze: wszystko, czego potrzebujesz tutaj, to wyrocznia dla parzystości, więc otrzymujesz ). $PP$ $AC0$ $AC0[2]$

W kolekcji cytowanych przez ciebie dowodów uważam, że większość z nich (jeśli nie wszystkie) działa, zakładając i wyprowadzając sprzeczność. Tego rodzaju wyniki nazywane są „pośrednią diagonalizacją”. Więc relatywizacja ich dowód musiałby powiedzieć: „jeśli , to sprzeczność ...”, ale to założenie jest faktycznie prawda przez jakiś wyrocznie . $TC0 = PP$ $TC0^{O} = PP^{O}$ $O$

W komentarzach wskazano, że w sposób, w jaki go używam. To tylko subtelności z mechanizmem wyroczni. Po stronie LOGSPACE taśma zapytania nie może być częścią ograniczonej przestrzeni, ponieważ zapytania mają długość wielomianową. Po stronie PSPACE taśma zapytania jest $LOGSPACE^{O} = PSPACE^{O}$ wzięte jako część ograniczonej przestrzeni. To miało uczynić wszystko „sprawiedliwym”. Ale jeśli dasz im dokładnie ten sam mechanizm wyroczni, to rzeczywiście możesz je ponownie rozdzielić poprzez przekątną. Na przykład, jeśli zapytania nie liczą się do ograniczonej przestrzeni, to w PSPACE ^ {PSPACE} możesz zadawać wykładniczo długie pytania do PSPACE, więc tak naprawdę zawiera EXPSPACE. Przepraszam, że nie powiedziałem tego wcześniej.

Obliczenia ograniczone przestrzenią są bardzo subtelne w odniesieniu do wyroczni. Zobacz stronę 5 tego artykułu autorstwa Fortnow, aby uzyskać dobre podsumowanie, dlaczego obliczenia w Oracle i przestrzeni nie zawsze się mieszają.

Ryan Williams
źródło

Dziękujemy za komentarz na temat PSPACE ^ {PSPACE} zawierającej EXPSPACE w modelu, którego użyliśmy dla LOGSPACE. Moje zamieszanie zostało usunięte.

Robin Kothari,

Zobacz także Aehlig, Cook i Nguyen, Relatywizacja małych klas złożoności i ich teorii .

Yuval Filmus