Complexity Classについて語れ

>>20
それはない

馬鹿共がお騒がせ致しました。

いえいえ（＾＾）

>>34-35
自演キモイ

それは違う

>>16
ﾜﾛﾀ
SAT∈YACC みたいにして使うのかな？使ってる実例だれか教えて

>>21-33
自演だろうけど超ムカツク！ｗ

complexityの日本語訳が「計算量」なんだよ。
time complexityは時間計算量、space complexityは空間計算量（または領域計算量）、complexity classは計算量クラス。
なぜかcomputational complexityの場合には「計算複雑性」と訳される。
complexity classも複雑性クラスと訳されることはあるけど、計算量クラスのほうが普通。

証拠：

・明らかに時間計算量をtime complexityと呼んでいる。
http://en.wikipedia.org/wiki/Computational_complexity
> The time complexity of a problem is the number of steps that it takes to solve
> an instance of the problem as a function of the size of the input (usually
> measured in bits), using the most efficient algorithm.

・O(n)など計算量を称するのにcomplexityと言っている（151,000件）
http://www.google.com/search?hl=en&q=%22complexity+is+O%28%22&lr=lang_en

・計算量クラス（4,300件）、複雑性クラス（1,650件）、複雑度クラス（3件）
http://www.google.com/search?hl=ja&q=%E8%A8%88%E7%AE%97%E9%87%8F%E3%82%AF%E3%83%A9%E3%82%B9&lr=lang_ja
http://www.google.com/search?hl=ja&q=%E8%A4%87%E9%9B%91%E6%80%A7%E3%82%AF%E3%83%A9%E3%82%B9&lr=lang_ja
http://www.google.com/search?hl=ja&q=%E8%A4%87%E9%9B%91%E5%BA%A6%E3%82%AF%E3%83%A9%E3%82%B9&lr=lang_ja

>>39
VIPPERが突撃したんだと思う
気にするなｗｗｗ

コルモゴロフの話はここでしょうか？

>>41
ヘッド反転量も含めてどうぞ。

階層定理の意味がわかりません＞＜

「階層定理」を何気なくググってみた。

…ガクガクブルブル。

http://www.kyoritsu-pub.co.jp/shinkan/shin0611_03.html
こんな本が出てたんだ。
日本語でここまで詳しく書かれた本は初めてじゃない？

>>45
これらでは不満？
http://www.amazon.co.jp/o/ASIN/4785635339/
http://www.amazon.co.jp/gp/product/4320026543

>>46
少し古くない？
まぁ、理論系は工学系に比べて結果が出にくいから、10年くらい前の本でも普通に使えるけど。

>>47
いや「初めてじゃないだろ」ってツッコミたかっただけ。

形式言語スレができた記念age

この分野の研究者の方々に質問です。
公理的集合論の知識って、この分野の研究にどれくらい必要ですか？

>>50
要るの？

論理から攻めるなら超重要。でも最近の流行りはアルゴリズム系。
というか論理系はここ数十年ほとんど結果を出していない

Natural Proofs がどうこうで
電通大へ講演を聞きにいったことがあったなー

何でも知ってるそうなので何かあったら聞いてみてあげて下さい・・・
http://music6.2ch.net/test/read.cgi/mesaloon/1165965202/l50

この問題のComplexityはまだ分かっていない(Open problemだ)
とか書かれたページにたまに出くわすんだけど、問題のComplexityを求めるのってそんなに難しいの？

計算量の下界は求めにくいらしいです。
効率的なアルゴリズムは、素朴なアルゴリズムよりも複雑になるのが普通です。
AKS素数判定アルゴリズムが好例ですが、
あれはフェルマーの素数判定を改良したものなのですが、
やや複雑なアルゴリズムになっています。

>>55
何かよくわからんけど、普通は計算量（Complexity）ってアルゴリズムに対しての尺度であって、「問題の計算量」って意味不明ですよ。
この分野的に言えば、問題＝言語＝可算集合だからね。
アルゴリズムがわかっているのに計算量がわからん、ってのはあんまないような気がするけど、世の中にはそういうのもあるのかな？

