Problème de fonctionnement

En théorie de la complexité algorithmique , un problème de fonction est un problème de calcul où une seule sortie est attendue pour chaque entrée, mais cette sortie est plus complexe que celle d'un problème de décision . Pour les problèmes de fonction, la sortie n'est pas simplement « oui » ou « non ».

Le problème de satisfaisabilité booléenne fonctionnelle, ou FSAT , est un problème fonctionnel bien connu . Ce problème, étroitement lié au problème de décision SAT , peut être formulé comme suit :

Étant donné une formule propositionnelle avec des variables , trouvez une affectation telle que soit évaluée à ou décidez qu'une telle affectation n'existe pas.

Dans ce cas, la relation est définie par des paires de formules propositionnelles et d'affectations satisfaisantes, correctement encodées. Alors qu'un algorithme SAT, alimenté par une formule , doit seulement renvoyer « insatisfaisable » ou « satisfaisable », un algorithme FSAT doit, dans ce dernier cas, renvoyer une affectation satisfaisante.

Parmi les autres exemples notables, citons le problème du voyageur de commerce , qui consiste à déterminer l'itinéraire emprunté par le voyageur, et le problème de la factorisation des entiers , qui consiste à fournir la liste des facteurs.

Considérons un problème de décision quelconque appartenant à la classe NP . Par définition de NP , il existe un système de certificats tel que chaque instance du problème à laquelle on répond « oui » possède un certificat de taille polynomiale servant de preuve de cette réponse (les instances auxquelles on répond « non » ne possèdent pas de tel certificat). L'ensemble de ces paires forme ainsi une relation, représentant le problème fonctionnel « étant donné dans , trouver un certificat pour ». Ce problème fonctionnel est appelé une variante fonctionnelle de ; il appartient à la classe FNP .

Inversement, chaque problème R dans FNP induit un problème de décision correspondant (unique) : étant donné x , décider s'il existe un y tel que R ( x , y ) soit vrai.

La classe FNP peut être vue comme l'analogue de la classe NP pour les fonctions , en ce sens que les solutions des problèmes FNP peuvent être vérifiées efficacement (c'est-à-dire en temps polynomial par rapport à la longueur de l'entrée) , mais pas nécessairement trouvées efficacement . En revanche, la classe FP , que l'on peut voir comme l'analogue de la classe P pour les fonctions , est constituée de problèmes fonctionnels dont les solutions peuvent être trouvées en temps polynomial.

On remarque que le problème FSAT introduit ci-dessus peut être résolu en un nombre polynomial d'appels à une sous-routine qui résout le problème SAT : un algorithme peut d'abord vérifier si la formule est satisfaisable. Ensuite, il peut fixer la variable à VRAI et vérifier à nouveau. Si la formule résultante est toujours satisfaisable, l'algorithme maintient la variable à VRAI et continue de la fixer ; sinon, il décide que la variable doit être FAUX et poursuit son exécution. Ainsi, FSAT est résoluble en temps polynomial à l'aide d'un oracle qui détermine le problème SAT . De manière générale, un problème de FNP est dit auto-réductible s'il peut être résolu en temps polynomial à l'aide d'un oracle pour son problème de décision induit. Toute variante fonctionnelle de tout problème NP-complet est auto-réductible. Il existe plusieurs notions (légèrement différentes) d'auto-réductibilité.

Les problèmes de fonctions peuvent être réduits de manière similaire aux problèmes de décision : étant donné des problèmes de fonctions et , on dit que se réduit à s'il existe des fonctions et calculables en temps polynomial telles que, pour toutes les instances de et solutions possibles de , on a .

• Si possède une -solution, alors possède une -solution.

Il est donc possible de définir des problèmes FNP-difficiles analogues aux problèmes NP-difficiles :

Un problème est FNP-difficile si tout problème de FNP peut être réduit à . Un problème est FNP-complet s'il est FNP-difficile et appartient à FNP . Le problème FSAT est un problème FNP-complet, et par conséquent, par auto-réductibilité de FSAT, on a si et seulement si .

La relation utilisée pour définir les problèmes de fonctions présente l'inconvénient d'être potentiellement incomplète : toutes les entrées n'ont pas nécessairement de contrepartie telle que . Par conséquent, la question de la calculabilité des sorties n'est pas dissociée de celle de leur existence. Pour pallier ce problème, il est commode de restreindre les problèmes de fonctions aux relations totales, ce qui donne la classe TFNP comme sous-classe de FNP . Cette classe comprend des problèmes tels que le calcul des équilibres de Nash purs dans certains jeux stratégiques où l'existence d'une solution est garantie. De plus, si TFNP contient un problème FNP-complet, alors s'ensuit que .