Teoria złożoności strukturalnej
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(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Wiadomo również, że...
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....
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...
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...
Nie wiadomo, czy izomorfizm wykres (GI) do silnie graf regularny (SRGs) jest P . Czy są jakieś wskazówki, że może, ale nie musi, być GI -Complete? Czy w takich przypadkach są jakieś poważne konsekwencje? (Podobne do przekonania, że oznaczenie geograficzne może nie być
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...
Dwa dokumenty, które chciałbym załączyć to: D. Kozen, „Indeksowanie klas subrekursywnych” , STOC, 1978. R. Ladner, „O strukturze wielomianowej redukcji czasu” , JACM,
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...
Gęstość języka jest funkcją zdefiniowano jako Załóżmy, i są to języki na pewną skończoną alfabetu wielu jeden logspace redukuje się do , a jest w . Funkcje są wielomianowo powiązane, jeśli istnieją wielomiany i takie, że dla wszystkich , id X : N → N d X ( n ) = | { x ∈ X ∣ | x | ≤ n } | . A B A B...
Czy oznacza ?E = N EE X P = N E X PmiXP.=N.miXP.\mathsf{EXP}=\mathsf{NEXP}E = N
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...