The Strong Exponential Time Hypothesis (SETH) is stronger than P != NP. If SETH is false (i.e., some k-SAT algorithm achieves 2^((1 - epsilon) k n) for all k with epsilon > 0), what would that imply?
AP = NP
BThere exists a subexponential-time algorithm for k-SAT for each fixed k, but this does not imply P = NP — it only says that the exponential dependence on clause size k can be reduced
CAll NP-hard problems have subexponential-time algorithms
DSETH is logically equivalent to P != NP, so disproving SETH proves P = NP
SETH is a quantitative strengthening of P != NP. It says that not only is k-SAT exponential in n (which follows from P != NP), but the exponential base is 2^(Omega(k)), meaning the dependence on k is unavoidable. If SETH is false, there are algorithms with running time like 2^(0.9 * k * n), which is subexponential in k for fixed n. This does not contradict P != NP (since for fixed k the dependence on n is still exponential). However, a false SETH would have profound implications for the fine-grained complexity hierarchy — it would suggest that brute-force algorithms for SAT and related problems can be substantially improved in ways currently unknown.
Question 2 True / False
ETH (not SETH) conjectures that 3-SAT requires 2^(Omega(n)) time. Under ETH, can one-SAT and two-SAT have algorithms substantially faster than 2^(cn) for some c > 0?
TTrue
FFalse
Answer: True
ETH only makes a claim about one specific problem (3-SAT, or equivalently, all k-SAT with unbounded k). It does not directly constrain the complexity of k-SAT for small fixed k. In fact, 2-SAT is solvable in O(n^2) polynomial time via strongly connected components, and 1-SAT (unit propagation) is trivial. SETH is the hypothesis that makes quantitative claims about ALL k, preventing exponential speedups as k varies. ETH allows for the possibility that 2-SAT, 4-SAT, etc. have drastically faster algorithms than 3-SAT, even if 3-SAT is hard.
Question 3 Short Answer
Explain why ETH and SETH are called 'conditional' rather than 'unconditional' hypotheses, and how they are used to prove lower bounds for other problems.
Think about your answer, then reveal below.
Model answer: ETH and SETH are conjectures — unproven assumptions about complexity. Unlike unconditional lower bounds (which hold in all models of computation), conditional hardness says: 'IF the hypothesis is true, THEN this problem requires at least this much time.' Researchers use fine-grained reductions to show that faster algorithms for other problems would contradict SETH. For example, if 3-SUM could be solved in O(n^1.99) time, then (via a known reduction) 3-SAT could be solved faster than SETH predicts, contradicting SETH. Thus, under SETH, 3-SUM requires O(n^2) time. This is not proven hardness but a rigorous conditional statement: the assumptions explain empirical hardness observed across many classical problems.
The conditional approach is practical for algorithm design: problems that reduce to 3-SAT or 3-SUM are guaranteed hard under SETH, giving evidence that fast algorithms may not exist. This is weaker than unconditional hardness but much stronger than saying 'we haven't found a fast algorithm yet.'
Question 4 True / False
The Fine-Grained Complexity Conjecture (FGC) is that all NP-hard problems reduce to each other under fine-grained reductions. If FGC is true, then all NP-hard problems require essentially the same exponential time (possibly with different polynomial factors).
TTrue
FFalse
Answer: False
FGC is not universally accepted and is likely false. While many problems do reduce to k-SAT or 3-SUM and are thereby tied under SETH/3-SUM conjecture, some NP-hard problems may require fundamentally different time — for example, some may be solvable in 2^(sqrt(n)) (like certain graph coloring algorithms), while others seem to require 2^(Omega(n)). The fine-grained complexity landscape is stratified: different problems are believed to have different exponential bases or polynomial dependencies, explaining why the problem space is not flat. ETH and SETH describe specific hard anchors, not a universal hierarchy.