Complexité paramétrée - Parameterized complexity

En informatique , la complexité paramétrée est une branche de la théorie de la complexité computationnelle qui se concentre sur la classification des problèmes de calcul en fonction de leur difficulté inhérente par rapport à plusieurs paramètres de l'entrée ou de la sortie. La complexité d'un problème est alors mesurée en fonction de ces paramètres. Cela permet de classer les problèmes NP-difficiles à une échelle plus fine que dans le cadre classique, où la complexité d'un problème n'est mesurée qu'en fonction du nombre de bits en entrée. Le premier travail systématique sur la complexité paramétrée a été réalisé par Downey & Fellows (1999) .

En supposant que P NP , il existe de nombreux problèmes naturels qui nécessitent un temps d'exécution superpolynomial lorsque la complexité est mesurée en termes de taille d'entrée uniquement, mais qui sont calculables dans un temps polynomial dans la taille d'entrée et exponentiel ou pire dans un paramètre k . Par conséquent, si k est fixé à une petite valeur et que la croissance de la fonction sur k est relativement faible, de tels problèmes peuvent toujours être considérés comme « traitables » malgré leur classification traditionnelle comme « insolubles ».

L'existence d'algorithmes de résolution efficaces, exacts et déterministes pour les problèmes NP-complets , ou autrement NP-difficiles , est considérée comme peu probable, si les paramètres d'entrée ne sont pas fixés ; tous les algorithmes de résolution connus de ces problèmes nécessitent un temps exponentiel (ou au moins superpolynomial) dans la taille totale de l'entrée. Cependant, certains problèmes peuvent être résolus par des algorithmes qui ne sont exponentiels que dans la taille d'un paramètre fixe tandis que polynomiaux dans la taille de l'entrée. Un tel algorithme est appelé algorithme (fpt-) à paramètre fixe , car le problème peut être résolu efficacement pour de petites valeurs du paramètre fixe.

Les problèmes dans lesquels un paramètre k est fixé sont appelés problèmes paramétrés. Un problème paramétré qui permet un tel algorithme fpt est dit être un problème traitable à paramètres fixes et appartient à la classe FPT , et le premier nom de la théorie de la complexité paramétrée était traitabilité à paramètres fixes .

De nombreux problèmes ont la forme suivante : étant donné un objet x et un entier non négatif k , x a-t-il une propriété qui dépend de k ? Par exemple, pour le problème de couverture de sommets , le paramètre peut être le nombre de sommets dans la couverture. Dans de nombreuses applications, par exemple lors de la modélisation de la correction d'erreurs, on peut supposer que le paramètre est "petit" par rapport à la taille totale de l'entrée. Ensuite, il est difficile de trouver un algorithme exponentiel uniquement en k , et non en taille d'entrée.

De cette façon, la complexité paramétrée peut être considérée comme une théorie de la complexité à deux dimensions . Ce concept est formalisé comme suit :

Un problème paramétré est un langage , où est un alphabet fini. La deuxième composante est appelée le paramètre du problème.
Un problème paramétré L est traitable à paramètres fixes si la question « ? peut être décidé en temps d'exécution , où f est une fonction arbitraire ne dépendant que de k . La classe de complexité correspondante est appelée FPT .

Par exemple, il existe un algorithme qui résout le problème de couverture de sommets en temps, où n est le nombre de sommets et k est la taille de la couverture de sommets. Cela signifie que la couverture de sommet est traitable à paramètre fixe avec la taille de la solution comme paramètre.

Classes de complexité

FPT

FPT contient les problèmes traitables à paramètres fixes , qui sont ceux qui peuvent être résolus à temps pour une fonction calculable f . En règle générale, cette fonction est considérée comme une seule exponentielle, telle que mais la définition admet des fonctions qui croissent encore plus rapidement. Ceci est essentiel pour une grande partie de l'histoire des débuts de cette classe. La partie cruciale de la définition est d'exclure les fonctions de la forme , telles que . La classe FPL (paramètre fixe linéaire) est la classe de problèmes résolvables en temps pour une fonction calculable f . FPL est donc une sous-classe de FPT.

