Уменьшение от A до B: верно или неверно

Question

Есть два утверждения: если задача решения A сводится за полиномиальное время к решению проблемы B (т.е. A≤ pB), и B является NP-полным, тогда A должно быть NP-полным.

А также:

Если задача решения B сводится за полиномиальное время к решению проблемы A (т.е. B≤ pA), и B является NP-полным, тогда A должно быть NP-полным.

Какие из приведенных выше утверждений являются правдой?

Можете ли вы также дать объяснение?

Answer 1

Первое утверждение неверно, потому что это означает, что, решая B, а затем применяя некоторый алгоритм полиномиального времени, вы можете решить A, но, возможно, есть другой способ решения A, который не требует решения B и, возможно, это только полиномиальное.

второе утверждение верно, потому что это означает, что вы можете решить B, сначала решив A, а затем применив некоторый алгоритм за полиномиальное время для решения B, но B является NP-полным, поэтому A должно быть NP-полным