ssertsidniandim のコメント

定理: 一般化されたスーパーマリオブラザーズにおいて、ステージのスタートからゴールまで辿り着くことが可能かどうか判定するのはNP完全問題である。

つまりステージをランダム生成したスーパーマリオブラザーズがゴールできるか判定するには計算量がすごく大きくなる(もしくは解けない)ことを示しただけ
こういう話題を親しみやすい例で示してくれるのはありがたいが、適当なことを書くのはやめていただきたい

No.7 129ヶ月前

このコメントは以下の記事についています

コタク・ジャパンチャンネル

コタク・ジャパンチャンネル

このチャンネルの詳細