Complexity Classについて語れ

計算複雑性のスレが無いので、Complexity Classについてひとつ。
有名どころのPとかNPから、マイナーなものまで語ってください。

ここ参考
http://en.wikipedia.org/wiki/List_of_complexity_classes

class problem
　class P
　class NP
　　class NP_Complete
だっけ？
まだ何かあったきがする

complexity zoo
http://qwiki.caltech.edu/wiki/Complexity_Zoo

LとかNLくらいまでしか知らない俺が>>3を見ると、目眩がする…。

P完全問題が並列処理に適していると言われる理由を教えて下さい。

>>5
n次多項式をP(n)と表現し、ある問題がO(P(n))だとする
このとき完全並列なら同時に実行されるステップは並列数倍される
この倍数を仮にtと置くと、O(P(n))はO(P(n)/t)となる
結局次数は変わらないのでそれほど変化は無い

O(log(n))なら、O(log(n/t))=O(log(n)-log(t))=O(log(n))
O(exp(n))なら、O(exp(n/t))=O(exp(n)/exp(t))
てなわけで、オミクロン記号からすればexp(n)が並列化でかなり効率が上がるんだっけ？

適当に考えた

強多項式時間と弱多項式時間ってどう違うんですか？

>>5
逆じゃないの？
P完全問題がpoly(n)個のプロセッサでpolylog(n)時間に減らせるならば
（並列化して非常に高速化できるならば）Pに属する任意の問題がpoly(n)プロセッサで
polylog(n)時間が達成できる，じゃなかったっけ．
だからP完全問題はPの中でもっとも並列化しにくい問題じゃないのかな．

>>6 >>8
すいません。今調べると逆でした。
P完全問題は並列化しにくい問題、ですね。

「並列化しやすい」ことについて、何か指標を与えるのは難しいのかな。

>>9
NCとかACはそういうクラスじゃなかったっけ．

>>9
良く分からないけど、並列化率とかも関連してくるから
一概に言えないのでは？
計算量は並列化に直接関わらないと思うし

>>9
NCは「並列化できる」じゃなかったっけ。
ACは分からない…。勉強不足だなぁ。

あんまり人気ないねぇ、このスレ。
やっぱり、理論的な分野では、計算複雑性よりソフトウェアサイエンス系の方が人気があるのかな。

ソフトウェアサイエンスって帰納論理とか意味論とかのいわゆる数学基礎だろ
あまり人気があるようには思えないんだけど

>>14
計算複雑性も基礎論に入らないかい？

>>3のリンクからこんなものﾊｹｰﾝｗ

> YACC: Yet Another Complexity Class
> A term of derision, used against a complexity class.

http://www5f.biglobe.ne.jp/~shonanclub/news12.htm

ところで、この場合のComplexityって、日本語にどう訳すの？

複雑度

計算量か複雑性じゃないの？

>>20
それはない

>>20
それはないです

>>20
それはないです

>>20
バカじゃない？それはないです

>>20
バカじゃない？それはないです

>>20
それは違うんじゃないかな

根本的に間違ってる

>>20
まずない

>>20
辞書ひいたか？

>>20
あんたバカー？ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

そこは全力で否定するよ

>>20
きんもー☆

>>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