As provas de que permanente não está uniforme relativizadas?

Este é um acompanhamento para esta questão e está relacionado a esta questão de Shiva Kinali.

Parece que as provas desses artigos ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) usam teoremas de hierarquia. Quero saber se as provas são teoremas de diagonalização " puros " ou se usam algo mais que a diagonalização usual. Então minha pergunta é

existe uma relativização razoável que coloca permanente no uniforme $\mathsf{TC^0}$ ?

Observe que não tenho certeza de como definir o acesso ao oracle para uniforme , sei que encontrar a definição correta para pequenas classes de complexidade não é trivial. Outra possibilidade é que permanente não esteja completo para no universo relativizado, caso em que eu deveria usar algum problema completo para no universo relativizado no lugar dele, e acho que deve ter um problema completo de qualquer maneira razoável. universo relativizado. $\mathsf{TC^0}$ $\mathsf{\#P}$ $\mathsf{\#P}$ $\mathsf{\#P}$

cc.complexity-theory lower-bounds relativization permanent Kaveh
fonte

Como você define uma versão relativizada da permanente? Ou você está procurando um mundo relativizado em que PP⊆TC ^ 0?

Tsuyoshi Ito

@Tsuyoshi: O problema é que eu não estou certo sobre a prova de que ser permanente completa para

. Parece-me que a prova de que a permanente não está uniforme

também funciona para qualquer outro problema completo. Uma relativização razoável que coloque

dentro de

responderia à minha pergunta.

s h a r p P

$sharpP$

T C^{0}

$TC^0$

s h a r p P

$sharpP$

T C^{0}

$TC^0$

Kaveh

Não sei ao certo o que você quer dizer com relativização "razoável". Para quaisquer duas classes de complexidade, é possível torná-las iguais tomando um oráculo forte o suficiente, não? Por exemplo,

. (A primeira classe é

com "portões QBF".)

A C 0^{P S P A C E} = P S P A C E = P S P A C E^{P S P A C E}

$AC0^{PSPACE} = PSPACE = PSPACE^{PSPACE}$

A C 0

$AC0$

Ryan Williams

@ Ryan: Eu pensei que a maneira como se define o acesso ao oráculo é importante, e se a definição não estiver correta, então coisas estranhas podem acontecer. Por exemplo, consulte este arquivo cs.toronto.edu/~sacook/homepage/rel-web.ps . (nota: não lembro que eles também discutem

) Uma máquina com mais recursos pode fazer perguntas mais complicadas do que uma mais restrita do mesmo oráculo, e é por isso que não temos um (razoável). ) relativização que tornaria DTime (n) = DTime (

), então parece-me que não é tão direto quanto você diz, é?

T C^{0}

$TC^0$

n^{2}

$n^2$

Kaveh

(hierarquia de tempo do log)

, portanto, não deve haver uma relativização razoável que faça

. Eu sinto que algo provavelmente está errado com o meu raciocínio na linha anterior, sabemos

A C^{0} = L H

$AC^0 = LH$

\subset P H \subseteq P S p a c e

$\subset PH \subseteq PSpace$

A C^{0} = P S p a c e

$AC^0 = PSpace$

L H \subset P H

$LH \subset PH$

Kaveh

Respostas:

Qualquer separação de classes fechada em "recursos polinomiais" tem um oráculo que as torna iguais. (Isso é fornecido, o mecanismo oracle é justo e permite que ambos os modelos de máquina façam consultas de comprimento polinomial e não mais.)

Seja " com portões para o oráculo ". Deixando ser uma idioma -completo sob reduções, temos , onde, no mecanismo do Oracle para $TC0^{O}$ $TC0$ $O$ $O$ $PSPACE$ $TC0$ $TC0^{O} = PSPACE = PSPACE^{O} = PP^{O}$ , contamos o uso de espaço da fita oracle junto com o restante da memória. (Portanto, apenas consultas com comprimento polinomial são solicitadas.) Essa igualdade é válida para muitas classes "fechadas sob recursos polinomiais", no sentido de que elas podem solicitar consultas com comprimento polinomial para um oráculo, mas não maiores. Essas classes incluem coisas como , , (sob um mecanismo oracle diferente que não conta consultas do oracle para o espaço vinculado), , , e $PSPACE$ $AC0$ $TC0$ $LOGSPACE$ $P$ $NP$ $PH$ . Portanto, qualquer separação de classes nesta lista deve necessariamente usar algum tipo de argumento "não relativizante". Isso também implica (por exemplo) que as provas naturais de coisas como Paridade que não estão em não são relativizantes (mas isso é ainda mais fácil: tudo o que você precisa aqui é um oráculo de paridade, para obter ) $PP$ $AC0$ $AC0[2]$

Na coleção de provas que você cita, acredito que a maioria delas (se não todas) funciona assumindo e derivando uma contradição. Esses tipos de resultados são chamados de "diagonalização indireta". Assim, uma relativização de sua prova teria que dizer: "se , então contradições ...", mas esta suposição é realmente verdade para alguns oráculos . $TC0 = PP$ $TC0^{O} = PP^{O}$ $O$

Nos comentários, destacou-se que da maneira que estou usando. Essas são apenas sutilezas com o mecanismo oracle. No lado LOGSPACE, a fita de consulta não pode fazer parte do espaço vinculado, pois as consultas têm comprimento polinomial. No lado do PSPACE, a fita de consulta é $LOGSPACE^{O} = PSPACE^{O}$ tomado como parte do espaço vinculado. Isso foi para tornar as coisas "justas". Mas se você lhes der exatamente o mesmo mecanismo de oráculo, poderá separá-los novamente por diagonalização. Por exemplo, se as consultas não contam para o espaço vinculado, no PSPACE ^ {PSPACE} você pode fazer perguntas exponencialmente longas para o PSPACE, portanto, na verdade, ele contém EXPSPACE. Peço desculpas por não ter dito isso explicitamente antes.

A computação limitada ao espaço é muito sutil em relação aos oráculos. Veja a página 5 deste artigo de Fortnow para um bom resumo de por que o oráculo e a computação limitada pelo espaço nem sempre se misturam.

Ryan Williams
fonte

Obrigado pelo comentário sobre o PSPACE ^ {PSPACE} que contém EXPSPACE no modelo que usamos para o LOGSPACE. Minha confusão foi esclarecida.

Robin Kothari

Veja também Aehlig, Cook e Nguyen, Relativizando pequenas classes de complexidade e suas teorias .

Yuval Filmus