P-complet - P-complete

En théorie de la complexité computationnelle , un problème de décision est P-complet ( complet pour la classe de complexité P ) s'il est dans P et tout problème de P peut lui être réduit par une réduction appropriée.

La notion de problèmes de décision P-complet est utile dans l'analyse de :

• quels problèmes sont difficiles à paralléliser efficacement,
• quels problèmes sont difficiles à résoudre dans un espace limité.

en particulier lorsque des notions de réductibilité plus faibles que la réductibilité polytemporelle sont prises en compte.

Le type spécifique de réduction utilisé varie et peut affecter l'ensemble exact de problèmes. De manière générique, des réductions plus faibles que les réductions en temps polynomial sont utilisées, puisque tous les langages de P sont P-Complet 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 tous les problèmes P -complets se situent en dehors de NC et ne peuvent donc pas être parallélisés efficacement, sous l'hypothèse non prouvée que NC  ≠  P . Si nous utilisons la réduction de l'espace log plus faible , cela reste vrai, mais en plus nous apprenons que tous les problèmes P -complets se trouvent en dehors de L sous l'hypothèse non prouvée plus faible que L  ≠  P . Dans ce dernier cas l'ensemble P- complet peut être plus petit.

Motivation

La classe P , généralement considérée comme constituée de tous les problèmes « traitables » pour un ordinateur séquentiel, contient la classe NC , qui comprend les problèmes pouvant être résolus efficacement sur un ordinateur parallèle. En effet, des ordinateurs parallèles peuvent être simulés sur une machine séquentielle. On ne sait pas si NC  =  P . En d'autres termes, on ne sait pas s'il existe des problèmes traitables qui sont intrinsèquement séquentiels. Tout comme il est largement soupçonné que P n'est pas égal à NP , il est également largement soupçonné que NC n'est pas égal à P .

De même, la classe L contient tous les problèmes qui peuvent être résolus par un ordinateur séquentiel dans l'espace logarithmique. De telles machines fonctionnent en temps polynomial car elles peuvent avoir un nombre polynomial de configurations. On soupçonne que L  ≠  P ; c'est-à-dire que certains problèmes qui peuvent être résolus en temps polynomial nécessitent également plus que l'espace logarithmique.

De la même manière que l'utilisation de problèmes NP-complets pour analyser la question P  =  NP , les problèmes P -complets , considérés comme les problèmes "probablement non parallélisables" ou "probablement intrinsèquement séquentiels", servent de la même manière à étudier le NC  =  P question. Trouver un moyen efficace de paralléliser la solution d'un problème P- complet montrerait que NC  =  P . Il peut également être considéré comme les « problèmes nécessitant un espace superlogarithmique » ; une solution dans l'espace log à un problème P -complet (en utilisant la définition basée sur les réductions dans l'espace log) impliquerait L  =  P .

La logique derrière cela est analogue à la logique selon laquelle une solution en temps polynomial d'un problème NP -complet prouverait P  =  NP : si nous avons une réduction NC de n'importe quel problème de P à un problème A, et une solution NC pour A, alors NC  =  P . De même, si nous avons une réduction de l'espace log de n'importe quel problème de P vers un problème A, et une solution de l'espace log pour A, alors L  =  P .

Problèmes P-complets