この問題がどのComplexity Classに属するのか不明だ、の間違いでした

Complexiyt Classって階層分けされてるんだから上から順に検討していけば
その問題がどのクラスに属するかなんて分かりそうなのになあと思ったわけです

>>59
ある問題AがあるクラスCに「属さない」ことを示すのは難しい。
>>56の書いている「下界を求めにくい」ってのはそういうこと。

P=NP?を例にとれば，NPに属するがPに属さない問題を1つ見つけることができれば
P≠NPってことでおしまい。
だけど，NPに属す問題Aが「決定性Turing機械では多項式時間に受理できない」ってことを証明するのが難しい。

「問題の計算量」とは言わないけど、「問題の複雑さ」とは言うよね。
上の方でComplexityの訳が「計算量」か「複雑性」かって話があったけど、
この2つの意味を併せ持ったのがComplexityじゃないのかね。

>>61
それはないです

　　　　　　＿＿＿
　　　　 ／∧＿∧ ＼
　　　./ 　<ヽ｀∀´>､ ｀、 池袋西口立教通りに本拠地
　　/　/＼ ＼つ　 つ、ヽ 極東会 東京都豊島区西池袋1−29−5
　　|　|　　,＼ ＼ ﾉ　　|　| 松山眞一＝曹　圭化
　　ヽヽ 　レ ＼ ＼ﾌ /　/ 次の池田も朝鮮人
. 新宿　池袋　大塚の朝　鮮　人暴力団　極　東　会お断り
　　　 　ヽ､ _＿＿_,, ／
　極東会は、北朝鮮政府から麻薬を輸入販売する正規代理
店です。最近も、拳銃や麻薬の不法所持で何度か摘発され
ています。同地域の店は、否定しても大概みかじめ料を支払
などの関係があり、少年少女や各店舗などを通じてその地域
で何か話せば情報は筒抜けになります。学生相手と同じだね
同地域の、キャバクラ　バー　風俗店　１円ゲームなどは、
彼らの経営ないし影響下です。行かないようにしましょう。
　黒服や十五の金貸しや風俗嬢、キャバ嬢は彼らの目で
あり耳であり手足である香具師です。黒服は、昼は頭の軽い
女をスカウトしてＡＶ【女優】やキャバクラ嬢、風俗嬢に仕立て
ます。夕方〜夜は粘着ストーキングや駅などでの見張りや
スカウト、キャバクラなどの客引きを主に担当します。
同じ朝鮮人の集団粘着ストーカー創価学会と連携します。
池袋西口には、彼らの本部があります。気をつけましょう。
　右翼団体も経営し、赤羽　町田　埼玉にも勢力を持ちます。
http://ja.wikipedia.org/wiki/%E6%A5%B5%E6%9D%B1%E4%BC%9A

recursiveの和訳が再帰的だったり帰納的だったり
統一されてない部分もあるけどね。

complexiyは計算量。

>>61
そりゃ日常会話（？）では「ソートの計算量はn log nだよね」とか言っても、まあ文脈次第で何となく意味わかってあげられるじゃない。
でも厳密には何が言いたいかわからないよね。

俺が大学で習ったときは、決定性対数領域と非決定性対数領域の言語族はDLOGとNLOGだったんだけど、最近はLとNLっていうのが普通なのかな。
NLはともかく、Lだと一般的な言語の意味でよく使うLとごっちゃになりそうだけど、論文書くときはフォントとか分けてるのだろうか。

PSPACEがPSになってたりするね

D(決定的) N(非決定的) L(対数) P(多項式) E(指数) T(時間) S(空間)
この組み合わせで統一すれば…
DLS ⊆ NLS ⊆ DPT ⊆ NPT ⊆ DPS ＝ NPS ⊆ DET ⊆ NET ⊆ DES ⊆ NES
…かえって紛らわしいか(笑)

