NC = P conséquences?

Le zoo de complexité souligne dans l'entrée sur EXP que si L = P, alors PSPACE = EXP. Depuis NPSPACE = PSPACE par Savitch, dans la mesure où je peux dire, l’argument de remplissage de base sous-jacent s'étend pour montrer que Nous savons également que L NL NC P via la hiérarchie alternée liée aux ressources de Ruzzo.

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

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

\subseteq

$\subseteq$

\subseteq

$\subseteq$

\subseteq

$\subseteq$

Si NC = P, cela signifie-t-il que PSPACE = EXP?

Une interprétation différente de la question, dans l’esprit de Richard Lipton: est-il plus probable que certains problèmes de P ne puissent pas être mis en parallèle, plutôt qu’aucune procédure à exponentielle n’exige plus que de l’espace polynomial?

Je serais également intéressé par d’autres conséquences "surprenantes" de NC = P (le plus improbable sera le mieux).

Edit: La réponse de Ryan conduit à une autre question: quelle est l'hypothèse la plus faible connue pour garantir PSPACE = EXP?

W. Savitch. Relations entre la complexité des bandes non déterministes et déterministes, Journal of Computer and System Sciences 4 (2): 177-192, 1970.
WL Ruzzo. Sur la complexité du circuit uniforme, Journal of Computer Science and System Sciences 22 (3): 365-383, 1971.

Edit (2014): ancien lien de Zoo mis à jour et liens ajoutés pour toutes les autres classes.

cc.complexity-theory conditional-results András Salamon
la source

Comme je suis sûr que je ne suis pas le seul à ne pas savoir ce que NC est, voici un lien: fr.wikipedia.org/wiki/NC_%28complexity%29

Emil

@Andras: Une autre conséquence que vous connaissez peut-être déjà, mais que vous n'avez pas encore mentionnée, est qu'alors la hiérarchie s'effondrerait, car a des problèmes complets sous -reductions .

N C

$\mathsf{NC}$

P

$\mathsf{P}$

L

$\mathsf{L}$

Joshua Grochow

Réponses:

Oui. peut être considéré comme la classe de langages reconnus en alternant les machines de Turing utilisant un espace et un temps . (Ceci a été prouvé pour la première fois par Ruzzo.) est la classe dans laquelle les machines de Turing en alternance utilisent un espace mais peuvent prendre jusqu'à temps. Par souci de concision Appelons ces classes et . $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$

Supposons que les deux classes sont égales. En remplaçant le par dans ce qui précède (en appliquant des lemmes de traduction standard), on obtient $n$ $2^n$

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

Si alors également, car il existe des langues complètes dans . $TIME[2^{O(n)}] \subseteq PSPACE$ $EXP = PSPACE$ $EXP$ $TIME[2^{O(n)}]$

Edit: Bien que la réponse ci-dessus soit peut-être plus éducative, voici un argument plus simple: découle déjà de " est contenu dans un espace polylog" et d'une traduction standard. Note « est contenu dans l' espace polylog » est une hypothèse beaucoup plus faible que . $EXP = PSPACE$ $P$ $P$ $NC = P$

Plus de détails: comme les familles de circuits ont une profondeur constante, chaque famille de circuits de ce type peut être évaluée dans un espace . D'où . Donc implique . Appliquer la traduction (remplacer par ) implique . L'existence d'un langage complet dans termine l'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)}]$

