Pytania otagowane jako structural-complexity

Teoria złożoności strukturalnej

4
Jakie są konsekwencje
Wiemy, że L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} i że L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , gdzie L2=DSPACE(log2n)L2=DSPACE(log2⁡n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Wiadomo również, że polyL≠PpolyL≠P\mathsf{polyL} \neq \mathsf{P}ponieważ ten drugi ma całkowite problemy w przestrzeni logarytmicznej, wielokrotne redukcje jeden-jedynki, podczas gdy ten drugi nie (ze względu na twierdzenie o …
1
Algorytmy i teoria złożoności strukturalnej
Wiele ważnych wyników w teorii złożoności obliczeniowej, a zwłaszcza teoria złożoności „strukturalnej”, ma interesującą właściwość, którą można rozumieć jako zasadniczo wynikającą (jak widzę ...) z wyników algorytmicznych, dającą skuteczny algorytm lub protokół komunikacyjny dla niektórych problem. Należą do nich: IP = PSPACE wynika z wydajnego przestrzennie algorytmu rekurencyjnego symulującego interaktywne …
1
Jaka jest wyrocznia o minimalnej złożoności, która oddziela PSPACE od hierarchii wielomianowej?
tło Wiadomo, że istnieje oracle tak, że .P S P A C E A ≠ P H AAAAPSPACEA≠PHAPSPACEA≠PHAPSPACE^A \neq PH^A Wiadomo nawet, że separacja dotyczy przypadkowej wyroczni. Nieformalnie można to interpretować w ten sposób, że istnieje wiele wyroczni, dla których i są osobne.P HPSPACEPSPACEPSPACEPHPHPH Pytanie Jak skomplikowane są te wyrocznie, …
3
Jak trudna jest dokładna symulacja algorytmów i powiązana z nią operacja na klasach złożoności
Zwiastun Ponieważ problem jest długotrwały, tutaj jest szczególny przypadek, który oddaje jego istotę. Problem: Niech A będzie algorytmem detrministycznym dla 3-SAT. Czy problem polega na całkowitej symulacji algorytmu A (na każdym wystąpieniu problemu). P-Space trudne? (Dokładniej, czy istnieją powody, by sądzić, że to zadanie jest trudne dla P-Space, robi coś …
1
vs
W naszej ostatniej pracy rozwiązujemy problem obliczeniowy, który powstał w kontekście kombinatorycznym, przy założeniu, że , gdzie to -wersja . Jedyny artykuł na temat , który znaleźliśmy, to artykuł Beigel-Buhrman-Fortnow 1998 , cytowany w Zoo Complexity . Rozumiemy, że możemy wziąć wersje parzystości problemy (zobacz to pytanie ), ale być …
2
Nadzbiór wieloczęściowy NP kompletnego języka z nieskończenie wieloma ciągami wyłączonymi z niego
Czy dla dowolnego arbitralnego NP pełnego języka zawsze istnieje nadzbiór czasu policyjnego, którego dopełnienie jest również nieskończone? Na stronie /cs//q/50123/42961 poproszono o trywialną wersję, która nie przewiduje, że nadzbiór ma nieskończone uzupełnienie. Dla celów tej kwestii, można przyjąć, że . Jak wyjaśnił Vor, jeśli wówczas odpowiedź brzmi „Nie”. (Jeśli , …
1
Mogą
Pozwolić ATISP(f(n),g(n))ATISP(f(n),g(n))\mathsf{ATISP}(f(n), g(n)) być klasą języków ustaloną przez naprzemienne maszyny Turinga, które zatrzymują się w czasie f(n)f(n)f(n) używając przestrzeni g(n)g(n)g(n). PozwolićAALTSP(f(n),g(n))AALTSP(f(n),g(n))\mathsf{AALTSP}(f(n), g(n)) być klasą języków ustaloną przez naprzemienne używanie maszyn Turinga f(n)f(n)f(n) alternacje i przestrzeń g(n)g(n)g(n). Ruzzo udowodnił , żeNCk=ATISP(logkn,logn)NCk=ATISP(logk⁡n,log⁡n)\mathsf{NC}^k = \mathsf{ATISP}(\log^k n, \log n). On też to pokazałNCk⊆AALTSP(logkn,logn)⊆NCk+1NCk⊆AALTSP(logk⁡n,log⁡n)⊆NCk+1\mathsf{NC}^k \subseteq …
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.