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

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

コメント

コメントを書く

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

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/512682/63750418

この記事へのトラックバック一覧です: スーパーマリオブラザーズは難しい、なぜなら複雑性クラスがPSPACEだから、、、とMITが発表。:

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

無料ブログはココログ
2017年4月
            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            

最近のコメント

フォト