Team TripleFalcon. http://www.triplefalcon.com/

概要

 ある問題を計算するのが簡単な問題がある一方、計算するのが難しい問題もあることを私たちは直感的に知っています。しかしながら、もう少し論理的に難しさとは何かについて考えることはできないものでしょうか。

 そのような直感を表現する方法は様々に提唱されましたが、中でもコンピュータ技術者に最も適した表現方法としてチューリング機械(Turing machine)と呼ばれる概念上の機械を考えて、機械が計算で消費する資源が大きいとき問題が難しいと考える、という方法があります。そのような資源の消費量を計算量と呼びます。(参照→チューリング機械

 チューリング機械が消費する資源としては、動作開始から動作終了までの時間による、時間計算量(関数δによる状態遷移回数)とか使用したテープのマスの数による領域計算量に着目します。

 もう少し現代の工学に近い考え方には、計算に必要とされる素子(AND素子とかOR素子)の数を考えるというのもあります。

 時間計算量領域計算量は、単なる数字で表現するのが難しい量です。問題の難しさは問題の種類のほかに問題の大きさにも依存するからです。例えば、n 個の数値を小さい順に並べ替える問題は n が大きいか小さいかによって消費する時間や領域が異なるわけです。そこで、 の大きさと消費する時間関数 T(n) の型に着目して分類しようと考えるようになりました。 そして、T(n) の分類には、オーダーと呼ぶ概念を用いることがあります。 (参照→オーダー)

 計算論の世界では、問題を文字で記述した長さ n に対して、時間計算量 T(n) や領域計算量 S(n) が、n についてオーダーを用いて論じます。例えば、O(n2) であるか O(n5) であるとか。また、もっと大雑把に多項式型増加であるか指数型増加であるかという2分類を行うことすらあります。

Team TripleFalcon. http://www.triplefalcon.com/

定義

 ある問題の複雑さを調べる場合、まずその問題を判定問題として捉えます。(参照→判定問題)例えば、言語 L を定義したとき、ある質問分 x が x∈L を満たすかどうかという問題にします。そして、x の含む文字数を n とするとき、チューリング機械が受理するのにかかる時間計算量を T(n) 、領域計算量を S(n) と表した場合に言語 L の複雑性を以下のように表現します。

 以下、DTM は決定性チューリング機械、NTM は非決定性チューリング機械の略号です。チューリング機械 M について Mt(x,t) はチューリング機械が時間 t 内に出した出力とします。 Ms(x,s) は領域 s で出した出力とします。出力は、{yes,no,未定義} となります。(時間 t 内に答えにたどり着かない場合は、未定義です。)

定義1) DTIME(T(n))
def
{ L | ∃M∈DTM , x∈L⇔Mt(x,O(T(n)))=yes }
定義2) NTIME(T(n))
def
{ L | ∃M∈NTM , x∈L⇔Mt(x,O(T(n)))=yes }

 ここで、DTIME( n2 ) は、決定性チューリング機械が n2 時間あれば受理できる言語の集合を表すわけです。

定義1) DSPACE(T(n))
def
{ L | ∃M∈DTM , x∈L⇔Ms(x,O(T(n)))=yes }
定義2) NSPACE(T(n))
def
{ L | ∃M∈NTM , x∈L⇔Ms(x,O(T(n)))=yes }

 ここで、DSPACE( n2 ) は、決定性チューリング機械が n2 領域あれば受理できる言語の集合を表すわけです。

Team TripleFalcon. http://www.triplefalcon.com/

PNP

 時間限定の言語のクラス PNP を以下のように定義します。

定義3) P
def
DTIME(n)∪DTIME(n2)∪・・・=
k=1
DTIME(nk)
定義4) NP
def
NTIME(n)∪NTIME(n2)∪・・・=
k=1
NTIME(nk)

 特に P多項式時間計算可能とか現実的計算可能と呼ばれる重要なクラスです。NPP に比べるとかなり広い集合をさすと考えられています。 PNP は自明なのですが、PNP はまだ証明されていません。

 クラス NP に関しては誤解も多く、NP (No-deterministic Polynomial)P かどうか決定されていない問題の集合」と解釈してしまうことが多いようです。私は、これは正しく理解している人でも文脈によって「NPは現実的時間で解けるかどうかわかっていない問題です」という言い方をすることに原因があるのではないかと疑っています。その言葉を NP の定義と思い込むと、誤解にも納得がいきます。

 NP の定義を理解すればわかるとおり、NP の定義にはPで計算できない」とかPかどうか決定できない」という否定的な言葉は使われておらず、非決定性チューリング機械が多項式時間で受理する言語という肯定的な言葉で定義されていることを忘れないでください。性質として P に属さないように予想される問題を数多く含んでいるだけです。

Team TripleFalcon. http://www.triplefalcon.com/

現実的計算可能

 言語 L が現実的計算可能とは、L が Pであることを言います。

 定義上は、計算時間 T(n)=O(n100) であっても、現実的計算可能といえますが、これほど高い計算量では我々の手におえないのも確かです。P の上記の定義にこだわる理由は 3つあると思います。

理由1) P の定義は、Pに属すると簡単な問題であると言いたいのではなくて、P に属さない問題は到底解けそうも無いことを示すために定義されているからです。

理由2) 今のところ、O(n100) で解けるが O(n99) では解けないといった変な問題は見つかっておらず、それはかなり人工的な自然でない問題を作り出さない限りありそうもないからで、実用上のほとんどの問題が P の比較的低い次数の問題であるか、または P ではない、といって差し支えないからです。