Un exemple est le problème de satisfiabilité , paramétré par le nombre de variables. Une formule donnée de taille m avec k variables peut être vérifiée par force brute en temps . Une couverture de sommets de taille k dans un graphe d'ordre n peut être trouvée en temps , donc ce problème est également en FPT.

Un exemple de problème que l'on pense ne pas être dans FPT est la coloration de graphe paramétrée par le nombre de couleurs. On sait que le 3-colorant est NP-dur , et un algorithme de graphe k -colouring dans le temps pour irait en temps polynomial dans la taille de l'entrée. Ainsi, si la coloration du graphe paramétrée par le nombre de couleurs était en FPT, alors P = NP .

Il existe un certain nombre de définitions alternatives de FPT. Par exemple, l'exigence de temps d'exécution peut être remplacée par . Aussi, un problème paramétré est en FPT s'il a un soi-disant noyau. Le noyautage est une technique de prétraitement qui réduit l'instance d'origine à son « noyau dur », une instance peut-être beaucoup plus petite qui est équivalente à l'instance d'origine mais dont la taille est limitée par une fonction dans le paramètre.

FPT est fermé sous une réduction paramétrée appelée fpt-reduction , qui préserve simultanément la taille de l'instance et le paramètre.

Évidemment, FPT contient tous les problèmes calculables en temps polynomial. De plus, il contient tous les problèmes d'optimisation dans NP qui permettent un schéma d'approximation en temps polynomial (EPTAS) efficace .

Hiérarchie W

La hiérarchie W est un ensemble de classes de complexité de calcul. Un problème paramétré est dans la classe W [ i ], si chaque instance peut être transformée (en temps fpt) en un circuit combinatoire qui a une trame au plus i , tel que si et seulement s'il y a une affectation satisfaisante aux entrées qui attribue 1 à exactement k entrées. La trame est le plus grand nombre d'unités logiques avec un éventail illimité sur n'importe quel chemin d'une entrée à la sortie. Le nombre total d'unités logiques sur les chemins (appelé profondeur) doit être limité par une constante valable pour toutes les instances du problème.

Notez que et pour tous . Les classes de la hiérarchie W sont également fermées sous fpt-réduction.

De nombreux problèmes de calcul naturels occupent les niveaux inférieurs, W [1] et W [2].

W [1]

