指数時間仮説

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Exponential time hypothesis|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、Impagliazzo & Paturi (1999)によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいて準指数時間（英語版）では解けないというものである。^[1] 指数時間仮説がもし成立すれば、P ≠ NPも成立する。この予想は、多くの計算機科学の問題の計算量が同等である(どれか一つに準指数時間のアルゴリズムが見つかれば、その他すべての問題にも準指数時間のアルゴリズムがある)ことを示すのに使われる。

k-SATは一つの節に含まれる変数が高々k個であるような連言標準形の論理式が、ある真偽値の割り当てによって真となるようにできるかどうかチェックするという問題である。 各整数 k ≥ 2に対して、実数s_kをk-SATをO(2^δn)-時間で解くアルゴリズムが存在するような実数δの下限とする(nは与えられたk-SATのインスタンスに含まれる変数の個数)。このとき、2-SATは多項式時間で解けるためs₂ = 0である。指数時間仮説は、すべてのk > 2に対してs_k > 0であるという予想である。明らかに、s₃ ≤ s₄ ≤ ...である。そのためこれはs₃ > 0と同値である(残りの s_kが正であることはすぐにこれから言える)。

指数時間仮説を、「3-SATは2^o(n)時間で解けない」という少し弱い形で定義している文献もある。もし3-SATを2^o(n)時間で解くアルゴリズムが存在すれば、明らかにs₃は0である。しかし、これは「0に収束する数列δ_iが存在して、各アルゴリズムがO(2^δ_in)時間で動くような3-SATのアルゴリズムの列が存在するが、種類が高速に増大するので最適なものを選ぶことができない」という現在の知識と矛盾しない。^[2]

数列s₃, s₄, ...は上界1を持つ単調増加数列なので、極限値s_∞が存在する。強指数時間仮説(Strong exponential time hypothesis)は、極限値s_∞ が1に等しいという予想である。^[3]

• Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), “Strong computational lower bounds via parameterized complexity”, Journal of Computer and System Sciences 72 (8): 1346–1367, doi:10.1016/j.jcss.2006.04.007 .
• Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2013), “Known algorithms for EDGE CLIQUE COVER are probably optimal”, Proc. 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013), arXiv:1203.1754, オリジナルの2013年4月16日時点におけるアーカイブ。, https://archive.is/20130416012824/http://knowledgecenter.siam.org/0236-000085/0236-000085/1 .
• Dantsin, Evgeny; Wolpert, Alexander (2010), “On moderately exponential time for SAT”, Theory and Applications of Satisfiability Testing–SAT 2010, Lecture Notes in Computer Science, 6175, Springer-Verlag, pp. 313–325, doi:10.1007/978-3-642-14186-7_27 .
• Feige, Uriel; Kilian, Joe (1997), “On limited versus polynomial nondeterminism”, Chicago Journal of Theoretical Computer Science 1: 1–20, http://cjtcs.cs.uchicago.edu/articles/1997/1/contents.html .
• Flum, Jörg; Grohe, Martin (2006), “16. Subexponential Fixed-Parameter Tractability”, Parameterized Complexity Theory, EATCS Texts in Theoretical Computer Science, Springer-Verlag, pp. 417–451, ISBN 978-3-540-29952-3 .
• Impagliazzo, Russell; Paturi, Ramamohan (1999), “The Complexity of k-SAT”, Proc. 14th IEEE Conf. on Computational Complexity, pp. 237–240, doi:10.1109/CCC.1999.766282, http://www.sciencedirect.com/science/article/pii/S0022000000917276/pdf?md5=39d2ff12235e7d6a04f914120956cb5d&pid=1-s2.0-S0022000000917276-main.pdf .
• Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis (2001), “Which problems have strongly exponential complexity?”, Journal of Computer and System Sciences 63 (4): 512–530, doi:10.1006/jcss.2001.1774, CiteSeer^x: 10.1.1.66.3717, http://www.sciencedirect.com/science/article/pii/S002200000191774X/pdf?md5=dc03cf0d053a9fdab68b769ab65c28fd&pid=1-s2.0-S002200000191774X-main.pdf .
• Karpinski, Marek; Schudy, Warren (2010), “Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament”, Proc. ISAAC 2010, Part I: 3-14, doi:10.1007/978-3-642-17517-6_3, http://link.springer.com/chapter/10.1007/978-3-642-17517-6_3 .
• Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket (2011), “Known algorithms on graphs of bounded treewidth are probably optimal”, Proc. 22nd ACM/SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 777–789, arXiv:1007.5450, http://www.siam.org/proceedings/soda/2011/SODA11_060_lokshtanovd.pdf .
• Pătraşcu, Mihai; Williams, Ryan (2010), “On the possibility of faster SAT algorithms”, Proc. 21st ACM/SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 1065–1075, http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf .
• Williams, Ryan (2010), “Improving exhaustive search implies superpolynomial lower bounds”, Proc. 42nd ACM Symposium on Theory of Computing (STOC 2010), New York, NY, USA: ACM, pp. 231–240, doi:10.1145/1806689.1806723 .
• Woeginger, Gerhard (2003), “Exact algorithms for NP-hard problems: A survey”, Combinatorial Optimization — Eureka, You Shrink!, 2570, Springer-Verlag, pp. 185–207, doi:10.1007/3-540-36478-1_17, http://www.win.tue.nl/~gwoegi/papers/exact.pdf .

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

• 表示
• 編集