Duże klasy zawierające LOGSPACE, dla których ścisłe włączenia nie są znane

Strona wikipedii na PSPACE wspomina, że włączenie nie jest znane jako ścisłe (niestety bez odnośników). $NL\subset PH$

P1: Co z i - czy są one znane jako ścisłe? $L\subset PH$ $L\subset P^{\#P}$

P2: Jeśli nie, czy istnieje ustalona klasa która zawiera i dla której nie wiadomo, czy włączenie jest ścisłe? $C$ $P^{\#P}$ $L\subset C$

P3: Czy takie inkluzje są omawiane w literaturze?

cc.complexity-theory complexity-classes logspace Łukasz Grabowski
źródło

Chyba w drugim kwartale masz na myśli ściśle zawarte w PSPACE?

Sasho Nikolov

AFAIK, jedyną znaną separacją dla jest twierdzenie o hierarchii przestrzeni. Nie sądzę, aby wiadomo było, czy którakolwiek z klas wymienionych w pytaniu może symulować przestrzeń superlogarytmiczną, więc nie są one również znane jako ścisłe. (Niewiedza o separacji nie jest wynikiem, więc prawdopodobnie jest to powód, dla którego nie ma żadnych odniesień).

L

$\mathsf{L}$

Kaveh

Nawet dla mniejszych klas niż , takich jak uniform , inkluzje Q1 nie są znane jako ścisłe. Myślę, że biorąc pod uwagę obecny stan wiedzy, zasadniczo każda klasa pomiędzy i ściśle zawarta w jest pozytywną odpowiedzią na drugi kwartał.

L

$\mathsf{L}$

{N C}^{1}

$\mathsf{NC}^1$

C

$C$

P^{# P}

$\mathsf{P}^{\mathsf{\# P}}$

P S P A C E

$\mathsf{PSPACE}$

Joshua Grochow

W tytule pytania znajduje się „największa klasa”. Nie masz na myśli „najmniejszej klasy”?

Shaull

Nie wiadomo nawet, czy jest ściśle uwzględnione w PH. ściśle zawiera TC ^ 0 argumentem hierarchii, ale jak już wspomniano Joshua Grochow, nie jest to znane dla NC ^ 1. W drugim kwartale możesz wziąć CH.

A C^{0} [6]

$AC^0[6]$

P^{# P}

$P^{\#P}$

Emil Jeřábek

Odpowiedzi:

To moje ulubione pytanie.

W swojej pracy „Czasoprzestrzenne kompromisy dla satysfakcji” Fortnow wykazał , że jest właściwie zawarte w , gdzie jest dowolną nieograniczoną funkcją. Oznacza to, że niedeterministyczny obszar logu jest odpowiednio zawarty w naprzemiennym czasie wielomianowym z alternatywami. $NL$ $\Sigma_{a(n)} P$ $a(n)$ $a(n)$

że nie jest w dla stałej stałej , oznaczałoby, że . (Aby to zobaczyć, weź pod uwagę środek antykoncepcyjny.) $NL$ $\Sigma_k P$ $k$ $NL \neq NP$

Jest otwarte, czy . Ostatnim razem, gdy poważnie próbowałem to udowodnić, zaowocowało to pismem „Czasoprzestrzenne kompromisy w zakresie liczenia liczb całkowitych rozwiązań NP Modulo” . Próbowałem znaleźć jakąś symulację każdego języka w przestrzeni logów, która zajęłaby czasu na pewne ustalone gdy ktoś ma dostęp do wyroczni do zliczania satysfakcjonujących przypisań do danej formuły. (Oznaczałoby to .) Moje podejście nie zadziałało, ale ostatecznie zastosowałem to samo podejście, aby udowodnić dolne granice czasoprzestrzeni dla rozwiązania i innych powiązanych wyników. $NL = P^{\#P}$ $n^k$ $k$ $LOGSPACE \neq P^{\#P}$ $Mod_6 SAT$

Uniform- jest poprawnie zawarty w . Dowód znajduje się w Allender, „Stałe wymaga dużych jednolitych obwodów progowych” . Wszelkie ulepszenia tego rozdziału są otwarte. (Na przykład sprawdzanie jednolitości - jest otwarte, a sprawdzanie jednolitości - jest również otwarte.) $TC^0$ $P^{\#P}$ $NC^1 \neq P^{\#P}$ $TC^0 \neq NP$

Ryan Williams
źródło

Chłodny! (BTW, dotyczące ostatniego zdania nie nawiasie: Koiran i Perifel arxiv.org/abs/0902.1866 poprawiła rezultat Allender do poli-size mundurze obwody głębokości - ale myślę, że każdy poprawa na które jest otwarte).

T C

$\mathsf{TC}$

o (\log \log n)

$o(\log \log n)$

Joshua Grochów

Tak, ja też o tym wiem i innych referencjach. Ale trzymałem się podsumowującej odpowiedzi, której napisanie nie zajęłoby więcej niż 10 minut.

Ryan Williams