エントリーの編集
![loading...](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/common/loading@2x.gif)
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
![アプリのスクリーンショット](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/entry/app-screenshot.png)
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
立体ピクロスの計算量解析
概要 立体ピクロスは任天堂が2009年に発売したゲームです[1]。 我々は計算機が立体ピクロスを解くことが... 概要 立体ピクロスは任天堂が2009年に発売したゲームです[1]。 我々は計算機が立体ピクロスを解くことがどのくらい難しいかを解析し、 立体ピクロスの解の存在判定がNP完全である(立体ピクロスを解くことはとても難しい)ことを証明しました[2]。 通常のピクロスの解の存在判定や[3]、 サイズを一般化しNEXTぷよが全て見えている「ぷよぷよ」で全消しが可能か判定する問題[4]などがNP完全である(立体ピクロスと同程度に難しい)ことが知られています。 立体ピクロスの問題と解 NP完全 「与えられた配列を昇順に並べ替える」「迷路の最短経路を探す」「画像に書かれている文字を読み取る」など計算機が解く種々の問題があります。 このうち答えが「はい」か「いいえ」であるものを判定問題と言います。 「与えられた立体ピクロスを解け」は判定問題ではありませんが、「与えられた立体ピクロスは解を持つか?」は判定問題