Pytania otagowane jako space-bounded

Pytania o zasoby przestrzenne obliczeń w złożoności obliczeniowej lub algorytmach.

1
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⊊PSPACE/polyL/poly⊊PSPACE/polyL/poly \subsetneq PSPACE/poly Czy dla wszystkich funkcji f (n) możliwych do zbudowania w przestrzeni f(n)f(n)f(n)jest DSPACE(o(f(n)))/poly⊊DSPACE(f(n))/polyDSPACE(o(f(n)))/poly⊊DSPACE(f(n))/polyDSPACE(o(f(n)))/poly \subsetneq DSPACE(f(n))/poly ? Dla jakich funkcji h(n)h(n)h(n) wiadomo, że: dla wszystkich możliwych do zbudowania przestrzeni f(n)f(n)f(n) , …
1
Złożoność przestrzeni dla średnich przypadków
Próbuję znaleźć problemy, których złożoność przestrzeni dla średnich przypadków została przeanalizowana. Mówiąc dokładniej, jestem zainteresowany, aby dowiedzieć się, czy są jakieś problemy ze sprawdzoną dolną granicą złożoności przestrzeni, która jest superliniowa, a zwłaszcza, jeśli istnieją jakieś z analizą średnich przypadków (np. Granica jest zachowana, nawet jeśli algorytm jest dozwolony błądzić …
2
Czy niedeterministyczne automaty do chodzenia po drzewie są silniejsze niż te deterministyczne?
Aktualizacja: Wygląda na to, że ten problem został niedawno zbadany i rozwiązany, zobacz ten artykuł wiki: http://en.wikipedia.org/wiki/Tree_walking_automaton A także tę ankietę: http://www.mimuw.edu.pl/~bojan /papers/twasurvey.pdf Załóżmy, że zamiast zwykłego zestawu słów {0,1} *, nasze słowa nie są liniowe, ale raczej podane na jakiejś strukturze drzewa. Aby zapobiec „zagubieniu się” naszych maszyn, zdefiniuj …
1
Czy niedeterministyczne liniowe automaty z ograniczoną liczbą odwiedzin rozpoznają tylko zwykłe języki?
Czy niedeterministyczne liniowe automaty z ograniczoną liczbą odwiedzin rozpoznają tylko zwykłe języki? Przez niedeterministyczny automat związany liniowo (nLBA) mam na myśli niedeterministyczną maszynę Turinga z pojedynczą taśmą, w której dane wejściowe są „wyściełane” znakami końcowymi na obu końcach, których nigdy nie można nadpisać, a więc głowa nigdy nie może wyjść …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.