5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

Complexity Classについて語れ

1 :名無しさん@お腹いっぱい。:2006/08/27(日) 14:04:47 ID:Ltp1RT5Z0
計算複雑性のスレが無いので、Complexity Classについてひとつ。
有名どころのPとかNPから、マイナーなものまで語ってください。

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

2 :                       :2006/08/27(日) 14:36:35 ID:xtdo1+jV0
class problem
 class P
 class NP
  class NP_Complete
だっけ?
まだ何かあったきがする

3 :名無しさん@お腹いっぱい。:2006/08/27(日) 16:21:12 ID:A9Jn/5n90
complexity zoo
http://qwiki.caltech.edu/wiki/Complexity_Zoo

4 :名無しさん@お腹いっぱい。:2006/08/27(日) 20:48:33 ID:IwcfB7bV0
LとかNLくらいまでしか知らない俺が>>3を見ると、目眩がする…。


5 :名無しさん@お腹いっぱい。:2006/08/28(月) 22:39:21 ID:4Kp3D0tn0
P完全問題が並列処理に適していると言われる理由を教えて下さい。

6 :名無しさん@お腹いっぱい。:2006/08/28(月) 23:42:14 ID:KgoWt+To0
>>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)が並列化でかなり効率が上がるんだっけ?

適当に考えた

7 :名無しさん@お腹いっぱい。:2006/08/29(火) 04:35:31 ID:bksZl2gs0
強多項式時間と弱多項式時間ってどう違うんですか?

8 :名無しさん@お腹いっぱい。:2006/08/29(火) 12:13:07 ID:JVttZOF30
>>5
逆じゃないの?
P完全問題がpoly(n)個のプロセッサでpolylog(n)時間に減らせるならば
(並列化して非常に高速化できるならば)Pに属する任意の問題がpoly(n)プロセッサで
polylog(n)時間が達成できる,じゃなかったっけ.
だからP完全問題はPの中でもっとも並列化しにくい問題じゃないのかな.


9 :名無しさん@お腹いっぱい。:2006/08/30(水) 19:39:38 ID:AQmwdzm90
>>6 >>8
すいません。今調べると逆でした。
P完全問題は並列化しにくい問題、ですね。

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

10 :名無しさん@お腹いっぱい。:2006/08/30(水) 21:37:35 ID:iRfE5Yel0
>>9
NCとかACはそういうクラスじゃなかったっけ.

11 :名無しさん@お腹いっぱい。:2006/08/31(木) 01:50:29 ID:eeQ13u6v0
>>9
良く分からないけど、並列化率とかも関連してくるから
一概に言えないのでは?
計算量は並列化に直接関わらないと思うし

12 :名無しさん@お腹いっぱい。:2006/08/31(木) 09:27:27 ID:H+chIqgN0
>>9
NCは「並列化できる」じゃなかったっけ。
ACは分からない…。勉強不足だなぁ。

13 :名無しさん@お腹いっぱい。:2006/09/14(木) 22:49:58 ID:hJvcaTG+0
あんまり人気ないねぇ、このスレ。
やっぱり、理論的な分野では、計算複雑性よりソフトウェアサイエンス系の方が人気があるのかな。

14 :名無しさん@お腹いっぱい。:2006/09/14(木) 23:38:44 ID:egX30eA+0
ソフトウェアサイエンスって帰納論理とか意味論とかのいわゆる数学基礎だろ
あまり人気があるようには思えないんだけど

15 :名無しさん@お腹いっぱい。:2006/09/16(土) 10:55:29 ID:3ENRqddg0
>>14
計算複雑性も基礎論に入らないかい?

16 :名無しさん@お腹いっぱい。:2006/09/22(金) 18:15:06 ID:qcT3UUfU0
>>3のリンクからこんなものハケーンw

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

17 :名無しさん@お腹いっぱい。:2006/09/25(月) 23:13:56 ID:V/gbqhNS0
http://www5f.biglobe.ne.jp/~shonanclub/news12.htm

18 :名無しさん@お腹いっぱい。:2006/10/03(火) 15:22:31 ID:IM+3QQEb0
ところで、この場合のComplexityって、日本語にどう訳すの?

19 :名無しさん@お腹いっぱい。:2006/10/07(土) 20:23:02 ID:Pfc6CESA0
複雑度

