P-complétude et calcul parallèle

J'ai récemment lu sur les algorithmes de vérification de la bisimilarité et lu que le problème est P-complet . En outre, une conséquence de cela est que ce problème, ou tout problème P-complet, est peu susceptible d'avoir des algorithmes parallèles efficaces.

Quelle est l'intuition derrière cette dernière affirmation?

Tout problème $P$ complet, a peu de chances d'avoir un algorithme parallèle efficace. Pourquoi ?

L'existence de problèmes $P$ complets est l'indice le plus important que $(P ∩ POLYLOGSPACE) ≠ P$. La question est alors de savoir pourquoi cette conjecture est pertinente pour le calcul parallèle? Commençons par les ressources utilisées dans un calcul. Pour l'informatique séquentielle: temps et espace; pour le calcul parallèle: temps et matériel (nombre de processeurs). Y a-t-il une relation? Oui! Espace séquentiel time temps parallèle; Temps séquentiel hardware matériel parallèle. La correspondance entre l'espace séquentiel et le temps parallèle semble indépendante du modèle de calcul parallèle adopté; cela conduit à la thèse de calcul parallèle suivante, qui n'est pas prouvée.

(Chandra et Stockmeyer) Chaque calcul d'une MT avec complexité spatiale peut être simulé dans un modèle de calcul parallèle dans le temps T ( n ) = O ( S ( n ) O ( 1 ) ) et chaque calcul d'un calcul parallèle le modèle à complexité temporelle T ′ ( n ) peut être simulé par une MT à complexité spatiale S ′ ( n ) = O ( T ′ ( n ) $S(n)$$T(n) = O(S(n)^{O(1)})$$T’(n)$.$S’(n) = O(T’(n)^{O(1)})$

La classe des problèmes solubles séquentiellement dans l' espace polynôme est et l'ensemble des problèmes solubles en temps polynomial est P .Comme P S P A C E est considéré comme une classe beaucoup plus de problèmes que P , la thèse quantifie l'amélioration effective rendue possible par le parallélisme. Une conséquence de cette thèse est qu'une PRAM peut résoudre des problèmes complets en N P en temps polynomial… Malheureusement non! La thèse du calcul parallèle implique que nous pouvons réellement traiter des problèmes appartenant à P S P A C $PSPACE$$P$$PSPACE$$P$$NP$$PSPACE$… Mais cela nécessite un nombre exponentiel de processeurs! Un compromis espace-temps fonctionne: le temps exponentiel sur le modèle de calcul séquentiel est transformé en un nombre exponentiel de processeurs sur le modèle de calcul parallèle, tandis que l'espace polynomial sur le modèle de calcul séquentiel est transformé en un temps polynomial sur le parallèle modèle informatique.

Ce compromis est plus facile à comprendre si nous essayons de limiter le temps à la fois parallèle et matériel parallèle: si le modèle de calcul parallèle a un nombre polynôme de processeurs, la classe des problèmes résoluble en temps polynomial parallèle est . Si nous limitons le nombre de processeurs à un polynôme, nous pouvons améliorer les performances d'une machine séquentielle, mais pas plus qu'un facteur polynomial. Ainsi, nous pouvons réduire le degré du polynôme représentant la complexité temporelle, mais nous ne pouvons pas utiliser le parallélisme pour réduire les coûts exponentiels aux coûts polynomiaux.$P$

Les problèmes résolus en parallèle avec la complexité polynomiale sont les problèmes appartenant à . La contrainte polynomiale sur le nombre de processeurs conduit à un modèle de calcul parallèle équivalent à TM. Il y a deux considérations pratiques importantes: quel nombre polynomial de processeurs est acceptable / abordable? En pratique, le nombre polynomial de processeurs est censé être linéaire ou proche. Quel temps sous-polynomial est réalisable? Il s'est avéré que presque tous les problèmes réalisables hautement parallèles peuvent atteindre un temps parallèle polylogarithmique. En parallèle, une complexité temporelle logarithmique dans la longueur d'entrée représente un calcul parallèle efficace. Un algorithme parallèle est considéré comme efficace si, étant donné un nombre polynomial de processeurs, sa complexité temporelle est polylogarithmique.$P$

Étant donné un problème où k et h sont des constantes, la thèse du calcul parallèle implique l'existence d'un algorithme parallèle pour R avec complexité temporelle O ( ( l o g n ) k ′ ) où k $R \in TIME\_SPACE_{TM}(n^k, (log n)^h)$$k$$h$$R$$O((log n)^{k’})$$k’$est une constante. La comparaison entre le temps séquentiel et le temps parallèle permet de classer comme un problème hautement parallélisable (dans une perspective temporelle).$R$

De la thèse du calcul parallèle, il s'ensuit que est la classe de problèmes hautement parallélisable. P O L Y L O G S P A C E ne contient pas de problèmes complets en ce qui concerne les réductions d'espace logarithmique; cela implique P O L Y L O G S P A C E ≠ P . Il paraît que$POLYLOGSPACE$$POLYLOGSPACE$$POLYLOGSPACE \neq P$

1. $POLYLOGSPACE ⊄ P$
2. $P ⊄ POLYLOGSPACE$

contient les problèmes qui peuvent être résolus en temps polynomial en utilisant l'espace polylogarithmique. Les problèmes P -complets appartiennent probablement à P - ( P ∩ P O L Y L O G S P A C E ) .$P ∩ POLYLOGSPACE$$P$$P - (P ∩ POLYLOGSPACE)$

(classe de Nick - ainsi appelée en l'honneur de Nicholas Pippenger, le premier à l'identifier et à le caractériser en 1979) est la classe de problèmes qui peuvent être résolus en temps polylogarithmique (c'est-à-dire avec la complexité temporelle O ( ( l o g n ) k ) ) avec un nombre polynomial de processeurs (Ie, délimité par O ( f ( n ) ) pour une fonction polynomiale f où n est la taille du problème) La thèse du calcul parallèle implique N C ⊂ ( P ∩ P $NC$$O((log n)^k))$$O(f(n))$$f$$n$ .$NC ⊂ (P ∩ POLYLOGSPACE)$

Cependant, malheureusement, par définition, comprend également de nombreux problèmes qui ne sont pas efficacement parallélisables. L'exemple le plus tristement célèbre est la recherche binaire parallèle . Le problème est que ce problème a une complexité temporelle polylogarithmique même pour p = 1. Tout algorithme séquentiel nécessitant au plus le temps logarithmique dans le pire des cas est en N C quelle que soit sa faisabilité parallèle!$NC$$p$$NC$

Maintenant, nous pouvons enfin expliquer pourquoi les problèmes complets sont les problèmes parallélisables les plus difficiles. Étant donné un P problème -complete Q , il est très peu probable l'existence d'un algorithme parallèle efficace: si un tel algorithme parallèle existerait avec la complexité du temps O ( ( l o g n ) k ) , la thèse de calcul parallèle impliquera l'existence d'un algorithme séquentiel de complexité spatiale O ( ( l o g n ) k ′ ) pour le même problème. Puisque Q est un $P$$P$$Q$$O((log n)^k)$$O((log n)^{k’})$$Q$$P$-complete problème à son tour , impliquera que tous les problèmes de peut être résolu dans l' espace poly-log: ( P ∩ P O L Y L O G S P A C E ) = P . Comme vous le savez déjà, nous pensons plutôt que ( P ∩ P O L Y L O G S P A C E ) ⊂ P , même si nous ne sommes pas encore en mesure de le prouver.$P$$(P ∩ POLYLOGSPACE) = P$$(P ∩ POLYLOGSPACE) ⊂ P$

Une dernière observation, au sujet de l'exigence du processeur polynomial. Eh bien, c'est une déclaration théorique. En pratique: une exigence de processeur qui croît plus vite que la taille du problème peut ne pas être vraiment utile.

Parce que « parallèle efficace » tombe à l' intérieur $\mathsf{NC}$ ( « classe Nick » des problèmes décidables en temps polylogarithmique avec un nombre polynomial de processeurs), et il est largement considéré que $\mathsf{NC} \neq \mathsf{P}$ . Donc, tout problème n'est pas censé avoir un algorithme parallèle efficace (car cela impliquerait que P = N C ).$\mathsf{P\text{-}complete}$$\mathsf{P} = \mathsf{NC}$

Bien sûr , tout cela est à la conjecture que , comme vous le savez est un problème ouvert que P est pas dans le premier niveau de N C , autrement dit , nous ne pas savoir si N C 1 ≠ P .$\mathsf{NC} \neq \mathsf{P}$$\mathsf{P}$$\mathsf{NC}$$\mathsf{NC^1} \neq \mathsf{P}$

De plus, nous ne savons même pas si vous ne pouvez pas résoudre les problèmes de dans A C 0 [ 6 ] , c'est-à-dire les circuits booléens à profondeur constante (= temps parallèle constant) avec$\mathsf{P}$$\mathsf{AC^0[6]}$ portes.$\mod_6$

Pour plus d'informations, consultez le livre suivant:

Raymond Greenlaw, H. James Hoover, Walter L. Ruzzo, " Limits to Parallel Computation: P-Completeness Theory ", 1995.

La réponse de Kaveh couvre la définition habituelle du "parallélisme", qui est NC. La question de savoir si P NC est l'une des questions les plus difficiles dans la théorie de la complexité (et à certains égards tout aussi pertinente que la question P < NP).$<$$<$

L'intuition derrière cela est que certains problèmes en P, comme la programmation linéaire ou l'ordre DFS, semblent avoir beaucoup de dépendances qui forcent un long "chemin critique" qui ne peut pas être parallélisé. Ce n'est pas plus une preuve que le non-déterminisme qui semble être très puissant, mais c'est l'idée de base.

Edit: Pour clarifier les commentaires, le point de cette réponse est de dire pourquoi (certaines) personnes ne pensent pas que P et NC sont les mêmes. Tout comme avec P et NP, personne ne sait comment prouver si les deux sont différents, mais il y a quelque chose au sujet des problèmes difficiles qui font penser à (certains) informaticiens.

Un autre côté est que NC est un "temps polylog sur de nombreux processeurs polynomiaux", ce qui demande une accélération très spectaculaire mais donne beaucoup de processeurs. Ainsi, il pourrait ne pas correspondre à une notion pratique de parallélisable.

$<$

Soyez très attentif à qui veut dire exactement "algorithmes parallèles efficaces".

Les réponses plus anciennes expliquent la perspective de la théorie de la complexité. Là, «efficace» signifie généralement quelque chose de vague comme «runtime in$O(f(n))$ temps avec $O(g(n))$ processeurs ". Notez que le nombre de processeurs peut dépendre de la taille d'entrée!

En particulier, la classe NC souvent nommée est la

ensemble de problèmes de décision décidables en temps polylogarithmique sur un ordinateur parallèle avec un nombre polynomial de processeurs.

Cela n'a rien à voir avec l'existence d'algorithmes parallèles pour ces problèmes qui sont efficaces en termes plus pratiques¹:

• Si vous disposez d'un algorithme CN, vous n'obtenez aucune information sur la façon de résoudre le problème (efficacement) sur une machine avec un nombre fixe de processeurs.

• Just because there is no NC algorithm for a problem does not mean there isn't a "real" one; just because we can not break apart the problem into polynomially many very small pieces does not mean we can not break it into constantly many sufficiently smaller ones, as $n$ grows.

  For instance, on constantly many processors with shared memory, CYK parsing can be done in parallel with asymptotically optimal speedup (see my master thesis, even though context-free parsing is P-complete.

Describing efficiency on machines with finitely many processors in a useful way requires more precise analysis than $O(\dots)$l'accélération étant limitée par une constante finie, le nombre de processeurs². On trouve rarement cela dans la théorie de la complexité. Par conséquent, si vous voulez en savoir plus sur les algorithmes parallèles qui sont utiles dans le monde réel, je vous conseille de chercher ailleurs.

1. Laisser $T_p : \mathbb{N} \to \mathbb{R_{\geq 0}}$la fonction d'exécution d'un algorithme parallèle. Vous voudrez peut-être appeler un algorithme "efficace" si$T_1(n)/T_p(n) \approx p$, ou si $T_1(n) \approx T(n)$ pour $T$la fonction d'exécution d'un bon algorithme séquentiel. Je propose cela d'une manière plus rigoureuse dans ma thèse de maîtrise , en partant de la littérature qui y est citée.

2. This is not always true; memory hierarchy and hardware may allow for larger speedup, at least sometimes. There will be another constant bound, though.

Suppose tomorrow someone discovered a proof that P = NC. What would the consequences for computer science research and practical applications be in this case?

That question was marked as duplicate this question, so let me just assume that it is really a duplicate, and provide one possible answer.

Nous savons que NC! = PSPACE, donc une preuve que P = NC prouverait également P! = PSPACE. Cela peut ne pas sembler être un gros problème, mais c'est une conséquence pour la recherche en informatique.

Pourquoi connaissons-nous NC! = PSPACE? Eh bien, nous connaissons NC ^k ⊆ DSPACE (O (log ^k )), nous pouvons donc simplement utiliser le théorème de la hiérarchie spatiale.

En termes d'applications pratiques, les applications autour de la programmation linéaire (et convexe) pourraient être si séduisantes que des architectures parallèles personnalisées avec des compilateurs pour traduire efficacement les formulations de programmation linéaire en ce matériel pourraient être développées et vendues.