Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
P-complet
Résumé
En théorie de la complexité computationnelle, un problème de décision est P-complet (c.-à-d. complet pour la classe de complexité P des problèmes en temps polynomial) s'il est dans P et tout problème dans P peut y être réduit par une réduction en espace logarithmique (d'autres réductions sont aussi utilisées, comme NC).
La notion de problème de décision P-complet est utile pour déterminer :
quels problèmes sont difficiles à paralléliser efficacement (si on utilise des réductions NC),
quels problèmes sont difficiles à résoudre dans un espace limité (si on utilise des réductions en espace logarithmique).
Le type de réduction utilisé varie et peut affecter l'ensemble exact des problèmes. De manière générique, des réductions plus restrictives que les réductions en temps polynomial doivent être utilisées, puisque tous les langages de P (sauf le langage vide et le langage de toutes les chaînes) sont P-complets sous des réductions en temps polynomial. Si nous utilisons des réductions NC, c'est-à-dire des réductions qui peuvent fonctionner en temps polylogarithmique sur un ordinateur parallèle avec un nombre polynomial de processeurs, alors les problèmes P-complets pour NC se trouvent en dehors de NC et ne peuvent donc pas être efficacement parallélisés, sous l'hypothèse non prouvée que NC ≠ P. Si nous utilisons la réduction en espace logarithmique, plus restrictive, cela reste vrai, mais en plus ces problèmes P-complets pour L se trouvent en dehors de L sous l'hypothèse non prouvée plus faible que L ≠ P.
De nombreux autres problèmes se sont révélés être P-complets et sont donc largement considérés comme intrinsèquement séquentiels. Ceux-ci incluent les problèmes suivants :
Problème de l'évaluation d'un circuit (CVP) - Étant donné un circuit, les entrées du circuit et une porte dans le circuit, calculez la sortie de cette porte.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.