Pytania otagowane jako space-complexity

2
Najlepsza bieżąca dolna granica dla SAT?
Kontynuując poprzednie pytanie , jakie są najlepsze obecne dolne granice przestrzeni dla SAT? Przez spację dolną rozumiem tutaj liczbę komórek taśmy roboczej używanych przez maszynę Turinga, która używa binarnego alfabetu taśmy roboczej. Stały składnik addytywny jest nieunikniony, ponieważ TM może wykorzystywać stany wewnętrzne do symulacji dowolnej stałej liczby komórek taśmy …
3
Ile czasu rozpoznaje palindromy w przestrzeni logarytmicznej?
Dobrze wiadomo, że palindromy można rozpoznać w czasie liniowym na maszynach Turinga z taśmami, ale nie na maszynach Turinga z pojedynczą taśmą (w takim przypadku potrzebny czas jest kwadratowy). Algorytm czasu liniowego wykorzystuje kopię danych wejściowych, a zatem wykorzystuje również przestrzeń liniową.222 Czy potrafimy rozpoznać palindromy w czasie liniowym wielowarstwowej …
2
Jaka jest złożoność przestrzeni przy obliczaniu wartości własnych?
Szukam pracy ankietowej lub książki obejmującej wyniki dotyczące złożoności przestrzeni typowych operacji algebry liniowej, takich jak ranga macierzy, obliczanie wartości własnych itp. Podkreślam część „złożoności przestrzeni”, która oznacza złożoność przestrzeni pracy, a nie złożoność czasu, ponieważ łatwiej jest prześledzić wyniki czasowe. Doceniam wszelkie odniesienia w tej sprawie. Dzięki.
1
Kwadratowy związek między przestrzenią niedeterministyczną a deterministyczną?
Twierdzenie Savitcha pokazuje, że NSPACE(f(n))⊆DSPACE(f(n)2)NSPACE(f(n))⊆DSPACE(f(n)2)\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2) dla wszystkich wystarczająco dużych funkcji fff , i udowodnienie, że jest ciasno, było otwartym problemem od dziesięcioleci . Załóżmy, że podchodzimy do problemu z drugiego końca. Dla uproszczenia załóżmy logiczny alfabet. Ilość miejsca wykorzystywanego przez TM do decydowania o języku obliczeniowym jest często …
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
Czy SAT w ograniczonej szerokości jest rozstrzygalny w przestrzeni logów?
Elberfeld, Jakoby i Tantau 2010 ( ECCC TR10-062 ) dowiodły, że zajmująca mało miejsca wersja twierdzenia Bodlaendera. Wykazali, że w przypadku wykresów o szerokości co najwyżej rozkład drzewa o szerokości k można znaleźć za pomocą przestrzeni logarytmicznej. Stały współczynnik w ograniczonej przestrzeni zależy od k . (Twierdzenie Bodlaendera pokazuje liniowe …
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.