指数時間仮説

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, https://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, https://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:数学）。

• 表示
• 編集