ノート:計算複雑性理論

計算量理論と計算複雑性理論との統合

計算複雑性理論との統合を提案します。

理由としては、内容が酷似している。また計算複雑性理論に書かれている英語名 computational complexity theory を Yahoo! で機械翻訳したところ「計算量論」と出力されます、計算量理論は他言語リンクが無いので同一記事の別名の可能性が高いと思われます。

もしこの二つの記事の意味は違うと言われる方は意見をお願いします。何もなければ 10月末頃に統合します。--U-ichi 2006年10月6日 (金) 08:17 (UTC) 、一部修正しました--U-ichi 2006年10月6日 (金) 08:28 (UTC)

（追記）統合に関しては計算複雑性理論を計算量理論にという方向で考えています。理由は「計算量理論」の名前を冠した書籍は幾つか出ていますが（参考 ISBN 4254120583、ISBN 4431705597）、「計算複雑性理論」という名前の書籍（論文も）は見あたらないからです。--U-ichi 2006年10月6日 (金) 08:22 (UTC)

ご指摘のとおりいずれも Computational Complexity Theory に対応する同義の術語ですので、 統合が適切だと思います。

ただ逆に「計算複雑性理論」に統合したほうがよいかもしれません。 というのも研究者の間では，そうしようという方向に動いているからです。 確かに「計算量」も短くて発音しやすいのでつい言ってしまうのですが、 「複雑」を使った語のほうが分野の内容をよく捉えています。 量という字は「時間の長さ」「記憶領域の大きさ」といった量的な資源のみを連想させますが、 本来 Complexity Theory の興味の対象は、 それらに限定されないさまざまな尺度で計られる、 問題に固有の複雑さだからです。 例えば「非決定性」「ランダム性」といった資源（他にもいろいろ）は、 必ずしも「量」っぽい尺度ではありません。 推察するに、実用的には「多項式時間かどうか」があまりに重要であるために、なんとなく量と呼ばれてしまいやすいのだと思います。

そういうわけで専門家の間の雰囲気としてはたぶん、 本当は「複雑性」が適切だよね、という認識です （すみません、特に根拠となる資料はないんですが）。 その結果だんだん、Complexity の訳語としても「複雑さ」が主流になってきつつあるようです。 なので私の感触としては、現在は両者並存しているものの、より将来性のある言葉遣いとしては「複雑性」を推したい気がします。 ちなみに「複雑さ」を冠した教科書ももちろんあります：ISBN 4764902001、ISBN 4785635339。 とはいえ確かに

• 「計算複雑性理論」と書くと長い──ただし「計算（Computational）」を略して「複雑性理論（Complexity Theory）」ともいいますので、普通の文脈では単に「計算量」のかわりに「複雑性」といえば OK です
• 例えばかつて情報系学部を出た非研究者のかたにとっては、おそらく「計算量」のほうが通りがよいこともまた事実
• 「計算複雑性」「計算の複雑さ」「計算複雑度」などがあり、一つの呼称が定着していない

といった欠点もありますね。 U-ichi様ほか諸賢のご意見を待ちます。LQVX 2006年10月18日 (水) 23:53 (UTC)

ご意見ありがとうございます。「量」から「複雑性」に変えていくという動きがあるのですか。そうなると確かに「計算量理論」に統合するという方向は控えた方が良いかもしれませんね。僕も一応、情報系の人間（残り半年ほどの大学院生）ですが、どちらかといえばアルゴリズムの実用が専門なので、このあたりの事は疎くてどうも申し訳ないです。ただそういう立場にいる僕には「計算複雑性理論」より「計算量理論」という言葉の方が良く耳にしますので、この辺りのことについては導入文で記述する必要性がありそうですね。それにしても専門家の方が Wikipedia に参加されているというのは実に心強いです。--U-ichi 2006年10月19日 (木) 11:11 (UTC)

いえいえ、私もウィキペディアには2、3日前に参加し始めたばかりで、じつは「統合」の手順もよくわかっていないくらいなのですが、よろしくお願いします。それから、「複雑性」が「主流になってきつつある」は、確かによく考えるとちょっと言いすぎでした。LQVX 2006年10月20日 (金) 22:03 (UTC)

