Konsekwencje NC = P?

Zoo złożoności wskazuje we wpisie na EXP, że jeśli L = P, to PSPACE = EXP. Ponieważ NPSPACE = PSPACE autorstwa Savitcha, o ile mogę powiedzieć, podstawowy argument dopełniania rozszerza się, aby pokazać, że Wiemy również, że L NL NC P poprzez zmienną hierarchię ograniczoną zasobami Ruzzo.

(NL = P) \Rightarrow (PSPACE = EXP) .

$(\text{NL} = \text{P}) \Rightarrow (\text{PSPACE} = \text{EXP}).$

\subseteq

$\subseteq$

\subseteq

$\subseteq$

\subseteq

$\subseteq$

Jeśli NC = P, czy wynika z tego, że PSPACE = EXP?

Inna interpretacja pytania, w duchu Richarda Liptona: czy bardziej prawdopodobne jest, że niektóre problemy w P nie mogą być zrównoleglone, niż że żadna procedura wykładnicza nie wymaga więcej niż przestrzeni wielomianowej?

Byłbym także zainteresowany innymi „zaskakującymi” konsekwencjami NC = P (im bardziej mało prawdopodobne, tym lepiej).

Edycja: odpowiedź Ryana prowadzi do kolejnego pytania: jaka jest najsłabsza hipoteza, o której wiadomo, że gwarantuje PSPACE = EXP?

W. Savitch. Związki między niedeterministycznymi i deterministycznymi złożonościami taśm, Journal of Computer and System Sciences 4 (2): 177-192, 1970.
WL Ruzzo. O jednolitej złożoności obwodu, Journal of Computer and System Sciences 22 (3): 365-383, 1971.

Edycja (2014): zaktualizowano stary link do Zoo i dodano linki do wszystkich innych klas.

cc.complexity-theory conditional-results András Salamon
źródło

Ponieważ jestem pewien, że nie jestem jedynym, który nie wie, co to jest NC, oto link: en.wikipedia.org/wiki/NC_%28complexity%29

Emil

@Andras: Inną konsekwencją który może wiesz już, ale nie został jeszcze wspomnieć, że jest to

N C

$\mathsf{NC}$ hierarchia upadnie, ponieważ

P

$\mathsf{P}$ ma pełną problemów pod

L

$\mathsf{L}$ -reductions .

Joshua Grochow,

Odpowiedzi:

Tak. można postrzegać jako klasę języków rozpoznawanych przez naprzemienne maszyny Turinga, które wykorzystują przestrzeń i . (Zostało to po raz pierwszy udowodnione przez Ruzzo.) to klasa, w której naprzemienne maszyny Turinga używają przestrzeni ale mogą zająć nawet czasu. Dla zwięzłości nazwijmy tych klas i . $NC$ $O(\log n)$ $(\log n)^{O(1)}$ $P$ $O(\log n)$ $n^{O(1)}$ $ATISP[(\log n)^{O(1)},\log n] = NC$ $ASPACE[O(\log n)] = P$

Załóżmy, że dwie klasy są równe. Zastępując o w powyżej (tj stosujących standardowe tłumaczenie lematy), otrzymuje się $n$ $2^n$

$TIME[2^{O(n)}] = ASPACE[O(n)] = ATISP[n^{O(1)}, n] \subseteq ATIME[n^{O(1)}] = PSPACE$ .

Jeśli to także , ponieważ w znajdują się języki pełne . $TIME[2^{O(n)}] \subseteq PSPACE$ $EXP = PSPACE$ $EXP$ $TIME[2^{O(n)}]$

Edycja: Chociaż powyższa odpowiedź może być bardziej edukacyjna, oto prostszy argument: już wynika z „ jest zawarty w przestrzeni polilogu” i standardowego tłumaczenia. Uwaga „ zawarty jest w polylog przestrzeni” jest znacznie słabszy niż hipoteza . $EXP = PSPACE$ $P$ $P$ $NC = P$

Więcej szczegółów: Ponieważ rodziny obwodów mają głębokość dla pewnej stałej, każdą taką rodzinę obwodów można ocenić w przestrzeni . Stąd . Zatem oznacza . Stosując tłumaczenie (zastępując o ) oznacza . Istnienie języka pełnego w kończy argument. $NC$ $(\log n)^c$ $O((\log n)^c)$ $NC \subseteq \bigcup_{c > 0} SPACE[(\log n)^c]$ $P = NC$ $P \subseteq \bigcup_{c > 0} SPACE[(\log n)^c]$ $n$ $2^n$ $TIME[2^{O(n)}] \subseteq PSPACE$ $EXP$ $TIME[2^{O(n)}]$

