P-complet
From Wikipedia, the free encyclopedia
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[1]. 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.
