2ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 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
いや「初めてじゃないだろ」ってツッコミたかっただけ。


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

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

read.cgi ver 05.02.02 2014/06/23 Mango Mangüé ★
FOX ★ DSO(Dynamic Shared Object)