Poderia ser usada uma versão descritiva da complexidade do teorema de Rice para separar AC0 e PSPACE?

10

Em esta questão , foi mencionado que existem versões de complexidade descritivos do teorema de Rice. Encontrei uma prova do seguinte teorema:

Dada uma classe de complexidade C , propriedades não triviais de idiomas em C não podem ser computadas em C

Eu já havia postado a prova que encontrei, mas, por ser tão longa e apontada nos comentários, que este artigo já contém uma prova desse teorema, eu a removi. (Se, por algum motivo, você estiver desesperado para ver minha prova, consulte as revisões anteriores desta pergunta.)

Meu interesse é se esse teorema pode ou não ser usado para separar AC0 e PSPACE. Aqui está o argumento:

Considere a propriedade P da classe de complexidade AC0 definida da seguinte maneira:

P : a propriedade de ser uma consulta FO que aceita uma estrutura fixa específica, ou seja, a estrutura que consiste em um elemento, sem funções, sem constantes e sem relações

Claramente, pelo teorema acima, P não é decidível em AC0; é uma propriedade não trivial das consultas FO.

No entanto, um pequeno exame deve mostrar que calcular se uma consulta de FO aceita ou não uma estrutura tão simples pode ser decidido tão facilmente quanto o TQBF; assim, P é decidível no PSPACE.

Para garantir clareza sobre este ponto (que P é computável no PSPACE): Observe que a propriedade em que estamos interessados ​​exige que a estrutura seja FO. Portanto, estamos tentando determinar se uma consulta FO que está sendo executada em uma estrutura de elemento único sem relações aceita. Como não há relações com as quais lidar, deve ficar claro que a tarefa de decidir essa consulta FO é equivalente a decidir uma instância do TQBF; como não há relações, o único desafio que resta é avaliar se a fórmula booleana quantificada é verdadeira ou não. Isso é basicamente apenas TQBF, então P é computável no PSPACE.

Como P é computável no PSPACE, mas não no AC0, devemos concluir que AC0! = PSPACE. Esse raciocínio está correto ou cometi um erro em algum lugar? Estou particularmente preocupado com o parágrafo anterior; Tentarei esclarecer e atualizar o argumento amanhã, depois de ter a chance de pensar um pouco mais na exposição.

Eu aceitaria como resposta um exemplo de uma consulta FO que, ao calcular a estrutura sem relação de um elemento que eu descrevi, claramente não faz sentido como uma instância do TQBF. (Estou sugerindo que não há um, portanto, se você puder mostrar que existe, isso seria um contra-exemplo.)

Obrigado.

Philip White
fonte
@ Kaveh: Você deve fazer o seu comentário uma resposta.
Dai Le
@ Kaveh: Obrigado pelo seu comentário. Estou um pouco confuso com o que você está dizendo. A qual máquina nos conjuntos PSPACE para AC0 você se referia? Eu estava me referindo à propriedade P, que se refere especificamente a consultas de FO sobre estruturas muito simples. Estou sugerindo que avaliar se as consultas FO aceitam uma estrutura simples é garantido como TQBF, que é PSPACE. Não vejo onde é necessário um simulador universal para AC0.
Philip White
@Kaveh: OK. Vou preparar minha tentativa de prova da conjectura nesta questão e postá-la como uma pergunta separada. Eu pensei que estava correto, mas muitas vezes estou errado. (É claro que, se você refutar minha conjectura antes, não vou incomodar.)
Philip White
Oh. Acabei de postá-lo como uma pergunta. Devo excluir a nova pergunta e publicá-la como resposta?
Philip White
(Excluí-o e adicionei-o a esta pergunta.) #
547 Philip White

Respostas:

7

Decidir as propriedades não triviais de conjuntos (de indexação) em uma classe de complexidade é tão difícil quanto calcular o gráfico da função universal da classe. Intuitivamente, isso significa que a única maneira de decidir uma propriedade não trivial é simular as máquinas e aguardar respostas. Parece-me que a idéia de usar tal propriedade fornecerá apenas o que é conhecido pelos teoremas da hierarquia. (Veja o teorema 4.2 de D. Kozen, " Indexação de classes sub-recursivas ", 1978 para obter detalhes e a declaração exata do teorema.)

grUAC0AC0PSpaceAC0LLPSpaceAC0AC0FOPSpacePSpaceAC0AC0PSapce

AC0LPSpace

Kaveh
fonte
Interessante, obrigado. Então você está dizendo: 1) Meu argumento estava certo, mas 2) Havia uma maneira mais fácil. :) Acho que preciso aprimorar o teorema da hierarquia espacial.
Philip White
FO
OK ótimo. Na verdade, acabei de verificar a definição de FO. Eu sabia que isso incluía o símbolo da igualdade; por isso exigi que a estrutura fosse apenas um elemento. Dessa forma, qualquer declaração sobre a igualdade de duas variáveis ​​não afetará a verdade da consulta.
Philip White
Um comentário adicional ... você fez uma observação importante sobre os símbolos não lógicos. Como não há relações, o símbolo da igualdade é realmente essencial. Em particular, é necessário expressar os literais muito booleanos necessários para expressar o TQBF.
Philip White
FO