20 :名無しさん@お腹いっぱい。:2006/10/09(月) 04:27:06 ID:4HxJqkyF0
計算量か複雑性じゃないの?

21 :Soo ◆gB1U.Soo9c :2006/10/10(火) 18:06:03 ID:a/BodgrQ0 ?2BP(70)
>>20
それはない

22 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:06:08 ID:MuDjT54b0
>>20
それはないです

23 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:06:26 ID:abGsGID30
>>20
それはないです

24 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:06:29 ID:Cgbl23lp0
>>20
バカじゃない?それはないです

25 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:06:50 ID:iDRYDDJyO
>>20
バカじゃない?それはないです

26 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:06:52 ID:5KL6y62P0
>>20
それは違うんじゃないかな

27 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:06:57 ID:D9UzTFWr0
根本的に間違ってる

28 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:07:25 ID:Yrw07Dxe0
>>20
まずない

29 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:07:27 ID:yMxwLOXq0
>>20
辞書ひいたか?

30 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:08:13 ID:RFGYcrfZO
>>20
あんたバカー?wwwwwwwwwwwwwwwww

31 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:08:19 ID:0WanJwQaO
そこは全力で否定するよ

32 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:09:10 ID:L4y/X6N30
>>20
きんもー☆

33 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:10:11 ID:og1rwoiQO
>>20
それはない

34 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:10:52 ID:s9i/F6VI0
馬鹿共がお騒がせ致しました。

35 :以下、名無しにかわりましてVIPがお送りします:2006/10/10(火) 18:12:06 ID:Yrw07Dxe0
いえいえ(^^)

36 :名無しさん@お腹いっぱい。:2006/10/10(火) 18:15:55 ID:D9UzTFWr0
>>34-35
自演キモイ

37 :名無しさん@お腹いっぱい。:2006/10/10(火) 19:07:12 ID:PrDBJK930
それは違う

38 :名無しさん@お腹いっぱい。:2006/10/10(火) 19:29:06 ID:R4r4fV+a0
>>16
ワロタ
SAT∈YACC みたいにして使うのかな?使ってる実例だれか教えて

39 :20:2006/10/10(火) 22:30:59 ID:FbdzO1gl0
>>21-33
自演だろうけど超ムカツク!w

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

40 :名無しさん@お腹いっぱい。:2006/10/11(水) 04:47:03 ID:VhiAjA1v0
>>39
VIPPERが突撃したんだと思う
気にするなwww

41 :名無しさん@お腹いっぱい。:2006/10/12(木) 02:49:51 ID:r0tzGK+20
コルモゴロフの話はここでしょうか?

42 :名無しさん@お腹いっぱい。:2006/10/12(木) 11:37:51 ID:DutMIrjO0
>>41
ヘッド反転量も含めてどうぞ。

43 :名無しさん@お腹いっぱい。:2006/12/03(日) 14:10:49 ID:NePIWJsZ0
階層定理の意味がわかりません><

44 :電通太郎:2006/12/03(日) 18:47:47 ID:Vr3TAUTH0
「階層定理」を何気なくググってみた。

…ガクガクブルブル。


45 :名無しさん@お腹いっぱい。:2006/12/10(日) 10:39:55 ID:VtwwBQ3O0
http://www.kyoritsu-pub.co.jp/shinkan/shin0611_03.html
こんな本が出てたんだ。
日本語でここまで詳しく書かれた本は初めてじゃない?

46 :名無しさん@お腹いっぱい。:2006/12/10(日) 14:30:46 ID:zZvXKrtt0
>>45
これらでは不満?
http://www.amazon.co.jp/o/ASIN/4785635339/
http://www.amazon.co.jp/gp/product/4320026543


47 :名無しさん@お腹いっぱい。:2006/12/18(月) 22:56:46 ID:Uc4C80570
>>46
少し古くない?
まぁ、理論系は工学系に比べて結果が出にくいから、10年くらい前の本でも普通に使えるけど。

48 :名無しさん@お腹いっぱい。:2006/12/19(火) 13:14:05 ID:zxrQcAF80
>>47
いや「初めてじゃないだろ」ってツッコミたかっただけ。