Aktualizacja: Odpowiadając na dodatkowe pytanie Andreasa, uważam, że powinno być możliwe udowodnienie czegoś w rodzaju: iff dla wszystkich , każdy wielomierzo rzadki język w czas można rozwiązać w przestrzeni polilogu. (Bycie wielomianem rzadkim oznacza, że w języku występują najwyżej łańcuchy dla wszystkich .) Jeśli to prawda, dowód prawdopodobnie byłby zgodny z dowodem Hartmanisa, Immermana i Sewelsona, że IFF każdy język wielomianowo rzadki w jest zawarty w . (Uwaga, $EXP=PSPACE$ $c$ $n^{O(\log^c n)}$ $poly(n)$ $n$ $n$ $NE = E$ $NP$ $P$ $n^{O(\log^c n)}$ czas w przestrzeni polilogu wciąż wystarcza, by sugerować .) $PSPACE=EXP$

Ryan Williams
źródło

Dziękuję za miłą odpowiedź. Teoria obliczeń Dextera Kozen'a ma niezłą „jednolitą” notację dla klas Ruzzo na stronie 69: gdzie ogranicza przestrzeń, ogranicza czas, a ogranicza zmiany. Następnie podczas gdy która naprawdę podkreśla konstrukcję.

S T A (f, g, h)

$STA(f,g,h)$

f

$f$

g

$g$

h

$h$

NC = S T A (\log n, *, (\log n)^{O (1)})

$\text{NC} = STA(\log n, {*}, (\log n)^{O(1)})$

P = S T A (\log n, *, *)

$\text{P} = STA(\log n, {*}, {*})$

András Salamon

Zauważ, że mówię powyżej. Myślę jednak, że są takie same. Komputer, który zajmuje czas wielomianowy i przestrzeń ale wykonuje tylko można przekształcić w inną maszynę naprzemienną, która zajmuje tylko czas i przestrzeń . (Drugi kierunek jest oczywisty.) Chodzi o to, aby wstawić więcej alternatyw, aby każda faza egzystencjalna czasu wielomianowego i faza uniwersalna była „przyspieszona”, aby działać tylko w czasie i spacja, zgodnie z twierdzeniem Savitcha.

N C = S T A (\log n, (\log n)^{O (1)}, *)

$NC = STA(\log n, (\log n)^{O(1)}, *)$

O (\log n)

$O(\log n)$

(\log n)^{O (1)}

$(\log n)^{O(1)}$

(\log n)^{O (1)}

$(\log n)^{O(1)}$

O (\log n)

$O(\log n)$

(\log n)^{O (1)}

$(\log n)^{O(1)}$

O (\log n)

$O(\log n)$

Ryan Williams,

potrzebujemy jakiegoś skryptu fatmonkey, który automatycznie łączy coś takiego jak „\ NP” z wpisem w zoo.

Suresh Venkat,

(Widziałem odpowiedź Ryana, ale chciałem tylko przedstawić inną perspektywę, która była zbyt długa, aby zmieścić się w komentarzu).

W dowodzie , wszystko, co musisz wiedzieć o L, nieoficjalnie, to że po wysadzeniu przez wykładnik L staje się PSPACE. Ten sam dowód dotyczy NL, ponieważ NL wysadzony przez wykładnik również staje się PSPACE. $L = P \Rightarrow PSPACE = EXP$

Podobnie, gdy NC jest wysadzony przez wykładniczy, dostajesz PSPACE. Lubię to widzieć w kategoriach obwodów: NC to klasa obwodów wielomianowych o głębokości polilogu. Po wysadzeniu staje się to wykładniczym obwodem o wielomianowej głębokości. Można pokazać, że jest to dokładnie PSPACE, po dodaniu odpowiednich warunków jednorodności. Myślę, że jeśli NC jest zdefiniowane z L-jednolitością, to otrzyma jednolitość PSPACE.

Dowód powinien być łatwy. W jednym kierunku weź problem z PSPACE, taki jak TQBF, i wyrażaj kwantyfikatory za pomocą bramek AND i OR o wielkości wykładniczej. W przeciwnym kierunku spróbuj rekurencyjnie przejść przez wielomianowy obwód głębokości. Rozmiar stosu będzie wielomianowy, więc można to zrobić w PSPACE.

Wreszcie wymyśliłem ten argument, gdy zobaczyłem pytanie (i przed przeczytaniem odpowiedzi Ryana), aby mogły wystąpić błędy. Wskaż je.

Robin Kothari
źródło

Jedna korekta: NC ma obwody wielkości wielomianu i głębokości polilogu, ale po translacji jest to nadal tylko głębokość wielomianowa.

Ryan Williams

@Ryan: Masz rację. Naprawię to.

Robin Kothari,

Oto trochę więcej szczegółów z perspektywy symulacji maszyny naprzemiennej Turinga ograniczonej czasoprzestrzenią.

Załóżmy, że . $P = NC$

Ponieważ , otrzymujemy $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$

P = A T I S P ((\log (n))^{O (1)}, O (\log (n))) .

$P = ATISP((\log(n))^{O(1)}, O(\log(n))).$

