スーパーマリオブラザーズは難しい、なぜなら複雑性クラスが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のすまたんでは関西マイナーグルメ特集。滋賀のカレーと和歌山のポンチ。 »
「日記・コラム・つぶやき」カテゴリの記事
- 地球と月の間の万有引力より太陽と月の間の万有引力の方が強いのか！知らなかった、、、(2021.05.05)
- 新型コロナウイルス、中国、日本、韓国、アメリカ、ドイツ、フランス、イギリスでの感染者数を指数関数＆ロジスティック関数＆Log-Logプロットでべき関数フィッティングした（5/2更新） 日本は第4波が進行中、他の国もイギリスを除いて増加している。 (2021.05.03)
- AppleのUWB利用を忘れものタグ（位置タグ) AirTagの分解（iFixitの写真を解説、5/4追記）(2021.05.02)
- 万有引力と重力、そしてそのエネルギーをちゃんと地球のスケールでグラフ化したらわかるのでは（ひろゆきが位置エネルギーが存在しないといったことに対して）(2021.04.30)
- 新型コロナウイルス、中国、日本、韓国、アメリカ、ドイツ、フランス、イギリスでの感染者数を指数関数＆ロジスティック関数＆Log-Logプロットでべき関数フィッティングした（4/25更新） 日本は完全に第4波なので色を変えて表示。フランスもワクチン接種進んでいるはずなのに全然減らない。(2021.04.26)
« 113番元素のニホニウムだけじゃない！今回,115,117,118番目も名前がついた！モスコヴィウム、テネシーン、オガネッソン？おいおいウムはどこへ？ | トップページ | 6/9のすまたんでは関西マイナーグルメ特集。滋賀のカレーと和歌山のポンチ。 »
コメント