The Strong Exponential Time Hypothesis (SETH) conjectures that 3-SAT on n variables cannot be solved faster than 2^(cn) for some constant c > 0. If SETH is true, what does it imply about the existence of 'faster' algorithms for other NP-complete problems?
AIf SETH is true, all NP-complete problems can be solved in O(2^(n/2) * poly(n)) time
BSETH implies specific polynomial lower bounds for problems in P: if OV can be reduced to k-SAT, then OV cannot be solved faster than O(n^2 - epsilon) for small epsilon
CSETH only applies to SAT and has no consequences for other problems
DSETH is equivalent to P != NP, so verifying it would solve the Millennium Prize
SETH is a quantitative strengthening of P != NP that makes precise predictions about SAT's complexity. Fine-grained reductions take a fast algorithm for problem X and convert it into a fast SAT solver, contradicting SETH. For example, if Orthogonal Vectors (an NP-hard problem in the streaming model) could be solved in O(n^2 - epsilon) time, then — via a known reduction — 3-SAT could be solved in O(2^((1-delta)n)) time for some delta > 0, contradicting SETH. This creates a hierarchy of conditional hardness: problems are proven hard assuming SETH, giving explanations for why efficient algorithms have eluded discovery despite significant effort.
Question 2 True / False
The All-Pairs Shortest Paths (APSP) problem computes shortest distances between all pairs of vertices in an n-vertex graph. The best known algorithm runs in O(n^3 / log^2 n) time. Fine-grained complexity conjectures that APSP requires O(n^3 - epsilon) time for any epsilon > 0 under SETH. If this conjecture is true and there is a reduction from APSP to Problem X, then Problem X must require super-quadratic time.
TTrue
FFalse
Answer: True
This is the essence of conditional hardness: if you reduce APSP to your problem X in, say, O(n^2 poly(log n)) time, and APSP has a O(n^3 - epsilon) conditional lower bound, then X requires at least O(n^2 - epsilon) time (up to polynomial factors). Many important problems — 3-SUM, LCS, edit distance, substring matching — have been shown to reduce to APSP, suggesting they all share the same O(n^2) hardness barrier. These are not unconditional lower bounds, but they explain why a century of algorithmic work has not beaten the obvious quadratic algorithms.
Question 3 Short Answer
Explain the 3-SUM problem and why it is a central conjecture point for fine-grained complexity.
Think about your answer, then reveal below.
Model answer: The 3-SUM problem asks: given a set of n integers, do three of them sum to zero? The trivial algorithm fixes one element and uses a two-pointer technique on the sorted array, taking O(n^2) time. Despite intensive effort, no algorithm substantially faster than O(n^2) is known, even probabilistically. The 3-SUM conjecture states that 3-SUM requires O(n^2 - epsilon) time. Many problems reduce to 3-SUM: offline range search, some geometric problems, and substring matching. Fine-grained reductions from 3-SUM to other problems imply those problems are as hard. 3-SUM is empirically one of the strongest conjecture anchors: if true, it explains quadratic-time barriers across multiple domains.
The 3-SUM conjecture is slightly weaker than SETH but often more directly applicable to practical problems. It sits at the nexus of multiple reduction chains, making it a keystone conditional assumption for fine-grained complexity.
Question 4 True / False
A fine-grained reduction from Problem A to Problem B is an algorithm that, given a solver for B running in time T_B, solves A in time T_A that is comparable to T_B up to lower-order factors. This allows the structure of lower bounds to be transferred: if A has a conditional lower bound then B must too.
TTrue
FFalse
Answer: True
This is the operational definition of fine-grained reduction. Unlike NP-hardness reductions which are polynomial-time mappings of instances, fine-grained reductions are algorithmic: they show that faster algorithms for one problem would yield faster algorithms for another. If A reduces to B and A has a conditional lower bound (e.g., under SETH or 3-SUM conjecture), then B must be at least as hard. Building a web of reductions establishes a hierarchy of conditional hardness that explains why many problems resist faster algorithms — they are all equivalent under the reductions, pointing to fundamental barriers.