Pytania oznaczone «space-bounded»

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ą...

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...

Łączność ST to problem polegający na określeniu, czy istnieje ukierunkowana ścieżka między dwoma wyróżnionymi wierzchołkami i t na ukierunkowanym wykresie G ( V , E ) . To, czy problem ten można rozwiązać w przestrzeni logów, jest od dawna otwartym problemem. Jest to tak zwany N l vs L...

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...

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...

Oczywiste jest, że każdy problem, który można rozstrzygnąć w deterministycznej przestrzeni logów ( ), występuje co najwyżej w czasie wielomianowym ( ). Tam jest wiele klas złożoności między i . Przykłady obejmują , , , , , . Uważa się, że .P L P N L L o g C F L N C i S A C i A C i S C i L ≠...

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...

Zastanawiam się, czy jest jakieś uzasadnienie, by wierzyć, że czy wierzyć, że N L ≠ L ?NL=LNL=LNL=LNL≠LNL≠LNL\neq L Wiadomo, że . W literaturze derandomization z R L jest dość przekonanie, że R, L = L . Czy ktoś wie o niektórych artykułach lub pomysłach przekonujących, że N L ≠ L ?NL⊂L2NL⊂L2NL...

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...

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ń...

Immerman i Szelepcsenyi niezależnie okazało się, że . Stosując technikę zliczania indukcyjnego, Borodin i wsp. Udowodnili, że S A C i jest zamknięte pod komplementarnością dla i > 0 . Przed twierdzeniem Reingolda ( S L = L ) Nisan i Ta-Shma udowodnili S L = c o S L , stosując redukcje...

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...

USTCONN to problem, który wymaga podjęcia decyzji, czy istnieje ścieżka od wierzchołka źródłowego sss do wierzchołka docelowego ttt na wykresie GGG , gdzie wszystkie są podane jako część danych wejściowych. Omer Reingold wykazał, że USTCONN znajduje się w L (doi: 10.1145 / 1391289.1391291 ). Dowód...

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ą...

Ostatnio Watrous i wsp. Udowodnili, że QIP (3) = PSPACE to niezwykły wynik. Był to dla mnie zaskakujący wynik, co wywołało u mnie myśl ... Zastanawiałem się, czy komputery kwantowe mogłyby być skutecznie symulowane przez komputery klasyczne. Czy może to być PO PROSTU związane z podziałem między IP...

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,...

Mówi się, że rozkład ϵ -fooluje funkcję f if | E x ∈ U ( f ( x ) ) - E x ∈ D ( f ( x ) ) | ≤ ϵ . Mówi się, że oszuka klasę funkcji, jeśli oszuka każdą funkcję w tej klasie. Wiadomym jest, że ε -biased obowiązuje oszukać klasę parytetów nad podzbiorów. (patrz...

Ł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 ),...

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...

Nisan udowodnił w „Psuedorandom Generators for Compound-Bounded Computation”, że istnieje pseudolosowy generator, który „oszuka” obliczenia ograniczone w przestrzeni. Czy ta konstrukcja obowiązuje dla każdej wyroczni (przynajmniej w przypadku zapytań