Teraz rozważmy uniwersalny problem symulacji w czasie liniowym którym otrzymujemy kodowanie na maszynie Turinga i łańcuch wejściowy o długości i chcemy wiedzieć, czy akceptuje co najwyżej kroków. $LinU$ $M$ $x$ $n$ $M$ $x$ $n$

Wiemy, że . Dlatego istnieje stała (wystarczająco duża) taka, że $LinU \in P$ $c$

(*) L i n U \in A T I S P (\log^{c} (n), c \log (n)) .

$(*) \; LinU \in ATISP(\log^c(n), c\log(n)).$

W wyniku argumentu dopełniającego (trochę podchwytliwe zobacz komentarze) mamy

(1) D T I M E (n) \subseteq A T I S P (\log^{c} (n), c \log (n)) .

$(1) \; DTIME(n) \subseteq ATISP(\log^c(n), c\log(n)).$

Rozszerzając argument dopełniania, otrzymujemy

(2) D T I M E (n^{k}) \subseteq A T I S P (k^{c} \log^{c} (n), k c \log (n)) .

$(2) \; DTIME(n^k) \subseteq ATISP(k^c\log^c(n), kc\log(n)).$

(3) D T I M E (2^{n^{k}}) \subseteq A T I S P (k^{c} n^{k c}, k c n^{k}) .

$(3) \; DTIME(2^{n^k}) \subseteq ATISP(k^cn^{kc}, kcn^{k}).$

Ponadto znane są wyniki symulacji maszyn Turinga na przemian w czasoprzestrzeni. W szczególności wiemy, że

A T I S P (\log^{c} (n), c \log (n)) \subseteq D S P A C E (O (\log^{c + 1} (n))) .

$ATISP(\log^c(n), c\log(n)) \subseteq DSPACE(O(\log^{c+1}(n))).$

Dlatego (zasadniczo) mamy następujące wartości dla wszystkich liczb naturalnych : $k$

(2^{*}) D T I M E (n^{k}) \subseteq D S P A C E (k^{c + 1} \log^{c + 1} (n))

$(2^{*}) \; DTIME(n^k) \subseteq DSPACE(k^{c+1}\log^{c+1}(n))$

(3^{*}) D T I M E (2^{n^{k}}) \subseteq D S P A C E (n^{k (c + 1)}) .

$(3^{*}) \; DTIME(2^{n^k}) \subseteq DSPACE(n^{k(c+1)}).$

Z otrzymalibyśmy . $(3^{*})$ $EXP = PSPACE$

==================== Po przemyśleniu ===================

Należy zauważyć, że oznacza dla pewnej stałej . $P = NC$

A T I S P ((\log (n))^{O (1)}, O (\log (n))) = A T I S P (\log^{c} (n), O (\log (n)))

$ATISP((\log(n))^{O(1)}, O(\log(n))) = ATISP(\log^c(n), O(\log(n)))$

c

$c$

Wszelkie uwagi i poprawki są mile widziane. :)

Michael Wehar
źródło

@MichaelWehar Czy znamy w jakimkolwiek stałym ? W szczególności czy znamy a zatem ?

N C^{k} ⊊ P S P A C E

$NC^k\subsetneq PSPACE$

k

$k$

N C^{2} ⊊ P S P A C E

$NC^2\subsetneq PSPACE$

N C \neq P S P A C E

$NC\neq PSPACE$

T ....

@MichaelWehar Nie wiem, ale nigdzie nie widziałem, że . W rzeczywistości komentarz w cstheory.stackexchange.com/questions/39046/… mówi, że jest możliwy. I napisali zapytanie uściśleń cstheory.stackexchange.com/questions/40689/... . Myślisz, że możesz rzucić okiem?

N C \neq P S P A C E

$NC\neq PSPACE$

P - u n i f o r m N C^{1} = P S P A C E

$P-uniform NC^1=PSPACE$

T ....

@Turbo Dziękuję bardzo za miłą odpowiedź !! Może to zależeć od rodzaju munduru. Na przykład może obowiązywać tylko dla NC z log-uniformem. Pozwól mi pomyśleć o tym i wrócić do ciebie. :)

N C = A T I S P ((\log (n))^{O (1)}, O (\log (n)))

$NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$

Michael Wehar

@Turbo Dziękujemy za kontynuację !! Naprawdę uważam, że powinieneś przeczytać definicję na dole strony 370 z: sciencedirect.com/science/article/pii/0022000081900386

Michael Wehar

@Turbo Dzięki za wszystkie twoje kontynuacje !! Bardzo polecam przeczytanie artykułu, który połączyłem, ponieważ w nim jest napisane, że większość z tych pojęć jednolitego jest równoważna. Papier jednak nie uważa -uniform , który mógłby być inny, jak nie mam dowodu, że to jest to samo.

N C

$NC$

P

$P$

N C

$NC$

Michael Wehar