レポート講評

以下の基準で採点しました。

1. 2つの問題がとりあえず比べられていた 60点
2. 片方向の難易度だけ比べられていた 70点

認められない手法

1. 最速の保証がされてないプログラムのスピードを、その問題の 難しさとして扱って比較すること。 プログラマーの腕の悪さを問題の難しさに転嫁するのは良くないです。 とりあえず解いてみた方法が遅かったとか、 適当に書いたプログラムが遅かったとか、そういう比較は無意味です。
2. NP完全問題の知識を使って、NP完全問題の各問題が等価であるというこ と
3. 還元可能性を概要で説明して、明確なアルゴリズムとして示してない。 問題で求めている答をぼかしている場合、採点の対象にはなりません。
4. シナリオ潰しによる難易度の主張。 つまり、ある問題Aを解くのに、ある問題Bを解かないといけないので、 $B\le A$ という主張。 これは考え方がおかしいです。 「解かないといけない」は証明が必須です。 これを数学的に主張するには、Aのソルバーがあったとき、結局その内 部で B を解いている部分が抽出できるため、Aのソルバー を改造するとBのソルバーが作れることを示せるということです。 つまり、Aのソルバーを使っ たBを解くプログラムを示す必要があります。

今回は質の悪い解答が出回ってしまって、皆さん共倒れという感じになり、 残念です。 良い点数の人は一人もいませんでした。 問題の比較をするには、ベンチマークテストではだめで、 還元可能性を使うというのを毎回のように主張してきましたが、 ほとんど伝わって無くて残念です。