Jakie są konsekwencje ?

Shiva Kintali właśnie ogłosił (zimne!) Co powoduje, że izomorfizm wykres dla ograniczonych wykresach treewidth szerokości IS -hard$\geq 4$$\oplus L$ . Nieformalnie moje pytanie brzmi: „Jak trudne to jest?”

Wiemy, że nierównomiernie , patrz odpowiedzi na to pytanie . Wiemy również, że jest mało prawdopodobne, aby , zobaczył odpowiedzi na to pytanie . Jak zaskakujące byłoby, gdyby ? Słyszałem, że wiele osób mówi, że nie byłoby szokujące jak .$NL \subseteq \oplus L$$\oplus L = P$$L=\oplus L$$L=NL$$P=NP$

Jakie są konsekwencje ?$L=\oplus L$

Definicja: jest zestawem języków rozpoznawanych przez niedeterministyczną maszynę Turinga, która może rozróżniać tylko parzystą liczbę lub nieparzystą liczbę ścieżek „akceptacji” (zamiast zerowej lub niezerowej liczby ścieżek akceptacji) oraz który jest dodatkowo ograniczony do pracy w przestrzeni logarytmicznej.$\oplus L$

Wigderson udowodnił, że . Według standardowych argumentów oznacza . (Weź maszynę w języku . Ma ona równoważną maszynę w . Weź język par instancji-porad . Jeśli ten język jest w , to po zapisaniu odpowiedniej porady otrzymujemy maszynę odpowiadającą )$NL/poly \subseteq \oplus L/poly$$L = \oplus L$$L/poly = NL/poly$$M$$NL/poly$$M'$$\oplus L/poly$$\oplus L$$S = \{(x,a)~|~M'(x,a)~\textrm{accepts}\}$$L$$a$$L/poly$$M$

Myślę, że byłoby to zaskakujące: niedeterministyczne programy rozgałęziające byłyby równoważne deterministycznym programom rozgałęziającym (do czynników wielomianowych).

Cóż, jeśli to symulacja obwodów stabilizatora jest w , ponieważ Aaronson i Gottesman (Physical Review A 70, 052328) udowodnili, że taka symulacja jest zakończona dla przy zmniejszeniu przestrzeni logów lub, co słabsze, że symulowanie sieci CNOT jest w . Równoważnie Jeżeli symulacja takich układów jest następnie . Osobiście uważałbym to za zaskakujące, ale nie w wyniku upadku z fotela uznałbym zaskakujące.L ⊕ L L L L = ⊕ L P = N $L=\oplus L$$L$$\oplus L$$L$$L$$L = \oplus L$$P=NP$