POLYLOGはどうしましょ？

決定性のDと時間のTだけ省略したら、ちょっとすっきりすんじゃね？

LS ⊆ NLS ⊆ P ⊆ NP ⊆ PS ＝ NPS ⊆ E ⊆ NE ⊆ ES ⊆ NES

n log n に迫る乗算アルゴリズムが出たらしいです

【nビット】 Furer 乗算【n log n 2^O(log^* n)】
http://science6.2ch.net/test/read.cgi/math/1181643550/

あげ

理論的計算量なんて極論に意味はあるのだろうか
時間もリソースも有限だというのに

意味があるかないかで言ったら「無いことは無い」としか言えない
知識の垂直統合はまた違う分野になるから
野球みたいな球遊びやって意味あるの？サッカーのほうが面白いのにっていう質問と同レベル

>>73
現在知られている公開鍵暗号は全部計算量的安全性に依存している。
Amazon で買い物したときにクレジットカード番号がぶっこ抜かれないのも Complexity Theory の成果なんだぜ。

>>75
つカオス暗号

>>6
O(exp(n/t))≠O(exp(n)/exp(t))

>>75
> 現在知られている公開鍵暗号は全部計算量的安全性に依存している。
> Amazon で買い物したときにクレジットカード番号がぶっこ抜かれないのも Complexity Theory の成果なんだぜ。

超亀レスで済まんが、上は嘘というか完全に間違いだ。

Complexity Theoryで計算クラスの包含関係がproperだ（つまり等しくない）と証明されてるのは非常に少ない。

公開鍵暗号の基盤である素因数分解問題はＮＰであってＰではないと信じられ、その信念を前提としてクレジットカード番号の通信の暗号化に
利用されているのは事実だが、Ｐに属さないＮＰ問題が存在する事（つまりＰ≠ＮＰ）の証明はなされていないし、
ましてやＮＰではあるがＮＰ完全ではないと信じられている素因数分解問題がＰに属さない事は全くの未解決。

Complexity Theoryの研究からはＰとＮＰとが等しくなさそうだという状況証拠は幾つも出されているが
Ｐ≠ＮＰの最終的な証明はなされていないし、ましてや素因数分解問題がＰに属さない事の証明（この問題はＮＰ完全ではないと信じられており
それならばＰ≠ＮＰの証明より更に困難）つまり公開鍵暗号の安全性の確実な保証はComplexity Theoryからは何も与えられていない。

逆説的だが、クレジットカード番号がぶっこ抜かれないのは、素因数分解の高速なアルゴリズムが発見されていないという
単なる経験的な事実（人類の知識が不完全だという事実）と量子コンピュータ（Shorのアルゴリズムにより素因数分解問題を多項式時間で解く
計算能力を有する）を実用化するに必要な量子力学的な系を実現できていない事によって現在のところは担保されているに過ぎない。

>>78

>> 現在知られている公開鍵暗号は全部計算量的安全性に依存している。
>> Amazon で買い物したときにクレジットカード番号がぶっこ抜かれないのも Complexity Theory の成果なんだぜ。
>
> 超亀レスで済まんが、上は嘘というか完全に間違いだ。


完全に間違いは言い過ぎだろ．

確かにNPに属する問題で（意味があるほど高い）計算量の下界を厳密に導出することはできてはいないが，
例えば暗号に良く使われる離散対数問題などは generic model の下で指数関数的な下界が証明できる．
確かに generic model みたいに敵対者ができる演算を制限するのは厳密ではないが十分自然なモデルであるし，
その結果が暗号系の安全性をある程度は保証していると言ってもいいだろう．

まぁ専門家のものでもなさそうなレスに超マジレスしてこき下ろすのもどうかと思うがな．

しかも半年前のレスだもんな。

complexity zoo の動物の数すごいな。
complexity gardenは植物園の分類みたいやな。

w