Jaki jest „prawdziwy” powód, dla którego IP = PSPACE nie powoduje relatywizacji?

$O$ ${\sf coNP}^O \not\subseteq {\sf IP}^O$ ${\sf coNP}^O \subseteq {\sf PSPACE}^O$ $O$

Jednak widziałem tylko kilka osób, które wyjaśniają „bezpośrednio”, dlaczego wynik nie jest relatywizowany, a typową odpowiedzią jest „arytmetyzacja”. Po sprawdzeniu dowodu IP = PSPACE ta odpowiedź nie jest fałszywa , ale nie jest dla mnie zadowalająca. Wydaje się, że „prawdziwy” powód sięga do dowodu, że problem TQBF - prawdziwie skwantyfikowana formuła boolowska - jest kompletny dla PSPACE; aby to udowodnić, musisz pokazać, że możesz zakodować konfiguracje maszyny PSPACE w formacie wielomianowym, a (wydaje się, że jest to część niezwiązana z relatywizacją) możesz zakodować „poprawne” przejścia między konfiguracjami w wielomianowym rozmiarze formuła boolowska - wykorzystuje krok w stylu Cooka-Levina. ${\sf IP} = {\sf PSPACE}$

Intuicja, którą opracowałem, polega na tym, że wyniki nierelatywistyczne to takie, które szukają drobiazgów w maszynach Turinga, a krok, w którym TQBF jest kompletny dla PSPACE, to miejsce, w którym dzieje się to szturchanie - i krok arytmetyczny może Stało się tak tylko dlatego, że miałeś wyraźną logiczną formułę do arytmetyki.

Wydaje mi się, że jest to podstawowy powód, dla którego IP = PSPACE nie ma charakteru relatywistycznego; a mantra folklorystyczna, której techniki arytmetyczne nie relatywizują, wydaje się być produktem ubocznym tego: jedynym sposobem na arytmetyzację jest posiadanie boolowskiej formuły, która koduje coś o bazach TM!

Czy czegoś brakuje? Jako podpytanie - czy to oznacza, że wszystkie wyniki, które w jakiś sposób wykorzystują TQBF, również nie relatywizują?

cc.complexity-theory interactive-proofs relativization Henry Yuen
źródło

Możesz uwzględnić wrota wyroczni w skwantyfikowanej formule boolowskiej, a następnie taki relatywny TQBF ^ O jest kompletny dla PSPACE ^ O, więc nie jest to krok niezwiązany z relatywizacją.

Emil Jeřábek wspiera Monikę

Cześć Emil - czy mógłbyś rozwinąć nieco więcej? Powiedzmy, że mam maszynę i próbuję przeprowadzić ten sam dowód, że L (M) (język akceptowany przez M) można zredukować do (cokolwiek oznacza). W końcu będę musiał opracować boolowską formułę, która wyraża, czy dwie konfiguracje C, C 'maszyny M Oracle są sąsiadami (dla dowolnych dwóch konfiguracji C, C'). Jak mogę zapewnić, niezależnie od wyroczni, że ta formuła boolowska ma skończony rozmiar, a co dopiero wielomian? Na przykład O może kodować problem zatrzymania.

{P S P A C E}^{O}

${\sf PSPACE}^O$

T B Q F^{O}

$TBQF^O$

T B Q F^{O}

$TBQF^O$

Henry Yuen,

Wydaje mi się, że mógłbym to przesunąć jeszcze bardziej - czy samo twierdzenie Cooka-Levina relatywizuje się? Z tych samych powodów, o których mowa powyżej, nie sądzę, żeby tak było. To, czy twierdzenie Cooka-Levina relatywizuje, determinuje, czy dowód TQBF na kompletność PSPACE również się relatywizuje.

Henry Yuen,

Formuła QBF ^ O może, oprócz zwykłych kwantyfikatorów i łączników boolowskich, również używać nowej nieograniczonej bramki wachlarza, nazwijmy ją

, której semantyką jest

wtedy i tylko wtedy ciągu

należy do oracle

. Wyrażenie w tym języku, że jedna konfiguracja jest następcą innej, jest prostym ćwiczeniem, ponieważ można po prostu podłączyć zawartość taśmy zapytania Oracle do

f (x_{0}, \dots, x_{n})

$f(x_0,\dots,x_n)$

f (x_{0}, \dots, x_{n}) = 1

$f(x_0,\dots,x_n)=1$

x_{0} \dots x_{n}

$x_0\dots x_n$

O

$O$

f

$f$ . (Zakładam tutaj, że maszyna PSPACE może wykonywać zapytania wielomianowo długie).

Emil Jeřábek obsługuje Monikę

Rozumiem - mówisz, że relatywizując dowód kompletności TQBF PSPACE, nie tylko relatywizujesz maszyny w grze, ale także relatywizujesz same formuły boolowskie (więc nie są to już formuły boolowskie w ścisłym tego słowa znaczeniu) ). W takim przypadku widzę, dlaczego krok arytmetyczny miał się załamać. Dzięki! Być może możesz napisać to jako odpowiedź.

Henry Yuen,

Każda odpowiedź na pytanie o formę „Jaki jest prawdziwy powód, dla którego…” niekoniecznie musi być nieco subiektywna. Jednak w przypadku szczególnego przypadku IP = PSPACE uważam, że można dość dobrze argumentować, że arytmetyzacja jest rzeczywiście kluczem, obserwując, że chociaż IP = PSPACE nie relatywizuje się , to robi algebry w rozumieniu Aaronsona i Wigdersona . Jak wyjaśniają w swoim artykule, z grubsza rzecz biorąc, włączenie klasa złożoności algebrizes jeśli dla wszystkich wyrocznie i wszystkie rozszerzenia niskich stopni z ${\cal C} \subseteq {\cal D}$ ${\cal C}^A \subseteq {\cal D}^{\tilde A}$ $A$ $\tilde A$ . W szczególności pokazują, że włączenie PSPACE IP algebryzy, nawet jeśli nie relatywizuje. $A$ $\subseteq$

Intuicja, którą opracowałem, polega na tym, że nierelatywistyczne wyniki to takie, które szarpią się z podstępną precyzją maszyn Turinga

Nie jest to zła intuicja, ale myślę, że wynik Aaronsona-Wigdersona pokazuje, że dowód IP = PSPACE jest dość ograniczony, a na pewno nie w wystarczająco wyrafinowany sposób, aby udowodnić P NP, ponieważ Aaronson i Wigderson również wykazać, że do oddzielenia P od NP konieczne będą techniki niegebergezyjne. $\ne$

Timothy Chow
źródło

Dzięki za referencje. Pozwól mi zobaczyć, czy mogę to zrozumieć: co ty - a papier Aaronson / Wigderson - zdają się twierdzić, że „arithmetization” jest słabo non-relatywizacji krok, a maleńkim, naturalne zmiany w pojęciu relatywizacji (mianowicie, algebraiczna relatywizacja) złamie tę właściwość. Ponieważ reszta dowodu IP = PSPACE jest relatywizacyjna (i przekonuje mnie to, co powiedział Emil powyżej), oznacza to, że sam wynik IP = PSPACE jest bardzo słabo relatywistyczny, co powiedziałeś. Bardzo interesujące! Dzięki. Potrzebuję sposobu na zaakceptowanie obu odpowiedzi :)

Henry Yuen

Tak, to w zasadzie racja.

Timothy Chow

Jaki jest „prawdziwy” powód, dla którego IP = PSPACE nie powoduje relatywizacji?

Odpowiedzi: