« 113番元素のニホニウムだけじゃない!今回,115,117,118番目も名前がついた!モスコヴィウム、テネシーン、オガネッソン?おいおいウムはどこへ? | トップページ | 6/9のすまたんでは関西マイナーグルメ特集。滋賀のカレーと和歌山のポンチ。 »

2016年6月 9日 (木)

スーパーマリオブラザーズは難しい、なぜなら複雑性クラスがPSPACEだから、、、とMITが発表。

“Super Mario Brothers” is hard - Analysis shows popular video game is among the hardest problems in the “complexity class” PSPACE.

というのを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のすまたんでは関西マイナーグルメ特集。滋賀のカレーと和歌山のポンチ。 »

日記・コラム・つぶやき」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

« 113番元素のニホニウムだけじゃない!今回,115,117,118番目も名前がついた!モスコヴィウム、テネシーン、オガネッソン?おいおいウムはどこへ? | トップページ | 6/9のすまたんでは関西マイナーグルメ特集。滋賀のカレーと和歌山のポンチ。 »

最近の記事

最近のコメント

2023年3月
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  
フォト
無料ブログはココログ