Interaktywne proofy dla poziomów hierarchii wielomianowej

33

Wiemy, że jeśli masz maszynę PSPACE, jest ona wystarczająco mocna, aby dać interaktywny dowód dowolnego poziomu hierarchii wielomianowej. (I jeśli dobrze pamiętam, wszystko czego potrzebujesz to #P.) Ale załóżmy, że chcesz dać interaktywny dowód członkostwa w języku . Czy wystarczy rozwiązać problemy w ? Czy rozwiązywanie problemów w odpowiednie? Mówiąc bardziej ogólnie, jeśli potrafisz rozwiązać problemy lub , to po co to wystarcza do wygenerowania interaktywnych dowodów wszystkich języków w ? $\Sigma_2$ $\Sigma_2$ $\Sigma_5$ $\Sigma_k$ $\Pi_k$ $\Sigma_\ell$ $\Sigma_\ell$

To pytanie zostało zainspirowane tym pytaniem dotyczącym wymiany stosu cstheory .

cc.complexity-theory interactive-proofs Peter Shor
źródło

Czy jesteś zainteresowany tylko przypadkiem pojedynczego dowcipu, czy interesuje Cię przypadek wielu dowódców? Wydaje mi się, że oczywistym sposobem na zaatakowanie tego byłoby użycie PCP, co może być proste dla dwóch dowódców, ale prawdopodobnie nie zadziała dla jednego dowcipu.

Joe Fitzsimons,

1

Byłbym zainteresowany w obu przypadkach. Od dłuższego czasu zastanawiałem się nad tym pytaniem dotyczącym pojedynczych testów, ale wcale nie myślałem o wielu testach.

Peter Shor,

4

@Peter: Patrząc na dokument IP = PSPACE, wydaje się, że dowód przejdzie przy użyciu

(co jest kompletne dla

), a nie QBF, pod warunkiem, że masz wystarczająco mocnego, by obliczyć wielomian tożsamości wynikające z arytmizacja

. Czy coś brakuje?

{QBF}_{k}

$\mbox{QBF}_k$

Σ_{k}^{P}

$\Sigma^P_k$

{QBF}_{k}

$\mbox{QBF}_k$

Joe Fitzsimons,

1

@Joe, nie zastanawiałem się nad tym pomysłem; to może zadziałać.

Peter Shor,

2

Joe, może powinieneś zamieścić to jako odpowiedź

Suresh Venkat

25

Nawet w celu podania adresu IP dla koNP, przy użyciu obecnych technik, trzeba arytmetyzować, tzn. Użyć liczenia, co oznacza zasadniczo pełną moc #P. Wydaje mi się, że każdy słabszy prover, nawet dla CoNP, byłby bardzo interesujący (w szczególności oznaczałby nową technikę nierelatywną).

Noam
źródło

@Peter: Noam ma rację. Cytuję stąd następujące wiersze : ... oparcie skrótu odpornego na kolizję na najgorszą twardość NP poprzez redukcję czarnej skrzynki oznacza interaktywny system dowodu dla co-NP z dowcipem w BPP ^ NP ... Wszystkie znane (nawet z wieloma dowodami) systemy dowód dla co-NP wymagają dowodu o złożoności #P ...

MS Dousti

W takim przypadku moja odpowiedź najprawdopodobniej jest bzdurą. Dzięki za zwrócenie na to uwagi.

Joe Fitzsimons,

W rzeczywistości jest to naprawdę interesujące, biorąc pod uwagę, że interaktywny dowód na nieizomorfizm graficzny wymaga jedynie przysłowia z wyrocznią dla tego problemu. Wydaje się, że jest to dowód na to, że albo GI jest bardzo bardzo słaby (jak w P), albo granice interaktywnych dowodów poziomów wielomianowej hierarchii są prawdopodobnie bardzo luźne.

Joe Fitzsimons,

1

Zakładam, że wielu dowódców nie pomaga. Czy to jest poprawne?

Peter Shor

1

@Joe Dowód braku graficznego izomorfizmu na wykresie jest stałym okrągłym publicznym dowodem na monety, tym samym zaliczając go do klasy AM (powszechnie uważa się, że jest równy NP, a zatem uważa się, że GI i DNB są w

). Jest to znacznie mniej niż wielomianowy dowód rundy, który uważa się za niezbędny do udowodnienia członkostwa w całkowitych problemach koNP.

N P \cap c o N P

$NP \cap coNP$

Boaz Barak

21

To znany (cudowny) otwarty problem, nad którym od czasu do czasu pracowałem bez powodzenia.

Avi Wigderson i ja wspomnieliśmy o tym problemie w naszym artykule na temat algebriacji , w którym podnieśliśmy pytanie, czy pojemniki takie jak coNP ⊆ IP _NP można udowodnić za pomocą technik algebrizowania. (Tutaj IP _NP oznacza adres IP z weryfikatorem BPP i przysłowiową ^NP BPP .) Jeśli (jak przypuszczam) odpowiedź brzmi „nie”, to stanowiłoby formalny powód, dla którego jakikolwiek interaktywny protokół, taki jak ten, o który pyta Peter, wymagałby braku relatywizacji techniki, które „wykraczają zasadniczo poza” stosowane w przypadku IP = PSPACE.

Analogiczne pytanie brzmi, czy BQP = IP _BQP , gdzie IP _BQP oznacza IP z weryfikatorem BPP i prover BQP (kwantowy czas wielomianowy). To pytanie jest również otwarte --- chociaż niedawny przełom dokonany przez Broadbent, Fitzsimons i Kashefi pokazał, że ściśle powiązane stwierdzenie jest prawdziwe.

Scott Aaronson
źródło

20

Tak, pytanie o to, czy coNP ma interaktywny dowód, w którym prover jest słabszy niż #P (powiedzmy, polytime z dostępem do NP oracle) jest dobrze znanym otwartym pytaniem. Poniższy ostatni artykuł Haitnera, Mahmoody'ego i Xiao omawia to pytanie i pokazuje pewne konsekwencje założenia, że nie można tego zrobić.

Boaz Barak
źródło

11

Ponieważ Suresh zasugerował, żebym opublikował swój komentarz jako odpowiedź, zrobię to. Jednak nie uważam tego za pełną odpowiedź, ponieważ nie próbowałem tego udowodnić, i może okazać się ślepy zaułek.

$\mbox{QBF}_k$ $\Sigma^P_k$ $\mbox{QBF}_k$ $\Sigma^P_k$ ), powtarzając arytmetyzację w każdej rundzie, gdy weryfikator poda swoje losowe wybory.

Joe Fitzsimons
źródło

problem pojawia się już w dowodzie na koNP. Protokół sumcheck ma n rund (po jednej dla każdej zmiennej). W każdej rundzie prover musi wymyślić współczynniki wielomianu, który jest uzyskiwany przez jakąś wykładniczo dużą sumę. Nie wiem, jak to zrobić, zużywając mniej energii niż #P.

Boaz Barak

@Boaz: Tak, myślę, że takie podejście może zawieść. Myślałem, że widziałem wersję arytmetyki wykonaną gdzieś w taki sposób, że wielomian przyjął wartości 1 lub 0 tylko dla danych wejściowych 0 i 1. W takim przypadku wydaje się, że można użyć wyroczni dla odpowiedniego problemu decyzyjnego. Z drugiej strony, mogłem to sobie wyobrazić!

Joe Fitzsimons,

Interaktywne proofy dla poziomów hierarchii wielomianowej

Odpowiedzi: