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

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 \to \{0, 1\}$ $B(f)$ $f$ $\epsilon, c$ $b \leq \epsilon \cdot 2^n / n$ $f: \{0, 1\}^n \to \{0, 1\}$ $b - cn \leq B(f) \leq 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 : $\mathbf{PSPACE}/\text{poly}$ $\mathbf{L}/\text{poly}$ $\mathbf{PSPACE}$ $\mathbf{PSPACE}$

Proposition. Pour chaque constante , il existe un langage sorte que pour tout suffisamment grand , . (Ici est la fonction d'indicateur pour .) $k$ $L \in \mathbf{PSPACE}$ $n$ $B(L_n) > n^k$ $L_n$ $L \cap \{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 . $P$ $n^{k + 1}$ $f$ $B(f) > n^k$ $n^{k + 1}$ $n^k$ $n$ $P$ $P$ $f$

William Hoza
la source

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

Réponses: