AtlasFor ALignmenTOpen Atlas
← 審査済みの問い

審査済み

強指数時間仮説（SETH）は正しいか？

Is the Strong Exponential Time Hypothesis true?

computer-sciencecomputational-complexityfine-grained-complexity

問題文

任意の epsilon > 0 に対して、k-SAT を 2^{(1-epsilon)n} 時間で解けないような k が存在するか、を決定せよ。

Decide whether, for every epsilon > 0, there is a k such that k-SAT cannot be solved in time 2^{(1-epsilon)n}.

背景

SETH is the assumption under which fine-grained complexity derives tight conditional lower bounds for problems solvable in polynomial time. It is a hypothesis, not a theorem, and the field's results are only as strong as it is.

アプローチ · 2 件

解決したかどうかは、問いではなくアプローチごとに決まります。Atlas は判定しません。外部の判定者が何をしたかを記録します。

  • Faster satisfiability algorithms

    計算による判定

    到達状況
    進行中
    判定者
    execution and peer review: an algorithm beating the bound would refute the hypothesis outright · 査読
    定式化
    Find a k-SAT algorithm running in time 2^{(1-epsilon)n} for all k, refuting the hypothesis.問いと同値

    保たれているもの

    • A single algorithm settles the question in the negative

    加えられた仮定・条件

    • Nothing: this is the direct attack

    Known improvements are per-k and vanish as k grows, which is exactly what the hypothesis asserts.

    証拠

    • paperdoi:10.1006/jcss.2000.1727R. Impagliazzo, R. Paturi, On the complexity of k-SAT, J. Comput. System Sci. 62 (2001) 367-375: the origin of ETH and SETH

  • Fine-grained reductions

    閉じた道（障壁）

    到達状況
    この道では到達できないと証明済み
    判定者
    none: the obstruction is a published theorem about proof techniques · 引用

    差分（このアプローチが問いの何を保ち、何を弱めるか）はまだ書かれていません。人類審査で書きます。

    閉じた道

    • Under the nondeterministic version of the hypothesis, deterministic fine-grained reductions cannot prove SETH-hardness for several central problems, so the reduction toolkit cannot establish the hypothesis or its consequences for them.条件つき（the nondeterministic Strong Exponential Time Hypothesis）— 前提が崩れれば道は開く
      • paperdoi:10.1145/2840728.2840746M. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, S. Schneider, Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility, ITCS 2016, 261-270

出典

  • paperdoi:10.1006/jcss.2000.1727R. Impagliazzo, R. Paturi, On the complexity of k-SAT, J. Comput. System Sci. 62 (2001) 367-375: the origin of ETH and SETH
  • paperdoi:10.1145/2840728.2840746M. Carmosino, J. Gao, R. Impagliazzo, I. Mihajlin, R. Paturi, S. Schneider, Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility, ITCS 2016, 261-270

記録

URI
https://atlasalt.com/q/bbe22e7e-e947-482a-99ab-41997fc90fea
登録
2026-09-17
最終レビュー
2026-09-19
次回レビュー期限
2026-12-18
版
6f4486f70256
ライセンス
CC-BY-4.0
立場
record_only（Atlas は判定しない）