Le problème P- complet le plus basique sous les réductions à plusieurs et un de l'espace de log est le suivant : étant donné une machine de Turing , une entrée pour cette machine x et un nombre T (écrit en unaire ), cette machine s'arrête-t-elle sur cette entrée au cours des T premières étapes ? Pour tout x in dans P, sortir le codage de la machine de Turing qui l'accepte en temps polynomial, le codage de x lui-même, et un nombre d'étapes correspondant au p qui y est lié en temps polynomial sur le fonctionnement du Turing Machine à décider , . La machine M s'arrête sur x dans les étapes si et seulement si x est dans L. Clairement, si nous pouvons paralléliser une simulation générale d'un ordinateur séquentiel (c'est-à-dire la simulation de la machine de Turing d'une machine de Turing), alors nous pourrons paralléliser tout programme qui s'exécute sur cet ordinateur. Si ce problème est dans NC , alors tout autre problème dans P . Si le nombre d'étapes est écrit en binaire, le problème est EXPTIME-complete . Ce problème illustre une astuce courante dans la théorie de la P- complétude. Nous ne sommes pas vraiment intéressés à savoir si un problème peut être résolu rapidement sur une machine parallèle. Nous cherchons simplement à savoir si une machine parallèle le résout beaucoup plus rapidement qu'une machine séquentielle. Par conséquent, nous devons reformuler le problème pour que la version séquentielle soit dans P . C'est pourquoi ce problème nécessitait que T soit écrit en unaire. Si un nombre T est écrit sous forme de nombre binaire (une chaîne de n uns et zéros, où n  = log  T ), alors l'algorithme séquentiel évident peut prendre le temps 2 ⁿ . D'un autre côté, si T est écrit comme un nombre unaire (une chaîne de n unités, où n  =  T ), alors cela ne prend que le temps n . En écrivant T en unaire plutôt qu'en binaire, nous avons réduit l'algorithme séquentiel évident du temps exponentiel au temps linéaire. Cela pose le problème séquentiel dans P . Ensuite, il sera en CN si et seulement s'il est parallélisable. ${\style d'affichage M}$${\displaystyle \langle M,x,T\rangle }$${\style d'affichage L}$${\style d'affichage T=p(|x|)}$${\style d'affichage M_{L}}$${\style d'affichage L}$${\displaystyle \langle M,x,p(|x|)\rangle }$${\style d'affichage p(|x|)}$

De nombreux autres problèmes se sont avérés être P- complets et sont donc largement considérés comme intrinsèquement séquentiels. Ceux-ci incluent les problèmes suivants qui sont P-Complet sous au moins des réductions d'espace log, soit comme donné, soit sous une forme de problème de décision :

• Problème de valeur de circuit (CVP) - Étant donné un circuit , les entrées du circuit et une porte du circuit, calculent la sortie de cette porte. Ce langage est P-Complet sous des notions de réduction beaucoup plus faibles, y compris les réductions uniformes à plusieurs et les projections polylogarithmiques.${\displaystyle AC^{0}}$
• 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 ne sont que des portes ET, les autres sont des portes OU (ou, de manière équivalente, toutes les portes sont des portes NAND, ou toutes 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 en profondeur d'abord lexicographiquement - Étant donné un graphe avec des listes d'adjacence 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 d'adjacence ?
• Adhésion à la grammaire sans contexte - Étant donné une grammaire sans 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 variable qui les satisfasse ? C'est la version de P du problème de satisfiabilité booléenne .
• 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 ? (Notez que pour la compression LZ77 telle que gzip , c'est beaucoup plus facile, car le problème se réduit à "Is t in s ?".)
• 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.

Afin de prouver qu'un problème donné dans P est P-complet, on essaie généralement de réduire un connu P problème -complete à celui donné.

En 1999, Jin-Yi Cai et D. Sivakumar, s'appuyant sur les travaux d'Ogihara, ont montré que s'il existe un langage clairsemé qui est P- complet, alors L  =  P .

Les problèmes P-complets peuvent être résolus avec des complexités temporelles différentes . Par exemple, le problème de la valeur du circuit peut être résolu en temps linéaire par un tri topologique . Bien sûr, parce que les réductions à un problème P-complet peuvent avoir des complexités temporelles différentes, ce fait n'implique pas que tous les problèmes de P puissent également être résolus en temps linéaire.

Problèmes non connus pour être P-complet

Certains NP -problèmes ne sont pas connus pour être NP -complets ou en P . Ces problèmes (ex. factorisation , isomorphisme de graphes , jeux de parité ) sont suspectés d'être difficiles. De même, il existe des problèmes dans P qui ne sont pas connus pour être P -complet ou NC , mais sont considérés comme difficiles à paralléliser. Les exemples incluent les formes de problème de décision consistant à trouver le plus grand diviseur commun de deux nombres et à déterminer quelle réponse l' algorithme euclidien étendu retournerait lorsqu'on lui donnait deux nombres.

Remarques

Les références

• Greenlaw, Raymond, James Hoover et Walter Ruzzo. 1995. Limites au calcul parallèle ; Théorie de la P-Complétude . ISBN  0-19-508591-4 . — Développe la théorie, puis répertorie 96 problèmes P-Complet.
• Satoru Miyano, Shuji Shiraishi et Takayoshi Shoudai. Une liste de problèmes P-complet . Université de Kyushu, RIFIS-TR-CS-17. décembre 1990.