上のLQVX氏の直接の知り合いです、と断った上でコメント。僕も情報系の学生（理論系ではない）ですが、現状ではやっぱり計算量のほうがやや優勢じゃないかな。計算量を知ってて複雑さを聞いたことない人はいても、逆は少なそうです。でも、複雑さのほうが適切なのは確かだと思います。僕も前から思ってたんですが、そもそも「問題の計算量」って日本語的に変じゃないですか？個々のアルゴリズムが行う計算量ならわかるけど。ある問題を解く一番速いアルゴリズムですらかかってしまう計算量を、その問題の複雑さと考えるわけでしょう。そのへんを混同した、本来は誤用だったんじゃないでしょうか。で、知名度では「計算量」、正しさでは「複雑さ」ってことなら、百科事典としては世間を正しい方向に持っていく気概を持って（？）、U-ichiさんがおっしゃるように導入分で記述した上で、標題を複雑さでいいんじゃないでしょうか。--128.100.5.198 2006年10月20日 (金) 16:25 (UTC)

「問題の複雑さ」「算法の計算量」は、言われてみればその通りですね。こっちが本当の理由かもしれません。「この算法の計算量は O (n log n)」のような言い方はされますが、それは問題自体がもつ複雑さとは別物ですね（だからといって分野名を計算量理論と呼ぶのがおかしいということにはなりませんが）。LQVX 2006年10月20日 (金) 22:03 (UTC)

（処置）反対意見もないようなので、本日「計算量理論」を「計算複雑性理論」に統合しました。計算量理論の記事内容はこちらと同等程度だったので記事内容は融合（重複部分は削除）した形にしました。また元「計算量理論」の記事内容だった部分は記事名に会わせて「計算量」の部分を「複雑性」に変えました。ただ一つ

＞ 代表的な計算量として時間計算量(＝要する時間(ステップ数))と空間計算量(＝要するメモリ量)がある。

という部分だけ、どう変えればよいか悩んでいるので誰か修正をお願いします。

なおこのノートも計算量理論のノートから計算複雑性理論のノートに移動させたことも合わせて報告します。--U-ichi 2006年10月27日 (金) 09:21 (UTC)

算法の「計算量」、問題の「複雑性」に統一するという方針の言葉遣いにして、この「時間計算量」「空間計算量」は残してみました。これで「計算量」という別の見出し語とも整合性がとれそうです。LQVX 2006年10月28日 (土) 23:15 (UTC)

計算量との統合提案

計算量を計算複雑性理論に統合することを提案しました。

理由は2つの記事に分割する意味がないからです。計算量と計算複雑性で書く内容を分ける必要があるとは思えません。また計算の複雑さなどは計算複雑性理論へのリダイレクトになっているなど、関連記事からどちらにリンクすべきかなど混乱があります。よって統一すべきだと考えます。 --Fryed-peach 2006年11月13日 (月) 10:07 (UTC)

「計算量／計算複雑性」は実際には混用されますが，現在の記事中では次のように異なる概念に使い分けられており，別物です：

• ある算法が利用する資源の量を，その算法（アルゴリズム）の「計算量」という．
• ある問題を解く最も効率のよい算法の計算量を，その問題の「計算複雑性」という．

計算量に記述されている内容はen:computational resourceに近いかもしれません．

ただ，この2つの概念をちゃんと区別しつつ，両方とも複雑性と呼ぶことにするとか，一つの記事にまとめるとかいうのはありかなと思います．LQVX 2006年11月19日 (日) 08:13 (UTC)

2つの呼び方は区別する方向で考えています。単に記事を統合しようということです。--Fryed-peach 2006年11月20日 (月) 05:49 (UTC)

すいません…編集は統合完了まで控えていただければ助かります…--Fryed-peach 2006年11月21日 (火) 05:25 (UTC)

うっかり忘れていました．申し訳ありません．LQVX 2006年11月21日 (火) 18:33 (UTC)

統合を行いました。用語の説明がややこしいですが…。不満なところは編集してください。--Fryed-peach 2006年11月21日 (火) 06:12 (UTC)

複雑性クラス名について

固有名詞的なクラス名は，記事によって太字になっているものといないものがあるようです．「Pに属する言語L」などのように書き分けるのが慣例でもあり，分かりやすいと思うので，なるべく本文中では太字（シングルクオート3つ囲み）に揃えていく方針にしたいと考えますが，いかがでしょうか．また，記事名ではどうするのが妥当でしょうか．LQVX 2006年11月21日 (火) 18:33 (UTC)

