| 翻訳と辞書 |
指数時間仮説[しすうじかんかせつ]
計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいてでは解けないというものである。〔.〕 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。
==定義==
''k''-SATは一つの節に含まれる変数が高々''k''個であるような連言標準形の論理式が、ある真偽値の割り当てによって真となるようにできるかどうかチェックするという問題である。
各整数 ''k'' ≥ 2に対して、実数''sk''を''k''-SATをO(2δ''n'')-時間で解くアルゴリズムが存在するような実数δの下限とする(''n''は与えられた''k''-SATのインスタンスに含まれる変数の個数)。このとき、2-SATは多項式時間で解けるため''s''2 = 0である。指数時間仮説は、すべての''k'' > 2に対して''s''''k'' > 0であるという予想である。明らかに、''s''3 ≤ ''s''4 ≤ ...である。そのためこれは''s''3 > 0と同値である(残りの ''sk''が正であることはすぐにこれから言える)。
指数時間仮説を、「3-SATは2o(''n'')時間で解けない」という少し弱い形で定義している文献もある。もし3-SATを2o(''n'')時間で解くアルゴリズムが存在すれば、明らかに''s''3は0である。しかし、これは「0に収束する数列δ''i''が存在して、各アルゴリズムがO(2δ''i''''n'')時間で動くような3-SATのアルゴリズムの列が存在するが、種類が高速に増大するので最適なものを選ぶことができない」という現在の知識と矛盾しない。〔.〕
数列''s''3, ''s''4, ...は上界1を持つ単調増加数列なので、極限値''s''∞が存在する。強指数時間仮説(Strong exponential time hypothesis)は、極限値''s''∞ が1に等しいという予想である。〔.〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「指数時間仮説」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|