山下(Seamless) 2014年から幅広い分野の研究論文をピックアップして解説しているメディア「Seamless」を個人運営。 X(@shiropen2)でも更新情報を発信中。 @shiropen2 Seamless(シームレス) 著者記事一覧 米MIT Hardness Groupに所属する研究者らが発表した論文「Tetris is Hard with Just One Piece Type」は、降ってくるブロックが1種類に制限された『テトリス』の計算複雑性を分析した研究報告である。 ▲ブロック1種類だけのテトリスのイラスト(絵:おね) ほとんどのミノで「NP困難」 テトリスは7種のテトロミノ(テトリミノ、I・J・L・O・S・T・Z)で構成されるパズルゲームだが、コンピュータサイエンスにおける計算複雑性の研究対象としても扱われる。この種の研究では、初期の盤面状態とこれから落ちてくるピ

