algorithm - A から B への還元 : 真または偽

Question

次の 2 つのステートメントがあります。決定問題 A が決定問題 B に多項式時間で還元可能であり (つまりA≤ pB)、B が NP 完全である場合、A は NP 完全でなければなりません。

と：

決定問題 B が決定問題 A (つまりB≤ pA) に多項式時間で還元可能であり、B が NP 完全である場合、A は NP 完全でなければなりません。

上記の記述のうち、正しいものはどれですか?

解説もお願いできますか？

Answer 1

最初のステートメントは false です。これは、B を解いてから多項式時間アルゴリズムを適用することで A を解くことができることを意味しますが、B を解く必要のない A を解く別の方法があり、多項式のみである可能性があることを意味します。

2 番目のステートメントは true です。最初に A を解くことで B を解くことができ、次に多項式時間アルゴリズムを適用して B を解くことができますが、B は NP 完全であるため、A は NP 完全でなければなりません。