Qu'est-ce que l'explication intuitive de «réduction de A à B»?

Question

J'étudie maintenant la théorie de la complexité et je viens de répondre à une «réduction de cartographie». Je comprends la «réduction du temps polynomial de A à B» comme «Si on peut résoudre B et avoir un temps polynomial, on peut résoudre A». (Ai-je raison?)

Il implique problème A n'est pas plus difficile que (avec le temps polynomiale) B.

Ensuite, ce qui est réduit de A à B? Comment puis-je comprendre le mot «réduction»?

Answer 1

Supposons que le problème A est «d'avoir une tasse de café». Il y a plusieurs façons de résoudre ce problème, qui dépend de ce que vous avez déjà:

• Mettez-vous dans votre voiture, aller au magasin, acheter un bug de café, une machine à café et une tasse, se la maison, la puissance de votre nouvelle machine, obtenir de l'eau, moudre le café etc.
• Acheter une voiture, puis voir ci-dessus
• obtenir une carte de crédit, allez à Amazon, trouver une machine à café, commander, trouver une tasse à la maison, lavez-le, etc.
• Demander une carte de crédit, attendez, puis voyez ci-dessus
• Aller au Starbucks, commander un café, attendez un siège, etc

Dans tous ces cas, vous avez a réduit votre problème à une séquence d'étapes connues (sous-problèmes). Si vous savez, comment résoudre ces sous-problèmes dans un délai raisonnable, et leur nombre n'est pas trop grand, alors vous pouvez résoudre votre problème dans un délai raisonnable.

Profitez de votre tasse de café!