指数時間仮説

計算複雑性理論において、指数時間仮説(Exponential time hypothesis)はまだ証明されていない計算量に関する予想であり、Impagliazzo & Paturi (1999)によって定式化された。この予想は、3-SAT(あるいは他のNP完全問題)は最悪ケースにおいて準指数時間では解けないというものである。 指数時間仮説がもし成立すれば、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のアルゴリズムの列が存在するが、種類が高速に増大するので最適なものを選ぶことができない」という現在の知識と矛盾しない。

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

参考文献

• 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 .