Pytania otagowane jako space-bounded

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

4
Dlaczego traktujemy log-space jako model wydajnego obliczania (zamiast polilog-space)?
To może być pytanie subiektywne, a nie konkretne, ale tak czy inaczej. W teorii złożoności badamy pojęcie wydajnych obliczeń. Istnieją klasy takie jak oznacza czas wielomianowy , a L oznacza miejsce na log . Oba są uważane za reprezentowane jako rodzaj „wydajności” i dość dobrze wychwytują trudności niektórych problemów.PP\mathsf{P}LL\mathsf{L} Istnieje …
1
Czy LOGLOG = NLOGLOG?
Zdefiniuj LOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (loglog n) przez deterministyczną maszynę Turinga (z dwukierunkowym dostępem do danych wejściowych). Podobnie zdefiniuj NLOGLOG jako klasę języków, które mogą być obliczane w przestrzeni O (log log n) przez niedeterministyczną maszynę Turinga (z dwukierunkowym dostępem do danych wejściowych). …
2
Ciasne dolne granice twierdzenia Savitcha
Przede wszystkim z góry przepraszam za wszelką głupotę. W żadnym wypadku nie jestem ekspertem od teorii złożoności (a nawet daleko! Jestem studentem, który bierze moją pierwszą klasę z teorii złożoności). Oto moje pytanie. Teraz Twierdzenie Savitcha stwierdza, że Teraz jestem ciekawy, czy ta dolna granica była ścisła, tj. Czy jest …
3
Problemy pośrednie między L i NL
Jest dobrze wiadomo, że skierowane st-łączność jest -Complete. Przełom wynik Reingold wykazała, że nieukierunkowane st-łączność jest w L . Płaskie skierowane st-łączności jest znany w U L ∩ C O U L . Cho Huynh zdefiniowano sparametryzowanego problemu plecakowego i wykazywał hierarchię problemów między L i N l .NLNLNLLLLUL∩coULUL∩coULUL \cap …
1
Algorytmy przestrzeni logów na wykresach z ograniczoną szerokością drzewa
Szerokość drzewa mierzy, jak blisko wykresu znajduje się drzewo. Trudno jest obliczyć szerokość drzewa. Najbardziej znany algorytm aproksymacyjny osiąga współczynnik .O ( log n----√)O(logn)O(\sqrt{{\log}n}) Twierdzenie Courcelle'a stwierdza, że dowolną właściwość grafów definiowalną w monadycznej logice drugiego rzędu (MSO2) można rozstrzygać w czasie liniowym na dowolnej klasie wykresów o ograniczonej szerokości …
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 …
1
Czy można rozpoznać w wieloskładnikowej probabilistycznej przestrzeni sublogarytmicznej?
Zastanów się nad językiem .EQUALITY={anbn∣n≥0}EQUALITY={anbn∣n≥0} \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} Wiadomo, że nie może zostać rozpoznany przez żadną maszynę Turinga (ATM) na przemian z przestrzenią sublogarytmiczną (Szepietowski, 1994) . (Istnieje bankomat wykorzystujący przestrzeń sublogarytmiczną dla członków, ale nie dla wszystkich osób niebędących członkami!)EQUALITYEQUALITY \mathtt{EQUALITY} Z drugiej …
3
kosmiczne bazy TM i wyrocznie
Zasadniczo taśma zapytania dla wyroczni liczy się do złożoności przestrzennej bazy TM. Wydaje się jednak prawdopodobne, aby zezwolić na taśmę Oracle tylko do zapisu (na przykład w przypadku redukcji przestrzeni L). Czy taka konstrukcja jest przydatna? Czy przynosi jakieś absurdalne wyniki?
3
Analiza CFG przy użyciu spacji
Istnieje wiele algorytmów, które mogą analizować gramatykę bezkontekstową w czasie . Używając mnożenia macierzy, można nawet iść asymptotycznie szybciej.O(n3)O(n3)O(n^3) Jednak wszystkie algorytmy do analizy dowolnych CFG, które znam, mają najgorsze wykorzystanie przestrzeni (chociaż, co prawda, nie mam pojęcia, jakie jest użycie przestrzeni przez ten algorytm mnożenia macierzy). Zastanawiałem się, czy …
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.