Quelques questions sur le calcul parallèle et la classe NC

J'ai un certain nombre de questions connexes sur ces deux sujets.

Tout d' abord, la plupart des textes de complexité de brillant que sur la classe . Existe-t-il une bonne ressource qui couvre la recherche de manière plus approfondie? Par exemple, quelque chose qui traite de toutes mes questions ci-dessous. En outre, je suppose que N C voit toujours une bonne quantité de recherches en raison de son lien avec la parallélisation, mais je peux me tromper. La section du zoo de la complexité n'est pas d'une grande aide.$\mathbb{NC}$$\mathbb{NC}$

Deuxièmement, le calcul sur un semi-groupe est en si nous supposons que l'opération de semi-groupe prend un temps constant. Mais que se passe-t-il si l'opération ne prend pas un temps constant, comme c'est le cas pour les entiers non bornés? Y a-t-il des problèmes connus de N C i ?$\mathbb{NC}^1$$\mathbb{NC}^i$

Troisièmement, depuis , existe-t-il un algorithme pour convertir tout algorithme d'espace de journalisation en une version parallèle?$\mathbb{L} \subseteq \mathbb{NC}^2$

Quatrièmement, il semble que la plupart des gens supposent que de la même manière que P ≠ N $\mathbb{NC} \ne \mathbb{P}$$\mathbb{P} \ne \mathbb{NP}$ . Quelle est l'intuition derrière cela?

Cinquièmement, chaque texte que j'ai lu mentionne la classe $\mathbb{RNC}$ mais ne donne aucun exemple de problèmes qu'il contient. Y a-t-il?

Enfin, cette réponse mentionne des problèmes dans avec un temps d'exécution parallèle sublinéaire. Quels sont quelques exemples de ces problèmes? Y a-t-il d'autres classes de complexité qui contiennent des algorithmes parallèles qui ne sont pas connus pour être dans N C ?$\mathbb{P}$$\mathbb{NC}$

Troisièmement, depuis , existe-t-il un algorithme pour convertir tout algorithme d'espace de journalisation en une version parallèle?$\sf{L} \subseteq \sf{NC}^2$

On peut montrer (manuel Arora et Barak) étant donné un TM M à temps , qu'un TM M ′ inconscient (c'est-à-dire un TM dont le mouvement de la tête est indépendant de son entrée x ) peut construire un circuit C n pour calculer M ( x ) où | x | = n .$t(n)$$M$$M'$$x$$C_n$$M(x)$$|x| = n$

L'esquisse de preuve va dans le sens où simule M et définit des "instantanés" de son état (c'est-à-dire les positions des têtes, les symboles en tête) à chaque pas de temps t i (pensez à un journal de calcul). Chaque étape t i peut être calculée à partir de x et de l'état t i - 1 . Étant donné que chaque instantané n'implique qu'une chaîne de taille constante et qu'il n'existe qu'une quantité constante de chaînes de cette taille, l'instantané à t i peut être calculé par un circuit de taille constante.$M'$$M$$t_i$$t_i$$x$$t_{i-1}$$t_i$

Si vous composez les circuits de taille constante pour chaque nous avons un circuit qui calcule M ( x ) . En utilisant ce fait, avec la restriction que le langage de M est dans L, nous voyons que notre circuit C n est par définition un espace de log uniforme , où l'uniformité signifie simplement que nos circuits dans notre famille de circuits { C n } calculent M ( x ) tous ont le même algorithme. Pas un algorithme sur mesure pour chaque circuit fonctionnant sur la taille d'entrée n .$t_i$$M(x)$$M$$\sf{L}$$C_n$$\{C_n\}$$M(x)$$n$

Encore une fois, à partir de la définition de l'uniformité, nous voyons que les circuits décidant n'importe quel langage en doivent avoir une taille de fonction ( n ) calculable en O ( log n ) . La famille de circuits A C 1 a au plus une profondeur O ( log n ) .$\sf{L}$$\text{size}(n)$$O(\log n).$$\sf{AC}^1$$O(\log n)$

Enfin, on peut montrer que donnant la relation en question.$\sf{AC}^1 \subseteq \sf{NC}^2$

Quatrièmement, il semble que la plupart des gens supposent que de la même manière que P ≠ N P . Quelle est l'intuition derrière cela?$\sf{NC} \neq \sf{P}$$\sf{P} \neq \sf{NP}$

Avant d'aller plus loin, définissons ce que signifie la complétude.$\sf{P}$

Une langue est P -complète si L ∈ P et chaque langue de P est un espace journal qui lui est réductible. De plus, si L est P- complet, les conditions suivantes sont vraies$L$$\sf{P}$$L \in \sf{P}$$\sf{P}$$L$$\sf{P}$

1. $L \in \sf{NC} \iff \sf{P} = \sf{NC}$

2. $L \in \sf{L} \iff \sf{P} = \sf{L}$

Nous considérons maintenant comme la classe de langages efficacement décidée par un ordinateur parallèle (notre circuit). Il y a quelques problèmes dans P qui semblent résister à toute tentative de parallélisation (c.-à-d. Programmation linéaire et problème de valeur de circuit). C'est-à-dire que certains problèmes nécessitent que le calcul soit effectué par étapes.$\sf{NC}$$\sf{P}$

Par exemple, le problème de valeur de circuit est défini comme:

Étant donné un circuit , une entrée x et une porte g ∈ C , quelle est la sortie de g sur C ( x ) ?$C$$x$$g \in C$$g$$C(x)$

Nous ne savons pas comment calculer cela mieux que de calculer toutes les portes qui précèdent g . Étant donné que certains d'entre eux peuvent être calculés en parallèle, par exemple s'ils se produisent tous à un certain pas de temps t i , mais nous ne savons pas comment calculer la sortie des portes à pas de temps t i et pas de temps t i + 1 pour la difficulté évidente que les portes à t i + 1 nécessitent la sortie des portes à t i !$g'$$g$$t_i$$t_i$$t_{i+1}$$t_{i+1}$$t_i$

Ceci est l'intuition derrière .$\sf{NC} \neq \sf{P}$

Limites de calcul parallèle est un livre sur -Completeness dans la même veine de Garey de Johnson & N P livre -Completeness.$\sf{P}$$\sf{NP}$

Cinquièmement, chaque texte que j'ai lu mentionne la classe RNC mais ne donne aucun exemple de problèmes qu'il contient. Y a-t-il?

L'article «Matching is as Easy as Matrix Inversion» de Mulmuley, Vazirani et Vazirani présente plusieurs exemples de problèmes en classe . Le principal est de trouver une correspondance maximale, puis ils réduisent d'autres problèmes à celui-ci.$\mathbb{RNC}^2$