Les preuves que le permanent n'est pas en uniforme

Ceci fait suite à cette question et est lié à cette question de Shiva Kinali.

Il semble que les preuves dans ces articles ( Allender , Caussinus-McKenzie-Therien-Vollmer , Koiran-Perifel ) utilisent des théorèmes de hiérarchie. Je veux savoir si les preuves sont des théorèmes de diagonalisation " purs ", ou s'ils utilisent quelque chose de plus que la diagonalisation habituelle. Donc ma question est

y a-t-il une relativisation raisonnable qui met permanent en uniforme ? $\mathsf{TC^0}$

Notez que je ne sais pas comment définir l'accès oracle pour uniforme , je sais que trouver la définition correcte pour les petites classes de complexité n'est pas trivial. Une autre possibilité est que le permanent n'est pas complet pour dans l'univers relativisé, auquel cas je devrais utiliser un problème complet pour dans l'univers relativisé à sa place, et je pense que devrait avoir un problème complet de toute façon raisonnable univers relativisé. $\mathsf{TC^0}$ $\mathsf{\#P}$ $\mathsf{\#P}$ $\mathsf{\#P}$

cc.complexity-theory lower-bounds relativization permanent Kaveh
la source

Comment définissez-vous une version relativisée du permanent? Ou cherchez-vous un monde relativisé où PP⊆TC ^ 0?

Tsuyoshi Ito

@Tsuyoshi: Le problème est que je ne suis pas sûr de la preuve complète pour être permanent

. Il me semble que la preuve que le permanent n'est pas en uniforme

fonctionne aussi pour tout autre problème complet. Une relativisation raisonnable qui met

intérieur de

répondrait à ma question.

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

Je ne sais pas trop ce que vous entendez par relativisation "raisonnable". Pour deux classes de complexité, on peut les rendre égales en prenant un oracle assez fort, non? Exemples

. (La première classe est

avec "portes 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: Je pensais que la façon dont on définit l'accès à l'oracle est importante, et si la définition n'est pas correcte, des choses étranges peuvent se produire. Par exemple, consultez ce cs.toronto.edu/~sacook/homepage/rel-web.ps . (note: je ne me souviens pas qu'ils discutent également de

) Une machine avec plus de ressources peut poser des questions plus compliquées qu'une machine plus restreinte du même oracle et c'est la raison pour laquelle nous n'avons pas de (raisonnable ) relativisation qui ferait DTime (n) = DTime (

), il me semble donc que ce n'est pas aussi simple que vous le dites, n'est-ce pas?

T C^{0}

$TC^0$

n^{2}

$n^2$

Kaveh

(hiérarchie des temps logarithmiques)

, donc il ne devrait pas y avoir de relativisation raisonnable qui ferait

. Je pense que quelque chose ne va probablement pas avec mon raisonnement dans la ligne précédente, connaissons-nous

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

Réponses:

Toute séparation des classes fermées sous "ressources polynomiales" a un oracle qui les rend égales. (Ceci est fourni à condition que le mécanisme Oracle soit juste et permette aux deux modèles de machine de faire des requêtes de longueur polynomiale et pas plus.)

Soit " avec portes pour l'oracle ". Soit une langue -complète sous réductions , nous avons $TC0^{O}$ $TC0$ $O$ $O$ $PSPACE$ $TC0$ , où dans le mécanisme oracle pour $TC0^{O} = PSPACE = PSPACE^{O} = PP^{O}$ $PSPACE$ , nous comptons l'utilisation de l'espace de la bande oracle avec le reste de la mémoire. (Donc, seules les requêtes de longueur polynomiale sont posées.) Une telle égalité est valable pour de nombreuses classes "fermées sous des ressources polynomiales", dans le sens où elles peuvent demander des requêtes de longueur polynomiale à un oracle, mais pas plus. Ces classes comprennent des trucs comme , $AC0$ , (sous un mécanisme oracle différent qui ne compte pas les requêtes oracle vers l'espace), , , et $TC0$ $LOGSPACE$ $P$ $NP$ $PH$ . Ainsi, toute séparation de classes dans cette liste doit nécessairement utiliser une sorte d'argument "non relativisant". Cela implique également (par exemple) que les preuves naturelles de choses comme la parité non dans sont pas relativisantes (mais c'est encore plus facile: tout ce dont vous avez besoin ici est un oracle pour la parité, donc vous obtenez ). $PP$ $AC0$ $AC0[2]$

Dans la collection de preuves que vous citez, je pense que la plupart d'entre elles (sinon toutes) fonctionnent en supposant et en dérivant une contradiction. Ces types de résultats sont appelés "diagonalisation indirecte". Ainsi , une relativisation de leur preuve aurait à dire: « si , alors la contradiction ... » , mais cette hypothèse est en fait vrai pour certains oracles . $TC0 = PP$ $TC0^{O} = PP^{O}$ $O$

Dans les commentaires, il a été souligné que dans la façon dont je l'utilise. Ce ne sont que des subtilités avec le mécanisme oracle. Côté LOGSPACE, la bande de requête ne peut pas faire partie de l'espace lié, car les requêtes sont de longueur polynomiale. Côté PSPACE, la bande de requête est $LOGSPACE^{O} = PSPACE^{O}$ pris dans le cadre de l'espace lié. C'était pour rendre les choses "justes". Mais si vous leur donnez exactement le même mécanisme oracle, vous pouvez en effet les séparer à nouveau par diagonalisation. Par exemple, si les requêtes ne comptent pas dans l'espace, alors dans PSPACE ^ {PSPACE} vous pouvez poser des questions exponentiellement longues à PSPACE, donc cela contient en fait EXPSPACE. Je m'excuse de ne pas l'avoir dit explicitement plus tôt.

Le calcul limité dans l'espace est très subtil en ce qui concerne les oracles. Reportez-vous à la page 5 de cet article de Fortnow pour un bon résumé des raisons pour lesquelles le calcul Oracle et l'espace ne se mélangent pas toujours.

Ryan Williams
la source

Merci pour le commentaire sur PSPACE ^ {PSPACE} contenant EXPSPACE dans le modèle que nous avons utilisé pour LOGSPACE. Ma confusion a été dissipée.

Robin Kothari

Voir aussi Aehlig, Cook et Nguyen, Relativiser les petites classes de complexité et leurs théories .

Yuval Filmus