理由3) P はクラスとして安定しています。計算機モデルの定義には、チューリング機械の他、kテープチューリング機械ランダムアクセス機械のようにテープの扱い方やステップ数の数え方の定義が異なる変種が多くあります。 DTIME( nc ) といったクラスは具体的過ぎて、わずかな機械の定義の違いを吸収できない場合があります。一方、P はいずれの機械の定義を用いても集合の大きさは変わりません。

Team TripleFalcon. http://www.triplefalcon.com/

下界と上界

 計算量(時間や領域) の上界というのは、これこれの計算量で計算できるという場合に使う言葉で、下界はこれこれより少ない資源で計算できないという意味で使います。言語 L の計算時間の上界 f(n) であるという場合、f(n) 時間で L を受理する チューリング機械が存在すると言うことを意味しますが、計算時間の下界f(n) であるという場合は、f(n) より短い時間で L を受理するチューリング機械が存在しないことを意味します。

 ここでちょっと疑問に感じる方もいるでしょう。機械が存在しないなんて、証明できるんでしょうか?確かにこれは重大な問題で、多くの場合証明できません。証明できるほうがまれともいえます。

 問題の上界を探る場合は、効率よく計算できるアルゴリズムを考え出せばよいのです。しかし、反対に下界を探る場合は、自分がアルゴリズムを思いつかなかったというだけでは、効率のいいチューリング機械が存在しないという証明にはなりません。 自分の下手くそなアルゴリズムが問題を効率よく速く解かないという愚痴に過ぎないからです。

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/


Team TRIPLE FALCON

アクション&シミュレーション ゲーミングとゲーム製作を真面目に考える 新進気鋭の研究者集団

   
 
用語集TOP

計算複雑性(computational complexity)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
あ-お か-こ さ-そ た-と な-の
は-ほ ま-も や-よ ら-ろ わ-ん

数学、哲学、工学を横断する事典です。よろしければ活用してください。 ゲーム, アクション,シューティング,シミュレーション,リアルタイム, 計量経済学,計量心理学, コンピュータ,用語集,計算機科学用語集,コンピュータ用語集, 3DCG, グラフィックス,ゲームグラフィックス,美少女, 光反射,鏡面反射,拡散反射,屈折,散乱,異方性反射,影, シェーディング,レンダリング,透視変換, 発光,爆発,爆炎,煙, 物理, 人物,表情,表現,運動,力学,流体, 計算幾何学, グラフ,アフィン変換,アフィン写像,凸包,超平面,3D,3Dの数理, コンピュータサイエンス,コンピュータ, 計算機科学, チューリングマシン,チューリング機械,線形有界オートマトン,プッシュダウンオートマトン,有限オートマトン, オートマトン,状態遷移,遷移関数,対角線論法,文字列,記号, FA,NFA,PDA,NPDA,LBA,NLBA,TM, 計算量,P,NP,PSPACE,NP完全,NP困難,P完全,PSPACE完全,PP,APX,APX完全, 確率チューリング機械,確率オートマトン, 音声, 音階,音量,音律,和音,和声,無限上昇音,MIDI, 色彩, 表色系,顕色系,混色系,RGB,CMY,YCbCr,YUV,YIQ,CIE,L*a*b*, 符号, 圧縮,符号化,情報源符号化, 符号,ブロック符号,ストリーム符号,符号理論, 離散数学, 集合,写像,関数,全単写,単写,全写,対応関係,関係,反射,反射推移閉包, 代数系, 群,環,体,モノイド,半群,準同型写像,同型写像, 形式言語, 言語,正則言語,文脈自由言語,文脈依存言語,確率言語, 文法,正則文法,文脈自由文法,文脈依存文法,確率文脈自由言語, 文字,文字列, 3型言語,2型言語,1型言語,0型言語, 信号処理, 変換,フィルタ,信号処理,DFT,DCT,DST,FFT,Wavelet,フーリエ変換, 離散,コサイン変換,サイン変換,ウェーブレット, 基礎数学, 数学,応用数学,基礎数学,フィボナッチ数列, 解析学, 位相空間,線形空間,距離空間,ベクトル空間,vector,バナッハ空間,Banach,ヒルベルト空間,Hilbert,ユークリッド空間,Euclid, ノルム,内積,可算濃度,非可算濃度, 情報理論, 情報源,情報量,エントロピー,相互情報量,記号,記号列, 複雑系, カオス,フラクタル,フラクタル幾何学,カオス写像, インターネット, セキュリティ,HTTP,SMTP,FTP,プロトコル, その他理論,理論, 紅茶,自転車通勤,備忘録, 暗号, モンゴメリ演算,高速計算法,素因数分解,離散対数問題, 暗号,ブロック暗号,ストリーム暗号,楕円暗号, 乱数,乱数生成,共通鍵暗号,公開鍵暗号,公開鍵署名,鍵共有,鍵交換, 線形攻撃,差分攻撃,補間攻撃,スライド攻撃,量子暗号, 依頼計算,ゼロ知識対話証明,ハッシュ,

AES,Rijndael,RSA,ElGamal,Twofish,Serpent,

RC6,MARS,CAST,IDEA,GOST,

MQV,DH,EC-DH,EC-ElGamal,

終了,

フィリピンパブ
アミューズメント企画はお任せ
資産運用はお任せ
メール お問い合わせ お問い合わせ メール メール メール メール メール メール