スーパーマリオブラザーズは難しい、なぜなら複雑性クラスがPSPACEだから、、、とMITが発表。
というのをMIT Newsで見た。
論文はこれ。
”Super Mario Bros. is Harder/Easier than We Thought”
http://erikdemaine.org/papers/Mario_FUN2016/paper.pdf
NPだというのは前に論文みたけれど、
Classic Nintendo Games are (Computationally) Hard
https://arxiv.org/pdf/1203.1895.pdf
同じ筆者たちが今度はさらにPSPACEだって示した。
って論文にマリオの画面があるのはものすごくシュールだ。
« 113番元素のニホニウムだけじゃない！今回,115,117,118番目も名前がついた！モスコヴィウム、テネシーン、オガネッソン？おいおいウムはどこへ？ | トップページ | 6/9のすまたんでは関西マイナーグルメ特集。滋賀のカレーと和歌山のポンチ。 »
「日記・コラム・つぶやき」カテゴリの記事
- Wordleを100回やってみて正解率の分布を見た。1回目で当たる確率をpとして、2回目からはk倍ずつ確率が上がっていく(kp,k²p,k³p…）とすると、私の結果はp=0.0089, k=2.4になった。(2022.05.27)
- 高周波回路シミュレータQucsStudioを使ってみる（その５）マルチポート（４ポートだとs4pみたいな）のSパラメータデータをTouchstoneファイルに出力しようとするとExport to SnPでは2ポートになってしまう。Project→Import Dataからポート数を手で入れないと。(2022.05.24)
- 新型コロナウイルス、日本の陽性者数＆ワクチン接種者数総計をプロット＆中国、韓国、アメリカ、ドイツ、フランス、イギリスの陽性者数もプロット（5/22更新）どの国もじわじわと増加は続いている。マスクをしなくなったり油断してるからかな…(2022.05.22)
- 高周波（RF・マイクロ波・ミリ波・5G）関連ニュース2022年5月19日 IEEE Microwave Magazineで磁性体を使わない非可逆デバイス、Microwave Journalは5Gスモールセル、THz、Movanoがミリ波血圧＆血糖値計発表、三菱の3Dプリンタ衛星アンテナ、など。(2022.05.19)
- 新型コロナウイルス、日本の陽性者数＆ワクチン接種者数総計をプロット＆中国、韓国、アメリカ、ドイツ、フランス、イギリスの陽性者数もプロット（5/15更新）韓国も中国も減速だが日本はじわじわと増え続けてる。アメリカも増え始めた。(2022.05.15)
« 113番元素のニホニウムだけじゃない！今回,115,117,118番目も名前がついた！モスコヴィウム、テネシーン、オガネッソン？おいおいウムはどこへ？ | トップページ | 6/9のすまたんでは関西マイナーグルメ特集。滋賀のカレーと和歌山のポンチ。 »
コメント