Réduction (complexité) - Reduction (complexity)

Exemple d'une réduction du problème de satisfaisabilité booléenne ( A ∨ B ) ∧ (¬ A ∨ ¬ B ∨ ¬ C ) ∧ (¬ A ∨ B ∨ C ) à un problème de recouvrement de sommet . Les sommets bleus forment une couverture de sommets minimale, et les sommets bleus dans l'ovale gris correspondent à une affectation de vérité satisfaisante pour la formule originale.

Dans la théorie de la calculabilité et la théorie de la complexité computationnelle , une réduction est un algorithme pour transformer un problème en un autre problème. Une réduction suffisamment efficace d'un problème à un autre peut être utilisée pour montrer que le deuxième problème est au moins aussi difficile que le premier.

Intuitivement, le problème A est réductible au problème B , si un algorithme pour résoudre efficacement le problème B (s'il existait) pouvait également être utilisé comme sous-programme pour résoudre efficacement le problème A. Lorsque cela est vrai, résoudre A ne peut pas être plus difficile que résoudre B . "Plus difficile" signifie avoir une estimation plus élevée des ressources de calcul requises dans un contexte donné (par exemple, une complexité temporelle plus élevée , une plus grande exigence de mémoire, un besoin coûteux de cœurs de processeur matériels supplémentaires pour une solution parallèle par rapport à une solution monothread, etc.) . L'existence d'une réduction de A à B , peut être écrite dans la notation abrégée A ≤ m B , généralement avec un indice sur le pour indiquer le type de réduction utilisé (m : mapping reduction , p : réduction polynomiale ).

La structure mathématique générée sur un ensemble de problèmes par les réductions d'un type particulier forme généralement un préordre , dont les classes d'équivalence peuvent être utilisées pour définir des degrés d'insolvabilité et des classes de complexité .

introduction

Il y a deux situations principales où nous devons utiliser des réductions :

  • Premièrement, nous nous trouvons en train d'essayer de résoudre un problème similaire à un problème que nous avons déjà résolu. Dans ces cas, souvent un moyen rapide de résoudre le nouveau problème est de transformer chaque instance du nouveau problème en instances de l'ancien problème, de les résoudre en utilisant notre solution existante, puis de les utiliser pour obtenir notre solution finale. C'est peut-être l'utilisation la plus évidente des réductions.
  • Deuxièmement : supposons que nous ayons un problème dont nous avons prouvé qu'il est difficile à résoudre, et que nous ayons un nouveau problème similaire. On peut penser qu'il est également difficile à résoudre. Nous argumentons par contradiction : supposons que le nouveau problème soit facile à résoudre. Alors, si nous pouvons montrer que chaque instance de l'ancien problème peut être résolue facilement en la transformant en instances du nouveau problème et en les résolvant, nous avons une contradiction. Cela établit que le nouveau problème est également difficile.

Un exemple très simple d'une réduction est de la multiplication au carré . Supposons que tout ce que nous savons faire soit d'additionner, de soustraire, de prendre des carrés et de diviser par deux. Nous pouvons utiliser cette connaissance, combinée avec la formule suivante, pour obtenir le produit de deux nombres quelconques :

Nous avons aussi une réduction dans l'autre sens; évidemment, si nous pouvons multiplier deux nombres, nous pouvons mettre un nombre au carré. Cela semble impliquer que ces deux problèmes sont également difficiles. Ce type de réduction correspond à la réduction de Turing .

Cependant, la réduction devient beaucoup plus difficile si nous ajoutons la restriction que nous ne pouvons utiliser la fonction de mise au carré qu'une seule fois, et seulement à la fin. Dans ce cas, même si nous sommes autorisés à utiliser toutes les opérations arithmétiques de base, y compris la multiplication, aucune réduction n'existe en général, car pour obtenir le résultat souhaité sous forme de carré, nous devons d'abord calculer sa racine carrée, et ce carré racine pourrait être un nombre irrationnel comme celui qui ne peut pas être construit par des opérations arithmétiques sur des nombres rationnels. En allant dans l'autre sens, cependant, nous pouvons certainement mettre un nombre au carré avec une seule multiplication, seulement à la fin. En utilisant cette forme limitée de réduction, nous avons montré le résultat sans surprise que la multiplication est en général plus difficile que la quadrature. Cela correspond à une réduction multiple .

Propriétés

Une réduction est un préordre , qui est réfléchi et relation transitive , sur P ( N ) × P ( N ), où P ( N ) est la consigne de puissance des nombres naturels .

Types et applications des réductions

Comme décrit dans l'exemple ci-dessus, il existe deux principaux types de réductions utilisées dans la complexité de calcul, la réduction plusieurs-un et la réduction de Turing . Les réductions à plusieurs mappent les instances d'un problème aux instances d'un autre ; Les réductions de Turing calculent la solution à un problème, en supposant que l'autre problème est facile à résoudre. La réduction à plusieurs est un type de réduction de Turing plus puissant et est plus efficace pour séparer les problèmes en classes de complexité distinctes. Cependant, les restrictions accrues sur les réductions multiples les rendent plus difficiles à trouver.

Un problème est complet pour une classe de complexité si chaque problème de la classe se réduit à ce problème, et il est également dans la classe elle-même. En ce sens, le problème représente la classe, puisque toute solution de celui-ci peut, en combinaison avec les réductions, être utilisée pour résoudre tous les problèmes de la classe.

Cependant, pour être utiles, les réductions doivent être faciles . Par exemple, il est tout à fait possible de réduire un problème NP-complet difficile à résoudre comme le problème de satisfiabilité booléenne à un problème trivial, comme déterminer si un nombre est égal à zéro, en demandant à la machine de réduction de résoudre le problème en temps exponentiel et de sortir zéro seulement s'il y a une solution. Cependant, cela n'apporte pas grand-chose, car même si nous pouvons résoudre le nouveau problème, effectuer la réduction est tout aussi difficile que de résoudre l'ancien problème. De même, une réduction calculant une fonction non calculable peut réduire un problème indécidable à un problème décidable. Comme le souligne Michael Sipser dans Introduction to the Theory of Computation : "La réduction doit être facile, par rapport à la complexité des problèmes typiques de la classe [...] Si la réduction elle-même était difficile à calculer, une solution facile à la problème ne donnerait pas nécessairement une solution facile aux problèmes qui s'y réduisent."

Par conséquent, la notion appropriée de réduction dépend de la classe de complexité étudiée. Lors de l'étude de la classe de complexité NP et des classes plus difficiles telles que la hiérarchie polynomiale , des réductions en temps polynomial sont utilisées. Lors de l'étude de classes au sein de P telles que NC et NL , des réductions de l'espace log sont utilisées. Les réductions sont également utilisées dans la théorie de la calculabilité pour montrer si les problèmes peuvent ou non être résolus par des machines ; dans ce cas, les réductions sont limitées aux seules fonctions calculables .

En cas de problèmes d'optimisation (maximisation ou minimisation), on pense souvent en termes de réduction préservant l'approximation . Supposons que nous ayons deux problèmes d'optimisation tels que les instances d'un problème puissent être mappées sur les instances de l'autre, de manière à ce que des solutions presque optimales aux instances de ce dernier problème puissent être retransformées pour donner des solutions presque optimales au premier. De cette façon, si nous avons un algorithme d'optimisation (ou algorithme d'approximation ) qui trouve des solutions presque optimales (ou optimales) aux instances du problème B, et une réduction efficace préservant l'approximation du problème A au problème B, par composition nous obtenons une optimisation algorithme qui donne des solutions presque optimales aux instances du problème A. Les réductions préservant l'approximation sont souvent utilisées pour prouver la dureté des résultats d' approximation : si un problème d'optimisation A est difficile à approximer (sous certaines hypothèses de complexité) avec un facteur meilleur que α pour certains α, et il existe une réduction préservant l'approximation β du problème A au problème B, nous pouvons conclure que le problème B est difficile à approximer avec le facteur α/β.

Exemples

Exemple détaillé

L'exemple suivant montre comment utiliser la réduction du problème d'arrêt pour prouver qu'une langue est indécidable. Supposons que H ( M , w ) soit le problème de déterminer si une machine de Turing donnée M s'arrête (en acceptant ou en rejetant) sur la chaîne d'entrée w . Cette langue est connue pour être indécidable. Supposons que E ( M ) soit le problème de déterminer si le langage qu'une machine de Turing donnée M accepte est vide (en d'autres termes, si M accepte des chaînes du tout). On montre que E est indécidable par une réduction de H .

Pour obtenir une contradiction, supposons que R soit un décideur pour E . Nous allons l'utiliser pour produire un décideur S pour H (dont nous savons qu'il n'existe pas). Étant donné l'entrée M et w (une machine de Turing et une chaîne d'entrée), définissez S ( M , w ) avec le comportement suivant : S crée une machine de Turing N qui accepte uniquement si la chaîne d'entrée de N est w et M s'arrête sur l'entrée w , et ne s'arrête pas autrement. Le décideur S peut maintenant évaluer R ( N ) pour vérifier si le langage accepté par N est vide. Si R accepte N , alors la langue acceptée par N est vide, donc en particulier M ne s'arrête pas sur l'entrée w , donc S peut rejeter. Si R rejette N , alors la langue acceptée par N est non vide, donc M s'arrête sur l'entrée w , donc S peut accepter. Ainsi, si nous avions un décideur R pour E , nous serions capables de produire un décideur S pour le problème d'arrêt H ( M , w ) pour toute machine M et entrée w . Puisque nous savons qu'un tel S ne peut pas exister, il s'ensuit que le langage E est également indécidable.

Voir également

Les références

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction aux algorithmes, MIT Press, 2001, ISBN  978-0-262-03293-3
  • Hartley Rogers, Jr. : Théorie des fonctions récursives et calculabilité efficace, McGraw-Hill, 1967, ISBN  978-0-262-68052-3 .
  • Peter Bürgisser : Complétude et réduction de la théorie de la complexité algébrique, Springer, 2000, ISBN  978-3-540-66752-0 .
  • ER Griffor : Manuel de la théorie de la calculabilité, Hollande du Nord, 1999, ISBN  978-0-444-89882-1 .