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...
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...
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...
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...
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 czasie...
O ( log i n ) S A C i i ≥ 1 S A C 0 S A C 1 = L o g C F LSACiSACiSAC^i jest klasą problemów decyzyjnych rozwiązanych przez rodzinę obwodów głębinowych z nieograniczoną liczbą Fanin OR i ograniczonymi bramkami Fanin AND. Negacje są dozwolone tylko na poziomie wejściowym. Wiadomo, że dla jest...
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...
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...
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...
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)))...
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ą...
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...
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...
Pokaż funkcję którą można konstruować w przestrzeni, ale nie można jej konstruować w czasie.f(n)fa(n)f(n) Czy ten problem jest związany z możliwym rozdzieleniem klas złożoności DTIME (f (n)) i SPACJA (f
Dobrze wiadomo, że NP-Complete Problem o nazwie Subset Sum ma FPTAS. Zastanawiałem się, czy istnieje problem z PSPACE Complete, który ma także FPTAS? Z góry
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...