Hiérarchie pour BPP vs dérandomisation

29

En une phrase: l'existence d'une hiérarchie pour impliquerait-elle des résultats de dérandomisation?BPTIME

Une question connexe mais plus vague est: l'existence d'une hiérarchie pour implique-t-elle des limites inférieures difficiles? La résolution de ce problème heurte-t-elle une barrière connue dans la théorie de la complexité?BPTIME

Ma motivation pour cette question est de comprendre la difficulté relative (par rapport à d' autres grands problèmes ouverts dans la théorie de la complexité) de montrer une hiérarchie pour . Je suppose que tout le monde croit qu'une telle hiérarchie existe, mais veuillez me corriger si vous pensez le contraire.BPTIME

Quelques informations de base : contient les langues dont l'appartenance peut être décidée par une machine de tournage probabiliste dans le temps f ( n ) avec une probabilité d'erreur limitée. Plus précisément, un langage L B P T I M E ( f ( n ) ) s'il existe une machine de Turing probabiliste T telle que pour tout x L la machine TBPTIME(f(n))f(n)LBPTIME(f(n))TxLTexécute en temps et accepte avec une probabilité d' au moins deux / trois , et pour tout x L , T fonctionne en temps O ( f ( | x | ) ) et rejette avec une probabilité d' au moins 2 / 3 .O(f(|x|))2/3xLTO(f(|x|))2/3

Inconditionnellement, il est ouvert que pour tout c > 1 . Barak a montré qu'il existe une hiérarchie stricte pour B P T I M E pour les machines avec O ( log n )BPTIME(nc)BPTIME(n)c>1BPTIMEO(logn)Conseil. Fortnow et Santhanam ont amélioré cela à 1 bit de conseils. Cela m'amène à penser qu'une preuve de l'existence d'une hiérarchie temporelle probabiliste n'est pas si loin. En revanche, le résultat est toujours ouvert et je ne trouve aucun progrès après 2004. Les références, comme d'habitude, se trouvent dans le Zoo .

La relation à la dérandomisation provient des résultats d'Impagliazzo et Wigderson: ils ont montré que sous une hypothèse de complexité plausible, pour toute constante d et une constante c . D'après les théorèmes classiques de la hiérarchie du temps pour le temps déterministe, cela implique une hiérarchie du temps pour le temps probabiliste. Je pose la question inverse: une recherche probabiliste heurte-t-elle une barrière liée à la preuve des résultats de la dérandomisation?BPTIME(nd)DTIME(nc)dc


EDIT: J'accepte la réponse de Ryan comme une solution plus complète.

Si quelqu'un a des observations sur ce qui nous sépare et prouve l'existence d'une hiérarchie pour le temps probabiliste, n'hésitez pas à répondre / commenter. Bien sûr, la réponse évidente est que a une définition sémantique qui défie les techniques classiques. Je suis intéressé par des observations moins évidentes.BPTIME

Sasho Nikolov
la source

Réponses:

22

Soit PTH l'hypothèse qu'il existe une hiérarchie temporelle probabiliste. Supposons que la réponse à votre question soit vraie, c'est-à-dire, "PTH implique " pour certains c fixes . Alors, E X P B P P serait inconditionnellement vrai. Considérons deux cas:BPPTIME[2nc]cEXPBPP

  • Si PTH est faux, alors . C'est la contradiction de ce que Lance a noté.EXPBPP
  • Si PTH est vrai, "PTH implique " à nouveau E X P B P P .BPPTIME[2nc]EXPBPP

En fait, même une dérandomisation infiniment fréquente du BPP sous PTH entraînerait sans condition. Donc, quelles que soient les barrières qui s'appliquent à la preuve de E X P B P P , elles s'appliquent aux déclarations de preuve du type "PTH implique une dérandomisation".EXPBPPEXPBPP

Ryan Williams
la source
3
Agréable. Il existe donc une forte barrière contre la démonstration de l'existence d'une barrière liée à la dérandomisation pour prouver la PTH.
Sasho Nikolov
18

Il n'est pas difficile de dériver une hiérarchie temporelle probabiliste si BPP = EXP, le cas extrême de non-dérandomisation.

Lance Fortnow
la source
2
Et vous n'avez pas besoin de BPP = EXP, vous avez juste besoin de BPP pas en DTIME (2 ^ {n ^ c)}) pour une constante c> 1. Autrement dit, vous avez seulement besoin que BPP soit difficile pour DTIME, pas que BPP peut résoudre des langues E-complètes. Cela signifie que le manque extrême de dérandomisation implique une hiérarchie. Qu'en est-il du manque intermédiaire de dérandomisation?
Jeff KInne
Bonnes observations. Ainsi, un effondrement est tout aussi bon qu'un effondrement pour établir une hiérarchie. Cela mine ma motivation, mais, techniquement parlant, n'est-il pas encore possible qu'une hiérarchie probabiliste implique une dérandomisation, même si le manque de dérandomisation implique une hiérarchie probabiliste (une fausse déclaration peut impliquer une vraie déclaration)? La question plus vague sur les obstacles auxquels le problème de la hiérarchie BPP se heurte est toujours d'actualité. Par exemple, il est possible que BPP ait une hiérarchie pour tous les oracles (la question non résolue de Fortnow-Sipser'89), donc la relativisation n'est pas un problème de toute façon?
Sasho Nikolov