Le théorème de la hiérarchie spatiale se généralise-t-il au calcul non uniforme?

11

Question générale

Le théorème de la hiérarchie spatiale se généralise-t-il au calcul non uniforme?

Voici quelques questions plus spécifiques:

  • L/polyPSPACE/poly

  • Pour toutes les fonctions constructibles spatiales f(n) , DSPACE(o(f(n)))/polyDSPACE(f(n))/poly ?

  • Pour quelles fonctions h(n) est-il connu que: pour tout espace constructible f(n) , DSPACE(o(f(n)))/h(n)DSPACE(f(n))/h(n) ?

Michael Wehar
la source

Réponses:

7

Une "hiérarchie d'espace" non uniforme que nous pouvons prouver est une hiérarchie de taille pour les programmes de branchement . Pour une fonction booléenne , soit la taille la plus petite d'un programme de branchement calculant . Par un argument analogue à cet argument de hiérarchie pour la taille du circuit , on peut montrer qu'il y a des constantes donc pour chaque valeur , il y a une fonction telle sorte que .f:{0,1}n{0,1}B(f)fϵ,cbϵ2n/nf:{0,1}n{0,1}bcnB(f)b

Je pense que séparer de serait difficile. Cela revient à prouver que certains langages dans ont une complexité de programme de branchement super-polynomiale. Un simple argument montre que n'a pas de programme de branchement de taille polynomiale fixe :PSPACE/polyL/polyPSPACEPSPACE

Proposition. Pour chaque constante , il existe un langage sorte que pour tout suffisamment grand , . (Ici est la fonction d'indicateur pour .)kLPSPACEnB(Ln)>nkLnL{0,1}n

Preuve. Par la hiérarchie que nous avons démontrée, il existe un programme de branchement de taille qui calcule une fonction avec . Dans l' espace polynomiale, on peut itérer sur tous les programmes de la taille de branchement , tous les programmes de la taille de branchement , et toutes les entrées de longueur pour trouver un tel programme de branchement . Ensuite, nous pouvons simuler pour calculer .Pnk+1fB(f)>nknk+1nknPPf

William Hoza
la source