Mise à jour: Pour répondre à la question supplémentaire d’Andreas, je pense qu’il devrait être possible de prouver quelque chose du type: si et pour tout , tout langage polynomial peu développé en un temps peut être résolu dans l’espace polylog. (Être polynomialement rare signifie qu'il existe au plus chaînes de longueur dans la langue, pour tout .) Si cela est vrai, la preuve irait probablement dans le sens de la preuve de Hartmanis, Immerman et Sewelson selon laquelle ssi toutes les langues polynomiale rares dans est contenu dans . (Remarque, $EXP=PSPACE$ $c$ $n^{O(\log^c n)}$ $poly(n)$ $n$ $n$ $NE = E$ $NP$ $P$ $n^{O(\log^c n)}$ le temps en espace de polylogue est encore suffisant pour impliquer .) $PSPACE=EXP$

Ryan Williams
la source

Merci pour la belle réponse. La théorie du calcul de Dexter Kozen a une belle notation "uniforme" pour les classes de Ruzzo à la page 69: où limite l’espace, temps et alternances. Puis tandis que qui met vraiment en valeur la construction.

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 le

Notez que je dis dans ce qui précède. Cependant, je pense que ce sont les mêmes. Une machine qui prend un temps polynomial et un espace mais effectue uniquement des alternations peut être transformée en une autre machine alternée prenant uniquement heure et espace. (L’autre direction est évidente.) L’idée est d’insérer plus d’alternances pour que chaque phase existentielle polynomiale et chaque phase universelle soit "accélérée" pour ne fonctionner que dans temps et space, dans le sens du théorème de Savitch.

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 le

ce dont nous avons besoin, c'est une sorte de script greasemonkey qui lie automatiquement quelque chose comme "\ NP" à l'entrée du zoo.

Suresh Venkat

(J'ai vu la réponse de Ryan, mais je voulais simplement fournir une autre perspective, qui était trop longue pour tenir dans un commentaire.)

Dans la preuve , tout ce que vous devez savoir à propos de L, de manière informelle, est que, lorsqu'il est gonflé par une exponentielle, L devient PSPACE. La même preuve est valable pour NL, car NL qui est agrandi par une exponentielle devient également PSPACE. $L = P \Rightarrow PSPACE = EXP$

De même, lorsque NC est expulsé par une exponentielle, vous obtenez PSPACE. J'aime voir cela en termes de circuits: NC est la classe des circuits de taille polynomiale à profondeur de polylogue. Lorsque gonflé, cela devient des circuits de taille exponentielle avec une profondeur polynomiale. On peut montrer que c'est exactement PSPACE, une fois que les conditions d'uniformité appropriées ont été ajoutées. Je suppose que si NC est défini avec L-uniformity, alors cela obtiendra l'uniformité PSPACE.

La preuve devrait être facile. Dans un sens, prenez un problème complet de PSPACE tel que TQBF et exprimez les quantificateurs en utilisant les portes ET et OU de taille exponentielle. Dans l’autre direction, essayez de traverser le circuit de profondeur polynomial de manière récursive. La taille de la pile sera polynomiale, cela peut donc être fait dans PSPACE.

Finalement, j'ai eu cet argument lorsque j'ai vu la question (et avant de lire la réponse de Ryan), donc il pourrait y avoir des bugs. S'il vous plaît les signaler.

Robin Kothari
la source

Une correction: NC a des circuits de taille polynomiale et de profondeur de polylogue, mais il ne s’agit toujours que de profondeur polynomiale après translation.

Ryan Williams le

@ Ryan: Vous avez raison. Je vais arranger ça.

Robin Kothari le

Voici un peu plus de détails du point de vue de la simulation d'une machine de Turing alternante limitée dans le temps.

Supposons que . $P = NC$

Puisque , nous obtenons $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))).$

Maintenant, considérons le problème de simulation universelle linéaire du temps où nous recevons un codage sur une machine de Turing et une chaîne d'entrée de longueur et nous voulons savoir si accepte au plus étapes. $LinU$ $M$ $x$ $n$ $M$ $x$ $n$

$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)).$

(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)).$

(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}).$

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))).$

$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)}).$

$(3^{*})$ $EXP = PSPACE$

==================== Après réflexion ==================

$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$

Tous les commentaires ou corrections sont les bienvenus. :)

Michael Wehar
la source

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$

@ MichaelWehar Je ne sais pas mais je n'ai jamais vu nulle part que . En fait, un commentaire dans cstheory.stackexchange.com/questions/39046/… indique que est possible. J'ai posté une requête de clarification dans cstheory.stackexchange.com/questions/40689/… . Pensez-vous que vous pouvez jeter un oeil?

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 .... le

@Turbo Merci beaucoup pour l'aimable réponse !! Cela peut dépendre du type d'uniforme. Par exemple, ne peut être valable que pour Logspace-uniform NC. Laissez-moi y réfléchir et revenir à vous. :)

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 Merci pour le suivi !! Je pense vraiment que vous devriez lire la définition au bas de la page 370 de: sciencedirect.com/science/article/pii/0022000081900386

Michael Wehar

@Turbo Merci pour tous vos suivis! Je vous recommande vivement de lire le document que j'ai lié car il indique que la plupart de ces notions de uniforme sont équivalentes. Cependant, le document ne considère pas uniforme qui pourrait éventuellement être différent car je n'ai aucun moyen de prouver que c'est le même.

N C

$NC$

P

$P$

N C

$NC$

Michael Wehar