特に反対はないようですので、少しずつそのように揃えていきます。LQVX 2007年4月8日 (日) 17:08 (UTC)

用語の統一について

記事本文で使用する用語を統一するならば、計算機科学分野の他の記事でも同じ用語を使用するのがよいと思い、どの用語を採用すべきかについて、本分野に詳しい皆様のご意見をお伺いします。統一の是非なども含めてコメントを頂けないでしょうか。とりあえず気になったのは次の4点ですが他にも統一すると良いものがありましたら、どうぞ指摘を。

• Algorithm は、「算法」ではなく、カタカナで「アルゴリズム」がよいと思うのですが如何でしょう？
• Computer もカタカナで「コンピュータ」にした方が分りやすい場合もあると思いますが、計算機科学の文脈では、ほぼ「計算機」に揃えてよいでしょうか？
• Turing Machine は、「チューリングマシン」ではなく「チューリング機械」に揃える？
• the size of the input を「入力の大きさ」とすると意味が曖昧に聞こえて、「入力のサイズ」「入力サイズ」の方がよくはないでしょうか？あるいは「入力を表現するテープの長さ」とか？（いずれにしても意味をきちんと定義して使えばよい話ですけれども）

Sina 2007年3月25日 (日) 04:59 (UTC)

最近これらをそれぞれ「算法」「計算機」「機械」「大きさ」に揃えた者ですので専門外ながら一応コメントしますと、私が揃えたのは単にこの記事中で多い方に合わせただけであり、特に両者の良し悪しを比較したわけではありません。あと、「入力の長さ」はどうでしょうか。--笹本和彦 2007年3月26日 (月) 20:33 (UTC)

「この記事中で多い方に合わせただけ」というのは間違いですよね？「算法」と「アルゴリズム」は同数だったし、「計算機科学」以外の「計算機」は1つしかなかったし、他も多くは無かったですよ。まあ、私は用語をどうすべきかというポリシーを持ち合わせていないので、だからどうだというわけでもないのですが。--Melan 2007年3月27日 (火) 00:55 (UTC)

多い方にすべきかどうかはともかく、一つの記事中でいずれかに合わせるのは必ずしも間違いとはいえないように思いますが。さて、私の意見は、

• algorithmはアルゴリズム。じつは記事が短かったころに「算法」と書いたのは私なのですが、これは単なる私の癖であって、世の中では「アルゴリズム」と書く人のほうが多いからです。
• computerは計算機。一応は「コンピュータ」と全く同義ですが、この話題ではどちらかといえば漢語系の語彙が似合うように思います。理論分野内ではこれでよいと思いますが、それ以外では「コンピュータ」が一般的である文脈もあります。
• Turing machineはチューリング機械に一票。通じやすさは同じでしょう。ほんの少しだけ視認性が高い気がする、という程度の理由です。「チューリングマシン」の記事も「チューリング機械」に移しては。
• sizeは記事内では長さや入力長、他の記事とは特に統一しない。まず、和語で言えるものをカタカナ語にしないのは単なる私の好みです。「大きさ」が何か曖昧なものを指すかのように聞えるというのは確かにそういう気もしますので、「長さ」がよろしいかと。このこと以外に「大きさ」と「長さ」に特に意味の違いはないように思いますが、個々の算法に言及する際にはどちらかを避けたほうがすっきり書ける場合があります。入力するデータが正整数値であるときに大きさといったり、数列であるときに長さといったりすると紛らわしいからです（これが効いてくる状況ではどのみち明示的に注意を促すべきですが）。このため記事を跨いでの統一は不要と考えます。LQVX 2007年3月28日 (水) 00:53 (UTC)

中黒を使って「チューリング・マシン」と書かれた記事もありますね。LQVX 2007年3月28日 (水) 01:06 (UTC)

皆様、それぞれの立場でのご意見をありがとうございます。まず、用語を揃えること自体については反対意見はありませんでしたので、本記事について同じ意味で使われている用語は揃えることにしたいと思います。どう揃えるかについては、LQVXさんのご意見そのままで

• algorithm は「アルゴリズム」
• computer は「計算機」
• Turing machine は「チューリング機械」
• size は「長さ」や「入力長」など、文章に併せて使う

でよろしいですよね。2～7日したら記事本文を編集しようと思います。計算機科学分野の他の記事については、同じ分野の記事ならば同じ用語が選択される可能性は高いと思いますが、やや慎重に、機械的に用語統一するのではなくて、各々の記事の内容をみて同じ用語に揃えてよいかを個別に判断することとするのが無難そうですね。

