Pytania otagowane jako space-bounded

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

2
Wymagania dotyczące pamięci dla wyboru mediany (algorytmy dwuprzebiegowe)
W klasycznej pracy Munro i Paterson badają problem ilości pamięci potrzebnej algorytmowi do znalezienia mediany w losowo posortowanej tablicy. W szczególności koncentrują się na następującym modelu: wejście jest odczytywane od lewej do prawej kilka razy P. Pokazano, że komórki pamięci są wystarczające, ale odpowiadająca dolna granica jest znana tylko dla …
1
Które wyniki sprawiają, że przestrzeń kwantowa jest interesująca?
Obliczenia kwantowe ograniczone w czasie są oczywiście bardzo interesujące. A co z obliczeniami kwantowymi ograniczonymi przestrzenią? Znam wiele interesujących wyników obliczeń kwantowych z sublogarytmicznymi granicami przestrzeni i różnego rodzaju modelami automatów kwantowych. Z drugiej strony wykazano, że probabilistyczna i kwantowa przestrzeń bez ograniczeń związanych z błędem jest równoważna dla dowolnej …
3
Wydajne algorytmy przestrzeni logów
Łatwo zauważyć, że każdy problem, który można rozstrzygnąć w deterministycznej przestrzeni logicznej ( ), pojawia się co najwyżej w czasie wielomianowym ( P ). Wiele znanych algorytmów przestrzeni logicznej (na przykład: nieukierowana łączność st, izomorfizm płaskiego wykresu) działa w O ( n k ), gdzie k jest niesamowicie duże.L.L.LP.P.PO ( …
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
Gramatyka kontekstowa dla SAT?
Według klasycznego wyniku Kurody, klasa złożoności NSPACE [ ]nnn (znana również jako NLIN-SPACE) jest właśnie klasą CSL języków kontekstowych . Problem satysfakcji SAT występuje w NSPACE [ ], ponieważ domysły o liniowym rozmiarze dla rozwiązania można sprawdzić z co najwyżej liniowym obciążeniem dla księgowości. Oznacza to, że SAT musi mieć …
1
Języki kompletne i wrażliwe na kontekst.
Interesują mnie dwa pytania dotyczące języków kontekstowych (CSL) i kompletności: Czy istnieje pojęcie kompletności CSL i które języki są kompletne? Czy istnieją naturalne CSL, które są NP-kompletne? W przypadku 2. z pewnością mogę myśleć o naturalnych językach NP-zupełnych, które są CSL (ponieważ CSL jest równy NSPACE [nnn ], SAT to …
2
Algorytmy SC ^ 2 dla łączności st
Savitch podał algorytm deterministyczny do rozwiązania łączności st przy użyciu przestrzeni , sugerując, że N L ⊆ D S P A C E ( log 2 n ) . Algorytm Savitcha działa w czasie . Poważnym otwartym problemem jest to, czy łączność st może zostać rozwiązana przez algorytm deterministyczny w …
2
Analogi kwantowe klas złożoności SPACE
Często rozważamy klasy złożoności, w których jesteśmy ograniczeni ilością miejsca, które może wykorzystać nasza maszyna Turinga, na przykład: DSPACE(f(n))DSPACE(f(n))\textbf{DSPACE}(f(n)) lub NSPACE(f(n))NSPACE(f(n))\textbf{NSPACE}(f(n)) . Wydaje się, że we wczesnej teorii złożoności odniesiono duży sukces z tymi klasami, takimi jak twierdzenie o hierarchii przestrzeni i tworzenie ważnych klas, takich jak LL\textbf{L} i PSPACEPSPACE\textbf{PSPACE} …
2
Hierarchia naprzemienna
Dzięki Immerman i Szelepcsényi wiadomo, że jeśli f = Ω ( log ) (nawet w przypadku funkcji niemożliwych do zbudowania w przestrzeni).NSPACE(f)=coNSPACE(f)NSPACE(f)=coNSPACE(f){\rm NSPACE}(f)={\rm coNSPACE}(f)f=Ω(log)f=Ω(log)f=\Omega(\log) W tym samym artykule Immerman stwierdza, że ​​naprzemienna hierarchia przestrzeni logicznej się zawala, co oznacza, że (definicja ograniczonej naprzemiennej maszyny Turinga i tego, co jest hierarchię …
1
Hierarchie czasu w DSPACE (O (s)))
Twierdzenie o hierarchii czasu stwierdza, że ​​maszyny Turinga mogą rozwiązać więcej problemów, jeśli mają (wystarczająco) więcej czasu. Czy to w jakiś sposób się utrzymuje, jeśli przestrzeń jest asymptotycznie ograniczona? Jak DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n), O(s(n))) odnosi się do DTISP(f(n),O(s(n)))DTISP(f(n),O(s(n)))\textrm{DTISP}(f(n), O(s(n))) jeśli fgfg\frac{f}{g} rośnie wystarczająco szybko? Ja szczególnie zainteresowany w przypadku, s(n)=ns(n)=ns(n) = n …
3
Jak iterować po wektorach w kolejności prawdopodobieństwa na małej przestrzeni
Rozważmy wymiarowy wektor gdzie . Dla każdego wiemy i załóżmy, że są niezależne. Wykorzystując te prawdopodobieństwa, czy istnieje skuteczny sposób na iterację binarnych wektorów wymiarowych w kolejności od najbardziej prawdopodobnego do najmniej prawdopodobnego (z dowolnymi wyborami wiązań) z wykorzystaniem przestrzeni podliniowej w wielkości wyjściowej? v v i ∈ { 0 …
2
Czy automaty wielopłytkowe mogą decydować o wszystkich deterministycznych językach kontekstowych?
MPA (automat multipebble) to 2DFA (dwukierunkowy deterministyczny automat skończony), który może wykorzystywać dowolną liczbę otoczek (w rzeczywistości najwyżej otoczki na danym wejściu - wejście jest zapisywane na taśmie między dwoma końcami -markery jak ). Podczas obliczeń MPA może wykryć, czy symbol pod głową ma kamyk, a następnie może umieścić kamyk …
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.