Verallgemeinert sich der Satz der Raumhierarchie auf ungleichmäßige Berechnungen?

Eine ungleichmäßige "Raumhierarchie", die wir beweisen können, ist eine Größenhierarchie für Verzweigungsprogramme . Für eine Boolesche Funktion bezeichne die kleinste Größe eines Verzweigungsprogramms, das berechnet . Durch ein Argument analog zu diesem Hierarchieargument für die Schaltungsgröße kann gezeigt werden, dass es Konstanten Für jeden Wert gibt es eine Funktion so dass . $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$

Ich denke, es wäre schwierig , von zu trennen. Dies entspricht dem Nachweis, dass eine Sprache in eine superpolynomielle Verzweigungsprogrammkomplexität aufweist. Ein einfaches Argument zeigt, dass keine Verzweigungsprogramme mit fester Polynomgröße hat: $\mathbf{PSPACE}/\text{poly}$ $\mathbf{L}/\text{poly}$ $\mathbf{PSPACE}$ $\mathbf{PSPACE}$

Vorschlag. Für jede Konstante , gibt es eine Sprache so daß für alle ausreichend großen , . (Hier ist die Indikatorfunktion für .) $k$ $L \in \mathbf{PSPACE}$ $n$ $B(L_n) > n^k$ $L_n$ $L \cap \{0, 1\}^n$

Beweis. Durch die von uns bewiesene Hierarchie gibt es ein Verzweigungsprogramm der Größe , das eine Funktion mit berechnet . Im Polynomraum können wir alle Verzweigungsprogramme der Größe , alle Verzweigungsprogramme der Größe und alle Eingaben der Länge , um ein solches Verzweigungsprogramm . Dann können wir simulieren , um zu berechnen . $P$ $n^{k + 1}$ $f$ $B(f) > n^k$ $n^{k + 1}$ $n^k$ $n$ $P$ $P$ $f$

William Hoza
quelle

Verallgemeinert sich der Satz der Raumhierarchie auf ungleichmäßige Berechnungen?

Antworten: