Worldlex Wiki En informatique , la complexité paramétrée est une branche de la théorie de la complexité algorithmique qui vise à classer les problèmes de calcul selon leur difficulté intrinsèque par rapport à de multiples paramètres d'entrée ou de sortie. La complexité d'un problème est alors mesurée en fonction de ces paramètres. Ceci permet une classification plus fine des problèmes NP-difficiles que dans le cadre classique, où la complexité est uniquement mesurée en fonction du nombre de bits en entrée. Cette approche semble avoir été démontrée pour la première fois par NP-complets , ou NP-difficiles , est considérée comme improbable si les paramètres d'entrée ne sont pas fixés ; tous les algorithmes de résolution connus pour ces problèmes ont une complexité temporelle exponentielle (donc superpolynomiale) par rapport à la taille totale des données d'entrée. Cependant, certains problèmes peuvent être résolus par des algorithmes dont la complexité temporelle est exponentielle uniquement par rapport à la taille d'un paramètre fixe, et polynomiale par rapport à la taille totale des données d'entrée.
Sous l'hypothèse que P ≠ NP , il existe de nombreux problèmes naturels dont la complexité, mesurée uniquement par la taille de l'entrée, est supérieure à la complexité polynomiale, mais qui sont calculables en un temps polynomial par rapport à la taille de l'entrée et exponentiel, voire pire, par rapport à un paramètre k paramètre fixe traitable (FPT), car le problème peut être résolu efficacement (c'est-à-dire en temps polynomial) pour des valeurs constantes du paramètre fixe. Un problème paramétré admettant un tel algorithme FPT est dit à paramètre fixe traitable et appartient à la classe entier non négatif problème de couverture de sommets , le paramètre peut être le nombre de sommets de la couverture. Le problème de couverture de sommets minimale consiste à :
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 des données d'entrée. Il est alors difficile de trouver un algorithme dont la complexité soit exponentielle uniquement en
XP
XP est la classe des problèmes paramétrés qui peuvent être résolus en temps pour une fonction calculable
Un problème est para-NP-difficile s'il est déjà NP-difficile pour une valeur constante du paramètre. Autrement dit, il existe une « tranche » de valeurs de la coloration de graphes , paramétrée par le nombre Coloration de graphes#Complexité computationnelle ).
Hiérarchies
complexité. Chaque classe est fermée par réduction fpt. Les plus importantes sont la hiérarchie W et la hiérarchie A. ]
Définitions préliminaires
De manière générale, on peut définir une classe de complexité de deux façons : du point de vue de la théorie des machines et du point de vue logique. En théorie des machines, une classe est définie comme l’ensemble des problèmes de décision résolubles par une classe de machines. En logique, une classe est définie comme l’ensemble des problèmes de décision définissables par une classe de formules logiques.
circuits booléens
Le poids de Hamming ( ou poids en abrégé) d'une chaîne binaire est le nombre de 1 qui y apparaissent.
Un circuit booléen est un graphe orienté acyclique dont les nœuds représentent les portes logiques ET, OU ou NON. Une petite porte est une porte dont le nombre d'entrées est de 0, 1 ou 2. Les autres portes sont dites grandes. La trame correspond au nombre maximal de grandes portes réalisables sur un chemin quelconque entre une entrée et la sortie. La profondeur correspond au nombre maximal de portes (petites ou grandes) réalisables sur un chemin quelconque entre une entrée et la sortie. Par définition, trame ≤ profondeur.
Un circuit booléen est monotone s'il n'utilise aucune porte NON. Un circuit booléen est antimonotone s'il est de la forme où représentent toutes ses entrées, et est monotone.
Théorie des modèles finis
Étant donné que :
Nous définissons comme le problème de vérification de modèle paramétré pour ce tuple. Chaque instance du problème est :
- Entrée : et un modèle fini pour le langage
- Paramètre:
- Résultat :
Une formule est de la forme , de sorte que les quantificateurs alternent entre existence et pour tout, et que la formule à l'intérieur est sans quantificateur (c'est-à-dire écrite uniquement avec des variables, des connecteurs booléens et des relations) .
Une formule est de la forme , avec la condition supplémentaire que .
Définition
Du point de vue de la théorie des machines, un problème paramétré appartient à la classe W[w][d] s'il existe une réduction fpt du problème comme suit :
- Il existe des entiers constants tels que
- chaque instance est transformée en temps fpt en un circuit booléen qui a une trame d'au plus w et une profondeur d'au plus d .
Ici, « W » signifie « poids ». Notez que dans la définition ci-dessus, les valeurs de sont indépendantes de , mais le circuit lui-même dépend de , et peut changer si l’on modifie soit , soit .
La classe W[w] est alors définie comme leur union : Plus succinctement, W[w] est l'ensemble des problèmes fpt-réductibles à une famille de circuits booléens spécifiques à l'instance avec trame et profondeur limitées par une constante spécifique au problème.
Un circuit normalisé de trame w et de profondeur d est un circuit dont les premières couches ne contiennent que des portes logiques simples, et les dernières couches contiennent une alternance de grandes portes logiques ET et OU. On peut itérer les lois d'associativité et les lois de distribution de de Morgan pour normaliser le circuit en temps fpt. Par conséquent, sans perte de généralité, on ne peut considérer que des circuits normalisés.
Du point de vue de la théorie des modèles, la classe W[t] est définie comme la classe des problèmes fpt-réductibles à .
Alors que la hiérarchie W est une hiérarchie incluse dans NP, la hiérarchie A imite plus fidèlement la hiérarchie polynomiale de la complexité classique. Du point de vue de la théorie des machines, les problèmes de la hiérarchie A sont définis comme des problèmes fpt-réductibles à des calculs effectués par certains types de machines de Turing alternées . Le « A » signifie « alternées ».
Du point de vue de la théorie des modèles, la classe A[t] est définie comme la classe des problèmes fpt-réductibles à .
Par exemple, le problème des k -claques peut être formulé comme un problème de vérification de modèles. Le langage possède une unique relation binaire , où signifie « partager une arête ». Alors, un modèle fini est un graphe, et il possède une k -clique si et seulement si . Ceci montre que le problème des k -claques appartient à .
Un problème est A[i] -complet s'il est A[i] et si tout problème A[i] se réduit à lui par fpt.
Propriétés de base
Par définition, :
W[1]
W[2]
Les problèmes W[2] sont intuitivement de la forme : devinez un objet de taille k , effectuez un traitement local sur l'objet, puis effectuez un traitement global.
Exemples de problèmes W [2]-complets :
- décider si un graphe donné contient un ensemble dominant de taille k.
- Il s'agit de déterminer si une machine de Turing multi-bandes non déterministe donnée accepte une opération en k étapes (« problème d'acceptation de machine de Turing multi-bandes courte »). Point crucial, le branchement peut dépendre de n (comme dans la variante W[1]), de même que le nombre de bandes. Une formulation alternative 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 .
Le problème de l'ensemble dominant a pour formule .
W[i]
Certains problèmes sont connus pour être W[i] -complets, bien qu'ils soient sous une forme générique du point de vue du calcul, et sont généralement étudiés dans le cadre de la théorie de la complexité paramétrée elle-même. Empiriquement, en 2013, presque tous les problèmes paramétrés naturels étudiés se sont révélés être W[0] -complets, W[1] -complets ou W[2] -complets. Les suivants sont généralement utilisés :
- Satisfiabilité i -normalisée pondérée : Étant donné une formule booléenne, écrite comme un ET de OU de ET de ... de variables éventuellement négatives, avec des couches de ET ou OU alternés, peut-elle être satisfaite en fixant exactement k variables à 1 ?
- Si i>0 est pair, alors
- La satisfaisabilité normalisée monotone pondérée i est W[i] -complète.
- La satisfaisabilité normalisée monotone pondérée (i+1) se trouve dans W[i] .
- Si i>0 est impair, alors
- La satisfaisabilité normalisée i de l'Antionotone pondéré est W[i] -complète.
- Si , alors la satisfaisabilité antimonotone pondérée (i+1) -normalisée est dans W[i] .
Ces problèmes sont essentiellement « artificiels », en ce sens qu'ils ne sont étudiés que dans le contexte de la complexité paramétrée. La littérature recense peu de problèmes naturels qui sont W[i] -complets pour :
- La détection des dépendances d'inclusion dans les bases de données relationnelles est W[3] -complète.
- Certains problèmes dans les modèles de chaîne d'approvisionnement sont W[3] -complets ou W[4] -complets.
W[SAM]
W[SAT] est la classe de problèmes fpt-réductibles à des problèmes SAT pondérés :
- Entrée : une formule booléenne
- Paramètre : k
- Résultat : Indique si la formule possède une affectation satisfaisante de poids k .
Il contient tous les W[t] .
W [ P ]
W[P] est la classe de problèmes fpt-réductibles au problème des problèmes de circuits booléens pondérés :
- Entrée : un circuit booléen
- Paramètre : k
- Sortie : Indique s'il existe une entrée de poids k telle que le circuit produise la valeur Vrai.
Elle contient W[SAT] , car une formule booléenne peut être efficacement convertie en un circuit booléen. Notez que l'inverse n'est pas vrai en général, car la formule booléenne équivalente à un circuit booléen peut être nécessairement exponentiellement plus grande que le circuit.
De manière équivalente, il s'agit de la classe des problèmes qui peuvent être résolus par une machine de Turing non déterministe en temps k qui effectue au plus k choix non déterministes dans le calcul sur (une machine de Turing k -restreinte).
On sait que FPT est inclus dans W[P], et cette inclusion est considérée comme stricte. Cependant, résoudre ce problème impliquerait de résoudre le problème P versus NP .
D'autres liens avec la complexité de calcul non paramétrée sont que FPT est égal à W [ P ] si et seulement si la satisfaisabilité du circuit peut être décidée en temps , ou si et seulement s'il existe une fonction calculable, non décroissante et non bornée f telle que tous les langages reconnus par une machine de Turing non déterministe en temps polynomial utilisant
On peut concevoir W [ P ] comme la classe des problèmes où, étant donné un ensemble
Autres classes
La hiérarchie W* est similaire à la hiérarchie W , mais elle paramétrise la profondeur au lieu de la maintenir constante. La classe W*[t] est définie comme la classe des problèmes fpt-réductibles à ce problème :
- Entrée : un circuit booléen de trame au plus t et de profondeur au plus k .
- Paramètre : k
- Sortie : Indique si le circuit booléen possède une affectation satisfaisante de poids k .
Elle est liée à W par : La hiérarchie AW est obtenue en ajoutant l’alternance à la hiérarchie W. La classe AW[t] est définie comme la classe des problèmes fpt-réductibles à ce problème :
- Entrée : un circuit booléen de trame d’au plus t , et une partition de ses entrées à
- Paramètre:
- Sortie : Indique si le circuit booléen est satisfaisable sous des conditions de pondération alternées.
Le poids alterné est défini comme suit :
- Il existe un sous-ensemble de taille , tel que si nous attribuons exactement la valeur Vrai à ces entrées et la valeur Faux aux autres, alors,
- pour tout sous-ensemble de taille , tel que si nous attribuons exactement ces entrées à Vrai et les autres à Faux, alors,
- ...
- Le circuit booléen renvoie la valeur Vrai.
On peut interpréter cela comme un jeu à deux joueurs : le premier joueur tente de faire en sorte que la sortie du circuit soit vraie, et le second joueur tente de la faire en sorte qu'elle soit fausse. Le premier joueur agit en mettant exactement les entrées à vrai et les autres à faux, puis le second joueur agit sur , et ainsi de suite. Le circuit est soumis à des conditions de pondération alternées si et seulement si le joueur 1 possède une stratégie gagnante.
Il s'avère que la hiérarchie s'effondre : . Ainsi, la littérature n'utilise qu'un symbole commun pour les désigner : .