Étant donné que A réduit à B dans $ o (n ^ 2) $ et b est résoluble dans $ o (n ^ 3) $, résolvez un

Question

Supposons qu'un problème A réduit au problème B et que la réduction se fait en $ O (n ^ 2) $ temps.

Si le problème B est résolu dans $ O (n ^ 3) $ Le temps alors qu'en est-il de la complexité du temps du problème A?

Approcher:

A est réduit à b. Ici, la réduction se fait au temps polynomial. Ici, B est résolu en temps polynomial. Ainsi, A devrait également être en temps polynomial.

Maintenant un ne peut pas être plus difficile que b, donc je pense que A peut être $ O (n ^ 3) $ ou $ O (n ^ 2) $. Mais logiquement si j'ai réduit A à B et si b est $ O (n ^ 3) $ alors cela n'a aucun sens pour un $ O (n ^ 2) $, sinon pourquoi le réduirais-je à une complexité plus élevée? Donc a est $ O (n ^ 3) $.

Mais mon doute est que nous disons que lors de la réduction que A ne peut pas être plus difficile que b, alors comment pouvons-nous décider s'il est $ O (n ^ 2) $ ou $ O (n ^ 3) $. Ou cet argument est-il uniquement valable pour les classes de problème P, NP quand je dis que A ne peut pas être plus difficile que B ou B doit être au moins aussi difficile qu'un?

La réponse donnée est "a est $ O (n ^ 3) $", Mais pourquoi ne peut-il pas être $ O (n ^ 2) $ comme "A ne peut pas être plus difficile que B" mais peut être d'une complexité égale? Ou la réductibilité est-elle juste un argument pour les classes de complexité?

Expliquez si possible comment la réduction fonctionne réellement et pourquoi je ne pouvais pas l'appliquer à mon problème.