Czy twierdzenie o hierarchii przestrzeni generalizuje się do obliczeń niejednorodnych?

Jedną z niejednorodnych „hierarchii przestrzeni”, którą możemy udowodnić, jest hierarchia rozmiarów programów rozgałęziających . W przypadku funkcji boolowskiej , niech oznacza najmniejszy rozmiar programu rozgałęziającego obliczającego . Za pomocą argumentu analogicznego do tego argumentu hierarchii wielkości obwodu można pokazać, że istnieją stałe więc dla każdej wartości istnieje funkcja tak, że . $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$

Myślę, że oddzielenie od byłoby trudne. Jest to równoważne z udowodnieniem, że jakiś język w ma złożoność wielomianowego programu rozgałęziającego. Prosty argument pokazuje, że nie ma ustalonych programów rozgałęziających o rozmiarze wielomianowym: $\mathbf{PSPACE}/\text{poly}$ $\mathbf{L}/\text{poly}$ $\mathbf{PSPACE}$ $\mathbf{PSPACE}$

Propozycja. Dla każdej stałej istnieje język więc dla wszystkich wystarczająco dużych , . (Tutaj jest funkcją wskaźnika dla .) $k$ $L \in \mathbf{PSPACE}$ $n$ $B(L_n) > n^k$ $L_n$ $L \cap \{0, 1\}^n$

Dowód. Zgodnie z udowodnioną przez nas hierarchią istnieje program rozgałęziający o rozmiarze który oblicza funkcję pomocą . W wielomianu przestrzeni, możemy iteracyjne nad wszystkie programy rozgałęzienia wielkości , wszystkie programy rozgałęzienia wielkości , a wszystkie wejścia o długości , aby znaleźć taki rozgałęzienia programu . Następnie możemy symulować aby obliczyć . $P$ $n^{k + 1}$ $f$ $B(f) > n^k$ $n^{k + 1}$ $n^k$ $n$ $P$ $P$ $f$

William Hoza
źródło

Czy twierdzenie o hierarchii przestrzeni generalizuje się do obliczeń niejednorodnych?

Odpowiedzi: