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 .
fonte
Respostas:
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.)C C q q C C
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:B PP
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) PSp a c e B Q P ; 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.B Q P B Q P
fonte
fonte