粘菌でNP完全問題を解ける？ - 小宮日記
数日前のNHKのサイエンスゼロで「粘菌」を紹介していた。 変形菌 http://ja.wikipedia.org/wiki/%E5%A4%89%E5%BD%A2%E8%8F%8C 粘菌と言えば、風の谷のナウシカを思い出すが、番組でもナウシカに出てくることを紹介していた。 『粘菌は飢餓に陥ると1カ所に集まって胞子を作る。見た目は派手な状態＝粘菌の死を表している』 風の谷のナウシカの生命論 http://homepage3.nifty.com/mana/miyazaki-nausika-1.html 粘菌と共存しようとする王蟲、死んだように見えている時に元気で、生きているときに死に近い粘菌の3つの事象から、生と死の考え方を固めたのでしょう。↑ナウシカの元ネタの一つは「蟲めづる姫」で、それもやはり相克ですね http://yaplog.jp/kamogawani/archive/13 粘菌の研究
Complexity Zoo - Qwiki
Introduction Welcome to the Complexity Zoo... There are now 488 classes and counting! This information was originally moved from http://www.complexityzoo.com/ in August 2005, and is currently under the watchful eyes of its original creators: Zookeeper: Scott Aaronson Veterinarian: Greg Kuperberg Tour Guide: Christopher Granade Errors? Omissions? Misattributions? Your favorite class not here? The
複雑性クラス - Wikipedia
複雑性クラス一覧[編集] 以下の一覧の各複雑性クラスには補問題の集合である 'Co' の付くクラスが存在する。例えば、問題 L が NP に含まれるなら、その補問題は Co-NP に属する。 #P - NP問題の解を数える問題 #P完全 - #P の中で最も難しい問題群 AH - 算術的階層 AP - 交替性チューリングマシンで多項式時間で解ける問題のクラス BPP - 乱択アルゴリズムで多項式時間で解ける問題のクラス（解はおそらく正しい） BQP - 量子コンピュータで多項式時間で解ける問題のクラス（解はおそらく正しい） Co-NP - 非決定性機械で "NO" であることが多項式時間で決定可能な問題のクラス Co-NP完全 - Co-NP の中で最も難しい問題群 DSPACE(f(n)) - 決定性機械で空間計算量 O(f(n)) で解ける問題のクラス DTIME(f(n)) - 決定
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