あと、記事：チューリングマシンの改名については、後日ノート:チューリングマシンにて提案したいと思います。Sina 2007年4月1日 (日) 16:28 (UTC)

中間報告というわけでもないのですが2点気になった点があり、ご報告します。

• 「計算模型」は「計算モデル」にしようとしています。記事は計算模型ですが、カテゴリ名はCategory:計算モデルですし、計算模型より、計算モデルのほうが多く使われているように思うからです。計算モデルでは拙いというご意見がありましたら早めにお知らせ頂ければと思います。
• 概要の真中辺に「問題の時間計算量は、最も効率のよい算法を使ったときに問題のインスタンスを解くのに要するステップ数を意味し」という記述がありますが、時間計算量の定義にアルゴリズムが最良であるという条件があるのは不正確なのでは、と思い調べてます。サイズが同じでも入力値によって計算量はばらつくので、最悪ケースや平均ケースの計算量という定義はあるかと思いますが、アルゴリズムが最良か否かの判定は難しいのでは？・・・。Sina 2007年4月7日 (土) 13:06 (UTC)

英語版から翻訳した者として補足させていただくと、例えばソート問題の時間計算量を言うときにバブルソートでO(n²)だからといって、それをソート問題の時間計算量だとは言えないということではないでしょうか？最良かどうかの判定とか、平均だとか最悪だとかいうことは置いといて、ある問題の時間計算量は、その時点で既知の最良のアルゴリズムでのステップ数である、ということだと理解して翻訳しました。--Melan 2007年4月8日 (日) 01:12 (UTC)

補足ありがとうございます。Melanさんの翻訳の問題ではなくて、英語版にもしっかりそう書かれていますし、また、補足していただいたように「時間計算量」は計算モデルとアルゴリズムによって異なるので、特定の問題を解くアルゴリズムのうち最良の値でもって「問題の時間計算量」とするのは直感的だと思います。でも実際に使われている "定義" はもう少し扱いやすいように工夫されていないかと思われて、つまり出典を探しています（渡辺治著『計算可能性・計算の複雑さ入門』の4.2.3を読んでいました）。Sina 2007年4月8日 (日) 02:46 (UTC)

複雑性の定義が「計算時間（とか空間とか）の、（入力を動かしたときの）最悪値（とか平均値とか）の、（算法を動かしたときの）最良値（正確には下限）」であるのは、ややこしく見えるかもしれませんが、これはそういうものなので仕方ありません。ただ確かにもう少し読みやすく整理したほうがよさそうですね。これをすっきり書くには文章能力が問われて難しいところですが。時間があるときに私も手を加えてみます。LQVX 2007年4月8日 (日) 17:07 (UTC)

コメントありがとうございます。「（算法を動かしたときの）最良値（正確には下限）」の "正確には下限" のところが正確になるように推敲しようといじっていました。今オフラインで編集中の版は早々に切り上げて、ご専門の方が手を入れられるようにしなければ・・・。Sina 2007年4月8日 (日) 22:36 (UTC)

すみません、なぜか上で「正確には下限」と書いたんですが、今見てみるとなぜ書いたのかわからなくなってきました。どちらも正確でないかもしれません。ちょっと考えてみます。ごめんなさい。LQVX 2007年4月10日 (火) 23:04 (UTC)

落ち着いて考えてみると、「最小」「下限」いずれも不正確です。算法の計算量（＝入力を動かしたときの最悪値）を入力長から計算時間への函数とみると、それらの函数のうち最小のものは一般には存在しません。かといって下限を使うと、入力長に依らない一様（uniform）な算法の能力を測ったことならないので不適切です。要するに問題の複雑性というものは、「問題Pの複雑性はf(n)である」というふうには定義できず、「問題Pの複雑性はf(n)以内である」ということしかいえないものであるようです。

ただ地の文で、あくまで概括的、直感的な説明だとわかる形であれば、最良の算法が要する時間云々という言い回しを用いてもさほど問題ないと思います。LQVX 2007年4月11日 (水) 00:31 (UTC)

色々と頂いた助言を表現を参考にさせて頂いて先程推敲してみました。勘違いしている可能性もあるように思いますので、チェックをよろしくお願いいたします。Sina 2007年4月11日 (水) 14:52 (UTC)