49 :名無しさん@お腹いっぱい。:2007/02/10(土) 05:59:31 ID:Z1HnClKT0
形式言語スレができた記念age

50 :名無しさん@お腹いっぱい。:2007/02/12(月) 11:57:28 ID:d4cXW2z70
この分野の研究者の方々に質問です。
公理的集合論の知識って、この分野の研究にどれくらい必要ですか?

51 :名無しさん@お腹いっぱい。:2007/02/14(水) 21:43:03 ID:MLvoXqxm0
>>50
要るの?

52 :名無しさん@お腹いっぱい。:2007/02/15(木) 00:37:01 ID:KQZw6kwf0
論理から攻めるなら超重要。でも最近の流行りはアルゴリズム系。
というか論理系はここ数十年ほとんど結果を出していない

53 :名無しさん@お腹いっぱい。:2007/02/15(木) 01:17:31 ID:N+I2VzPSO
Natural Proofs がどうこうで
電通大へ講演を聞きにいったことがあったなー

54 :名無しさん@お腹いっぱい。:2007/02/16(金) 20:12:11 ID:g/3IYbo+0
何でも知ってるそうなので何かあったら聞いてみてあげて下さい・・・
http://music6.2ch.net/test/read.cgi/mesaloon/1165965202/l50

55 :名無しさん@お腹いっぱい。:2007/02/16(金) 22:52:42 ID:vacDsIcY0
この問題のComplexityはまだ分かっていない(Open problemだ)
とか書かれたページにたまに出くわすんだけど、問題のComplexityを求めるのってそんなに難しいの?

56 :名無しさん@お腹いっぱい。:2007/02/17(土) 01:47:19 ID:OmYDe3O5O
計算量の下界は求めにくいらしいです。
効率的なアルゴリズムは、素朴なアルゴリズムよりも複雑になるのが普通です。
AKS素数判定アルゴリズムが好例ですが、
あれはフェルマーの素数判定を改良したものなのですが、
やや複雑なアルゴリズムになっています。

57 :名無しさん@お腹いっぱい。:2007/02/17(土) 03:52:25 ID:TF6xWvqy0
>>55
何かよくわからんけど、普通は計算量(Complexity)ってアルゴリズムに対しての尺度であって、「問題の計算量」って意味不明ですよ。
この分野的に言えば、問題=言語=可算集合だからね。
アルゴリズムがわかっているのに計算量がわからん、ってのはあんまないような気がするけど、世の中にはそういうのもあるのかな?

58 :名無しさん@お腹いっぱい。:2007/02/17(土) 06:52:33 ID:Flx4bIGk0
この問題がどのComplexity Classに属するのか不明だ、の間違いでした

59 :名無しさん@お腹いっぱい。:2007/02/17(土) 06:58:26 ID:Flx4bIGk0
Complexiyt Classって階層分けされてるんだから上から順に検討していけば
その問題がどのクラスに属するかなんて分かりそうなのになあと思ったわけです

60 :名無しさん@お腹いっぱい。:2007/02/17(土) 11:55:33 ID:Zvn1UkeS0
>>59
ある問題AがあるクラスCに「属さない」ことを示すのは難しい。
>>56の書いている「下界を求めにくい」ってのはそういうこと。

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

61 :名無しさん@お腹いっぱい。:2007/02/18(日) 17:27:14 ID:BSs1tOSn0
「問題の計算量」とは言わないけど、「問題の複雑さ」とは言うよね。
上の方でComplexityの訳が「計算量」か「複雑性」かって話があったけど、
この2つの意味を併せ持ったのがComplexityじゃないのかね。

62 :名無しさん@お腹いっぱい。:2007/02/18(日) 18:56:03 ID:fgVrrz/f0
>>61
それはないです

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

64 :名無しさん@お腹いっぱい。:2007/02/19(月) 01:18:57 ID:LCDxTbYDO
recursiveの和訳が再帰的だったり帰納的だったり
統一されてない部分もあるけどね。

complexiyは計算量。

65 :名無しさん@お腹いっぱい。:2007/02/20(火) 15:22:45 ID:zIwd38950
>>61
そりゃ日常会話(?)では「ソートの計算量はn log nだよね」とか言っても、まあ文脈次第で何となく意味わかってあげられるじゃない。
でも厳密には何が言いたいかわからないよね。

16 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)