2つのNP完全問題A,Bの等価性を示す場合、前提として使っていいのは A が NP 完全問題であるということだけです。 その上で、一番重要な部分は A≦Bを示す還元のアルゴリズムですが、当然 B≦Aにも言及しなくてはなりません。
B≦Aを示すには、その還元を示すのではなく、 BがNPに含まれることと、 A がNP完全問題であるという前提を使います。 AがNP完全問題であれば、任意の NPに含まれる問題は A に還元可能なので、B がNPに含まれれば B≦Aが成立します。
BがNPに含まれることを示すには、Bを解く非決定性の多項式時間プログラ ムを示せば良いです。 この辺は授業中にさらっと言っていて、プログラムとして書いたのはちょっと だけだと思うのですが、今回の課題では、レポートに記載している人はいませ んでした。
後、一人NPに含まれる2つの問題で一方の還元C≦Dができないという主張 をしていた人がいましたが、これが一つでも示せればミレニアム問題 P=NP? が解決することになります。どこがおかしいか見直してみてください。
決定性多項式時間で解けるすべての問題は、多項式時間で相互に還元可能 です。
例えば、数列中に最大値が2個含まれるか判定する問題を、数が偶数か どうかを判定する問題に還元する場合、与えられた数列について、 「最大値が2個含まれていれば2を出力して、それ以外は1を出力する」 プログラムは多項式時間で実行できますので、還元できています。
逆に対しても、与えられた数に対して「与えられた数が偶数なら{1,1} を出力して、それ以外は{1,2}を出力する」プログラムも多項式時間で 実行できます。
つまり「多項式時間で問題を解いてしまって、答に応じて別の問題の自 明なインスタンスを出力する」プログラムで還元ができるため、すべて 等価になります。
したがって、この方針で比較をした場合に良い評価は与えられません。 そのため、別のものさしを使わないといけません。 並列計算のときに少しだけお話した log space 還元可能性は使用できますが、 log space 還元性によって P を細分化したとき、P完全な問題とそれ以外が 真に複雑度が違うかどうかは未解決問題です。 授業であまり触れてないだけ難易度は高いです。
2つの問題A,Bをそれを解くプログラムPAとPBの計算時間で比較するのの何がだめか というと、PAがAの最速のプログラムとは限らないからです。 もっと高速なプログラムが出てこないことが証明されていない限りは、現 状知られているプログラムPA,PBの存在はたまたまそうだというだけにな ります。
また、「特定のプログラムが作れない」という説明は一般的にとても困難 です。 基本は背理法で「もしそのプログラムが存在したら矛盾する」という証明 をします。 三段論法で「Aを作るにはBが必要だがそれがないから無理」は、ただ「A が作れない」を「AにはBが必要」に言い換えているだけなので、「Bが無 くて作ったプログラムが存在すると矛盾する」ような証明が必要になりま す。
プログラムPと特定の入力Iに対して特定の出力を出す問題について、別の 問題に還元する場合、使えるのはPとIです。 出力の制限をしていなくて、 「P(I)=1ならyes, それ以外が no」 のとき 「P(I)=2 ならyes, それ以外が no 」の問題には自動的に還元できません。 P(I)=1のとき P'(I)=2 が出るように還元してしまうと、元々P(I')=2とな り no となっていた入力I'に対して P'(I')=2となるため、 yes になって しまいます。
いずれにしろ、すべてのレポートに関して満点はつけてませんので、各自、 見直し、振り返り等をしてみてください。