Existem representações descritivas da complexidade das classes de complexidade quântica?

20

O título diz mais ou menos tudo, mas acho que poderia adicionar um pouco de fundo e alguns exemplos específicos nos quais estou interessado.

Teóricos da complexidade descritiva, como Immerman e Fagin, caracterizaram muitas das classes de complexidade mais conhecidas usando a lógica. Por exemplo, o NP pode ser caracterizado com consultas existenciais de segunda ordem; P pode ser caracterizado com consultas de primeira ordem com um operador de ponto menos fixo adicionado.

Minha pergunta é: houve alguma tentativa, especialmente bem-sucedida, de apresentar tais representações para classes de complexidade quântica, como BQP ou NQP? Se não, por que não?

Obrigado.

Atualização (moderador) : esta pergunta é completamente respondida por esta postagem no mathoverflow .

Philip White
fonte
1
veja a pergunta de Kaveh no MO: mathoverflow.net/questions/35236/…
Alessandro Cosentino
1
fechar como duplicado?
Suresh Venkat
3
Para aqueles que se perguntam por que essa pergunta foi encerrada como fora de tópico (como eu): Ignore o motivo próximo porque não faz sentido (desde que essa pergunta esteja relacionada). Fechar uma pergunta requer um dos vários motivos. "Duplicar exata" seria o motivo adequado, mas o sistema não nos permite fechar uma pergunta como uma duplicata exata de uma pergunta no MathOverflow. Portanto, acho que Suresh selecionou um dos motivos disponíveis aleatoriamente.
Tsuyoshi Ito
1
ps: acho que pode ser razoável considerar esses casos de maneira semelhante à postagem cruzada e não fechá-los. Alguém (por exemplo, o OP) publica uma resposta CW com base na (ou apenas um link para) a resposta no MO.
Kaveh
2
Eu reabri a pergunta.
Ryan Williams

Respostas:

7

Acho que a resposta de Robins à minha pergunta sobre MO também responde a essa.

A complexidade descritiva caracterização de uma classe de complexidade dá uma língua cujas consultas (ie fórmulas) são exatamente as funções computáveis em C . A sintaxe da linguagem é geralmente muito simples, ou seja, dada uma string q , é fácil verificar se q é uma consulta bem formada da linguagem, pelo menos espera-se que seja decidível (mas geralmente a verificação da sintaxe é feita em um classe de complexidade pequena). Isto implicaria enumerablity eficaz dos problemas na classe C e daria uma caracterização sintáctica para C . (Se a complexidade da verificação de sintaxe for baixa, também poderá implicar a existência de um problema completo para a classe.)CCqqCC

Nas observações acima, Robin ligado a Kord Eickmeyer e papel de Martin Grohe " A randomização e Derandomization em Descritiva Complexidade Teoria ", que dá uma caracterização "complexidade descritiva" de . Os próprios autores observam na introdução que isso é diferente do que geralmente se entende por uma caracterização descritiva da complexidade:BPP

Provamos que , a versão probabilística da lógica de ponto fixo com contagem, captura a classe de complexidade B P P , mesmo em estruturas não ordenadas. Para estruturas ordenadas, esse resultado é uma conseqüência direta do Teorema de Immerman-Vardi [7, 8], e para estruturas arbitrárias decorre da observação de que podemos definir uma ordem aleatória com alta probabilidade em BPIFP + C. Ainda assim, o resultado é surpreendente à primeira vista devido à sua semelhança com a questão em aberto de saber se existe uma lógica captura P , e porque se acredita que P = B P P .BPIFP+CBPPPP=BPP A limitação é que a lógica não tem uma sintaxe eficaz e, portanto, não é um “lógica” de acordo com [9] definição de Gurevich subjacente a questão para uma lógica que capta P . BPIFP+CPNo entanto, acreditamos que fornece uma descrição completamente adequada da classe de complexidade B P P , porque a definição de B P P é inerentemente ineficaz também (em oposição à definição de P em termos de conjunto de máquinas de Turing com relógio polinomial).BPIFP+CBPPBPPP

Não sou especialista em teoria finita de modelos / complexidade descritiva (e pessoalmente gostaria de ouvir mais de especialistas), mas sinto que há um pouco de trapaça aqui ao dizer que essa é uma caracterização descritiva da complexidade. A razão da minha opinião é que, se tivermos uma sintaxe não eficaz, podemos usar restrições semânticas arbitrárias para restringir a classe de consultas bem formadas e fornecer uma caracterização de "complexidade descritiva" para qualquer classe de complexidade. Por exemplo, considere (que captura P S p a c e ) e, em seguida, faça exatamente as consultas computáveis ​​em B Q PSO(TC)PSpaceBQP; ou considerar a linguagem que tem um símbolo de função para cada máquina em . Ambos capturam B Q P, mas não possuem uma sintaxe efetiva.BQPBQP

Kaveh
fonte
8

PσσσMφMφσR1,R2,

σσρσρ. Este é o meu massacre da Definição 1 no artigo de Eickmeyer-Grohe, vinculado por Robin Kothari. Em particular, o vocabulário não é finito (bem, cada vocabulário é, mas temos que considerar infinitos vocabulários distintos), o conjunto de sentenças dessa lógica é indecidível e a noção de satisfação é diferente da apresentada por Gurevich .

Aaron Sterling
fonte