Des exemples de problèmes W [1]-complets incluent

  • décider si un graphe donné contient une clique de taille k
  • décider si un graphe donné contient un ensemble indépendant de taille k
  • décider si une machine de Turing à bande unique non déterministe donnée accepte en k étapes (problème d'acceptation de la machine de Turing courte). Cela s'applique également aux machines de Turing non déterministes avec des bandes f ( k ) et même des bandes f ( k ) de dimensions f ( k ), mais même avec cette extension, la restriction à la taille de l'alphabet de la bande f ( k ) est traitable à paramètres fixes. De manière cruciale, le branchement de la machine de Turing à chaque étape peut dépendre de n , la taille de l'entrée. De cette façon, la machine de Turing peut explorer n O( k ) chemins de calcul.

W [2]

Des exemples de problèmes W [2]-complets incluent

  • décider si un graphe donné contient un ensemble dominant de taille k
  • décider si une machine de Turing multi-bandes non déterministe donnée accepte en k étapes (problème d'acceptation de la machine de Turing multi-bandes courte). De manière cruciale, le branchement est autorisé à dépendre de n (comme la variante W[1]), tout comme le nombre de bandes. Une autre formulation W [2]-complète n'autorise que les machines de Turing à une seule bande, mais la taille de l'alphabet peut dépendre de n .

W [ t ]

peut être défini à l'aide de la famille de problèmes SAT de trame pondérée- t- profondeur- d pour : est la classe de problèmes paramétrés qui fpt-réduit à ce problème, et .

Ici, Weighted Weft- t -Profondeur- d SAT est le problème suivant :

  • Entrée : Une formule booléenne de profondeur au plus d et de trame au plus t , et un nombre k . La profondeur est le nombre maximal de portes sur n'importe quel chemin de la racine à une feuille, et la trame est le nombre maximal de portes de fan-in au moins trois sur n'importe quel chemin de la racine à une feuille.
  • Question : La formule a-t-elle une affectation satisfaisante du poids de Hamming exactement k ?

On peut montrer que pour le problème Weighted t -Normalize SAT est complet pour les sous-fpt-réductions. Ici, Weighted t -Normalize SAT est le problème suivant :

  • Entrée : une formule booléenne de profondeur au plus t avec une porte ET au-dessus et un nombre k .
  • Question : La formule a-t-elle une affectation satisfaisante du poids de Hamming exactement k ?

W [ P ]

W [ P ] est la classe de problèmes qui peuvent être résolus par une machine de Turing à temps non déterministe qui fait au plus des choix non déterministes dans le calcul sur (une machine de Turing k- restreinte). Flum & Grohe (2006)

On sait que FPT est contenu dans W[P], et l'inclusion est considérée comme stricte. Cependant, résoudre ce problème impliquerait une solution au problème P contre NP .

D'autres connexions à la complexité de calcul non paramétrée sont que FPT est égal à W [ P ] si et seulement si la satisfiabilité du circuit peut être décidée en temps , ou si et seulement s'il existe une fonction calculable, non décroissante et illimitée f telle que toutes les langues reconnues par un polynôme non déterministe -temps machine de Turing utilisant des choix non déterministes sont dans  P .

W [ P ] peut être considéré comme la classe de problèmes où nous avons un ensemble S de n éléments, et nous voulons trouver un sous-ensemble de taille k tel qu'une certaine propriété soit vérifiée. On peut encoder un choix sous la forme d'une liste de k entiers, stockés en binaire. Étant donné que le plus grand de ces nombres peut être n , des bits sont nécessaires pour chaque nombre. Par conséquent, le nombre total de bits est nécessaire pour coder un choix. Par conséquent, nous pouvons sélectionner un sous-ensemble avec des choix non déterministes.

XP

XP est la classe de problèmes paramétrés qui peuvent être résolus dans le temps pour une fonction calculable f . Ces problèmes sont appelés polynômes par tranches , dans le sens où chaque "tranche" de k fixe a un algorithme polynomial, bien qu'éventuellement avec un exposant différent pour chaque k. Comparez cela avec FPT, qui permet simplement un préfacteur constant différent pour chaque valeur de k. XP contient FPT, et on sait que ce confinement est strict par diagonalisation.

para-NP

para-NP est la classe de problèmes paramétrés qui peuvent être résolus par un algorithme non déterministe en temps pour une fonction calculable f . On sait que si et seulement si .

Un problème est para-NP-difficile s'il l'est déjà pour une valeur constante du paramètre. C'est-à-dire qu'il existe une "tranche" de k fixe qui est -difficile. Un problème paramétré qui est -difficile ne peut pas appartenir à la classe , à moins que . Un exemple classique de problème paramétré -difficile est la coloration de graphe , paramétrée par le nombre k de couleurs, qui est déjà -difficile pour (voir Coloration de graphe#Computational complexity ).

Une hiérarchie

La hiérarchie A est un ensemble de classes de complexité de calcul similaire à la hiérarchie W. Cependant, alors que la hiérarchie W est une hiérarchie contenue dans NP, la hiérarchie A imite plus étroitement la hiérarchie en temps polynomial de la complexité classique. On sait que A[1] = W[1] est vérifié.

Remarques

  1. ^ Chen, Kanj et Xia 2006
  2. ^ Grohe (1999)
  3. ^ Buss, Jonathan F, Islam, Tarique (2006). "Simplifier la hiérarchie de trame" . Informatique théorique . 351 (3) : 303-313. doi : 10.1016/j.tcs.2005.10.002 .CS1 maint : plusieurs noms : liste des auteurs ( lien )
  4. ^ Flum et Grohe , p. 39.

Les références

Liens externes