P-complet

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.

Catalogue de problèmes P-complets

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.
• Cas restreint de CVP - Comme CVP, sauf que chaque porte a deux entrées et deux sorties (F et Non F), toutes les autres couches sont juste des portes ET, les autres sont des portes OU (ou, de manière équivalente, toutes les portes sont des portes NAND, ou toutes les portes sont des portes NOR), les entrées d'une porte proviennent de la couche immédiatement précédente
• Programmation linéaire - Maximiser une fonction linéaire soumise à des contraintes d'inégalité linéaire
• Ordre de recherche lexicographiquement en profondeur d'abord - Étant donné un graphe avec des listes de contiguïtés ordonnées fixes et des nœuds u et v, le sommet u est-il visité avant le sommet v dans une recherche en profondeur d'abord induite par l'ordre des listes de contiguïté ?
• Appartenance à une grammaire hors contexte – Étant donné une grammaire hors contexte et une chaîne, cette chaîne peut-elle être générée par cette grammaire ?
• Horn-satisfiabilité - étant donné un ensemble de clauses de Horn, existe-t-il une affectation de variables qui les satisfait ?
• Jeu de la vie - Étant donné une configuration initiale du jeu de la vie de Conway, une cellule particulière et un temps T (en unaire), cette cellule est-elle vivante après T étapes ?
• LZW (algorithme) (paradigme de 1978) Compression de données - étant donné les chaînes s et t, la compression de s avec une méthode LZ78 ajoutera-t-elle t au dictionnaire ?
• Inférence de type pour les types partiels – Étant donné un terme non typé du calcul lambda, déterminez si ce terme a un type partiel.

Le livre de Greenlaw et al. contient 96 problèmes P-complets pour NC.