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

Pytanie ogólne

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

Oto kilka bardziej szczegółowych pytań:

$L/poly \subsetneq PSPACE/poly$
Czy dla wszystkich funkcji zbudowania w przestrzeni $f(n)$ jest $DSPACE(o(f(n)))/poly \subsetneq DSPACE(f(n))/poly$ ?
Dla jakich funkcji $h(n)$ wiadomo, że: dla wszystkich do zbudowania przestrzeni $f(n)$ , $DSPACE(o(f(n)))/h(n) \subsetneq DSPACE(f(n))/h(n)$ ?

— Michael Wehar
źródło

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