Quais são as consequências de

Shiva Kintali acaba de anunciar um resultado (legal!) De que o isomorfismo do gráfico para gráficos de largura de árvore limitada de largura é duro $\geq 4$ $\oplus L$ . Informalmente, minha pergunta é: "Quão difícil é isso?"

Sabemos que não uniforme , veja as respostas para esta pergunta . Também sabemos que é improvável que , veja as respostas para esta pergunta . Quão surpreendente seria se ? Já ouvi muitas pessoas dizerem que não seria chocante como seria. $NL \subseteq \oplus L$ $\oplus L = P$ $L=\oplus L$ $L=NL$ $P=NP$

Quais são as consequências de ? $L=\oplus L$

Definição: é o conjunto de idiomas reconhecidos por uma máquina de Turing não determinística que só pode distinguir entre um número par ou um número ímpar de caminhos de "aceitação" (em vez de um número zero ou diferente de zero de caminhos de aceitação) e que é ainda mais restrito ao trabalho no espaço logarítmico. $\oplus L$

cc.complexity-theory complexity-classes logspace Aaron Sterling
fonte

Respostas:

Wigderson provou que . Por argumentos padrão, implicaria . (Aqui máquina em . Tem uma máquina equivalente em $NL/poly \subseteq \oplus L/poly$ $L = \oplus L$ $L/poly = NL/poly$ $M$ $NL/poly$ $M'$ . Pegue alinguagem dos pares de conselhos de instância . Se este idioma está em , em seguida, por codificar o aconselhamento adequado obtemos uma máquina equivalente a ). $\oplus L/poly$ $\oplus L$ $S = \{(x,a)~|~M'(x,a)~\textrm{accepts}\}$ $L$ $a$ $L/poly$ $M$

Eu acho que isso seria surpreendente: programas de ramificação não determinísticos seriam equivalentes a programas de ramificação determinísticos (até fatores polinomiais).

Ryan Williams
fonte

(O resultado Widgerson estava incorporado por NL / poli = UL / poli .)

Bem, se , a simulação dos circuitos estabilizadores está em , já que Aaronson e Gottesman (Physical Review A 70, 052328) provaram que essa simulação é completa para sob reduções de espaço de log, ou mais fracamente que a simulação de redes CNOT esteja em . De forma equivalente, se a simulação de tais circuitos é em , em seguida, . Pessoalmente, eu consideraria isso surpreendente, mas não da maneira que eu caí da cadeira, consideraria surpreendente. $L=\oplus L$ $L$ $\oplus L$ $L$ $L$ $L = \oplus L$ $P=NP$

Joe Fitzsimons
fonte

Obrigado. Existe uma explicação intuitiva para o que os circuitos estabilizadores podem fazer? Eu não estou familiarizado com eles.

Aaron Sterling

@AaronSterling: Os circuitos estabilizadores são um modelo restrito de computação quântica; eles são gerados por portas CNOT (calculando reversivelmente o XOR de dois bits de entrada) e duas portas que não possuem análogos imediatos na computação clássica. Atuando em entradas "clássicas" (os chamados estados de base computacional) ou em entradas que são apenas levemente mais gerais que as entradas "clássicas", elas podem ser simuladas eficientemente em termos de transformações simpléticas no módulo 2, apesar de serem de sabor mecânico quântico ( e apenas um pouco tímido de ser capaz de universalidade para computação quântica).

Niel de Beaudrap

@AaronSterling: Eles são um subconjunto de todos os circuitos quânticos que incluem CNOTS (essencialmente XOR + fanout), além de vários portões quânticos que podem criar superposições iguais (por exemplo, portões Hadamard). Se você é familiar com a computação quântica, os circuitos correspondem aos operadores que mapeiam os operadores Pauli para outros operadores Pauli sob conjugação, atuando sobre a entrada clássica (ou entrada que pode ser obtida da entrada clássica através de outro circuito do grupo Clifford).

91111 Joe Fitzsimons

Acho que precisamos de uma hierarquia "surpresa", com 'cair da minha cadeira" no topo :)

Suresh Venkat