Review waiting, please be patient. This may take 3 months or more, since drafts are reviewed in no specific order. There are 4,431 pending submissions waiting for review. If the submission is accepted, then this page will be moved into the article space. If the submission is declined, then the reason will be posted here. In the meantime, you can continue to improve this submission by editing normally. Where to get help If you need help editing or submitting your draft, please ask us a question at the AfC Help Desk or get live help from experienced editors. These venues are only for help with editing and the submission process, not to get reviews. If you need feedback on your draft, or if the review is taking a lot of time, you can try asking for help on the talk page of a relevant WikiProject. Some WikiProjects are more active than others so a speedy reply is not guaranteed. How to improve a draft Wikipedia:Contributing to Wikipedia – a basic overview on how to edit Wikipedia. Help:Wikitext – how to use the markup Help:Referencing for beginners – how to include references Wikipedia:Article development – how to develop your article Wikipedia:Writing better articles – how to improve your article Wikipedia:Verifiability – make sure your article includes reliable third-party sources You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Add tags to your draft Editor resources Easy tools: Citation bot (help) | Advanced: Fix bare URLs Reviewer tools Instructions · What links here · Fine Grained Complexity (talk: + · bio) · (log) · Copyvios report · reFill · Citation Bot · (Search: Google, Wikipedia) · Submitted 31 days ago by ~2026-27361-32 (talk: D · +) · Last edited 31 days ago by ~2026-27361-32

Fine-grained complexity is a subfield of computational complexity theory that studies the time required to solve computational problems, especially those within the class P. While classical complexity theory distinguishes problems by whether they contain polynomial-time algorithms (most known through the P versus NP problem), fine-grained complexity seeks to distinguish problems solvable in O(n) time from those requiring Θ(n²) or Θ(n³) time, and to identify the precise polynomial exponent of fundamental problems.

The theory of NP-completeness separates problems likely to require exponential time from those solvable in polynomial time, but it gives no way to distinguish between polynomial algorithms of different exponents.^[1][2] Fine-grained complexity addresses this by mimicking NP-completeness at a finer scale, using fine-grained reductions which show that a polynomial-factor speedup for one problem would yield a polynomial-factor speedup for another.^[1] Through a network of such reductions, the field identifies a small number of central problems whose best known algorithms are conjectured to be optimal; under these conjectures, the best known algorithms for many problems across seemingly unrelated areas must also be optimal.^[1][2]

The four most-used hypotheses are the Strong Exponential Time Hypothesis (SETH), the Orthogonal Vectors hypothesis (OV), the 3-SUM hypothesis, and the All-Pairs Shortest Paths (APSP) hypothesis.^[2] Hundreds of problems across computational geometry, string algorithms, dynamic graph algorithms, and data structures have been shown hard under one or more of these.^[2]

Classical complexity theory works well for separating problems we can solve in polynomial time from those we (probably) cannot. Within polynomial time, though, the fine-grained differences are lost as, for example, a linear-time algorithm and a cubic-time algorithm are both "polynomial," but for an input of size one billion, that's the difference between a fraction of a second and decades of computation.^[1]

The time hierarchy theorems establish that algorithms with more running time can solve strictly more problems: for every constant c, there exist problems solvable in O(n^c) time but not in O(n^c−ε) time for any ε > 0.^[3] But these theorems only show such problems exist; they don't identify which problems sit at which level. Nothing about them tells us whether edit distance, for instance, is one of the problems requiring Θ(n²) time or one that could in principle be done faster. No superlinear lower bound is known for any problem in NP in standard models of computation; even establishing that SAT requires more than linear time is open.^[2]

Meanwhile, many fundamental problems have textbook algorithms whose running times haven't been substantially improved in decades. Longest common subsequence and edit distance have been stuck at O(n²) since the 1970s.^[4] Determining whether three of n points in the plane lie on a line is also stuck at O(n²).^[5] Computing the diameter of a sparse graph is stuck at roughly O(mn).^[6]

Fine-grained complexity is, therefore, an attempt to give conditional answers. Instead of proving unconditionally that edit distance requires n² time, one proves that any algorithm faster than n^2−ε would refute SETH.^[7] The framework lets us organize hundreds of problems into a coherent picture and identify which ones rise and fall together.^[2]

The 3-SUM conjecture was introduced by Anka Gajentaan and Mark Overmars in 1995.^[5] They studied a class of computational geometry problems with O(n²) algorithms, conjectured that 3-SUM (the problem of deciding whether three numbers in a set sum to zero) needs Θ(n²) time, and showed that a faster algorithm for 3-SUM would yield faster algorithms for many geometric problems — including determining whether three of n points in the plane are collinear.^[5]

The Exponential Time Hypothesis (ETH) and Strong Exponential Time Hypothesis (SETH) were introduced by Russell Impagliazzo and Ramamohan Paturi in 2001.^[8] ETH says 3-SAT requires 2^Ω(n) time; SETH is a stronger statement, that for any ε > 0, some k-SAT cannot be solved in 2^(1−ε)n time.^[8] The same year, Impagliazzo, Paturi, and Zane proved the Sparsification Lemma,^[9] a technical tool that lets one assume k-SAT formulas have at most a linear number of clauses, which will be useful for later fine-grained reductions.

These hypotheses were originally about exponential-time algorithms, but in the next decade they became central to lower bounds for problems that already run in polynomial time.^[2]

In 2004, Ryan Williams gave the reduction that connected SETH to fine-grained complexity. He showed that solving the Orthogonal Vectors problem in n^2−ε time would refute SETH.^[10] This made OV a workhorse, as most SETH-based lower bounds reduce from OV rather than directly from k-SAT, because OV is much easier to reduce from.^[2]

Vassilevska Williams in 2010 showed that several cubic-time problems are equivalent under fine-grained reductions: APSP, Negative Triangle, and (min,+)-matrix multiplication.^[11] A faster algorithm for any one would give a faster algorithm for all of them. This subcubic equivalence class became a foundational example in the field.

The next decade saw a flood of results. Pătrașcu (2010) reduced 3-SUM to dynamic data structure problems.^[12] Roditty and Vassilevska Williams (2013) showed that approximating the diameter of a sparse graph to better than a factor of 3/2 in subquadratic time would refute SETH.^[13] Henzinger, Krinninger, Nanongkai, and Saranurak (2015) introduced the OMv conjecture as a unified source of hardness for dynamic problems.^[14] Tight SETH-based lower bounds were established for sequence problems including edit distance,^[7] longest common subsequence,^[15] Fréchet distance,^[16] and regular expression matching.^[17]

A newer direction studies the fine-grained complexity of average-case inputs of random instances rather than adversarial worst-case ones. Ball, Rosen, Sabin, and Vasudevan (2017) gave the first worst-case-to-average-case reductions in this setting,^[18] raising the possibility of cryptographic primitives based on fine-grained hardness. Boix-Adserà, Brennan, and Bresler (2019) extended this in their 2019 paper.^[19] Lower bounds for dynamic graph problems and connections to the cell-probe model of data structures continue to be active areas.

Fine-grained complexity uses asymptotic notation a bit differently from the rest of computer science. Standard Õ(·) usually hides polylogarithmic factors, but in fine-grained complexity it hides everything below polynomial:^[2]

${\displaystyle {\widetilde {O}}(f(n))=O\!\left(f(n)\cdot n^{o(1)}\right).}$

Results in this field are about polynomial exponents, and it usually doesn't matter whether something has log² n or log¹⁷ n factors.

Lower bounds are typically stated as n^{c − o(1)}, which means: no algorithm solves the problem in O(n^c−ε) time for any constant ε > 0. A typical conditional theorem reads: "Under hypothesis H, problem P requires n^c−o(1) time."

Algorithms are analyzed in the word RAM model with O(log n)-bit words.^[2]

Four hypotheses anchor most of the field. They are believed to be incomparable: nobody has proved that any one implies any other, and Carmosino et al. (2016) gave evidence that they really are distinct.^[20]

SETH says that for every ε > 0, there is some k such that k-SAT on n variables and m clauses cannot be solved in time O(2^(1−ε)n · poly(m)).^[8] Equivalently: there is no algorithm for general CNF-SAT that beats brute force by an exponential factor.

SETH is a stronger statement than ETH (which only says 3-SAT requires 2^Ω(n) time).^[8] It is the working hypothesis behind most fine-grained lower bounds for sequence and string problems, almost always going through OV.^[2]

The Orthogonal Vectors problem asks: given n Boolean vectors of dimension d = ω(log n), are there two whose inner product (over the integers) is zero?^[10] Brute force takes O(n²d) time. The fastest known algorithm, from Abboud, Vassilevska Williams, and Yu (2015), runs in time n^{2 − 1/Θ(log(d/log n))[21]} which is only barely subquadratic, and only for small d.

The OV hypothesis says that OV requires n^2−o(1) time. Williams' 2004 reduction^[10] showed that SETH implies the OV hypothesis, so falsifying OV would also falsify SETH.

The 3-SUM problem asks: given n integers, are there three of them that sum to zero?^[5] The classical algorithm runs in O(n²) time. The best known algorithms run in roughly n² / log² n time, both for integers^[22] and for real numbers.^[23] The 3-SUM hypothesis says that 3-SUM on integers in {−n³, …, n³} requires n^2−o(1) time.^[2] It is the source of conditional lower bounds for many computational geometry problems^[5] and a number of dynamic data structure problems.^[12]

APSP asks: given an n-vertex weighted graph, find the shortest-path distance between every pair of vertices. The classical Floyd–Warshall algorithm runs in O(n³) time.^[24] The best known algorithm, due to Williams (2014), runs in n³ / 2^{Ω(√log n)} time^[25] which is faster than n³ by a subpolynomial factor, but no truly subcubic algorithm is known. The APSP hypothesis says that APSP on graphs with O(log n)-bit edge weights requires n^3−o(1) time.^[11]

Several other hypotheses appear in the literature. The Boolean Matrix Multiplication (BMM) hypothesis says that combinatorial algorithms (loosely, those that don't use fast matrix multiplication) for n × n Boolean matrices need n^3−o(1) time.^[2] The Online Matrix-Vector multiplication (OMv) conjecture concerns an online setting where a Boolean matrix is preprocessed and then queried with vectors arriving one at a time; OMv is a particularly strong tool for proving lower bounds on dynamic problems.^[14] The k-Clique hypothesis concerns detecting k-cliques in graphs; the best known algorithm uses fast matrix multiplication.^[26] The Hitting Set hypothesis is a strengthening of OV introduced by Abboud, Vassilevska Williams, and Wang.^[27]

The implication structure of fine-grained complexity can be summarized as follows. SETH implies the OV hypothesis through Williams' 2004 reduction; the three central hypotheses OV, 3-SUM, and APSP are believed to be mutually incomparable, and each is the source of tight conditional lower bounds for a different cluster of problems.

File:Fine-grained complexity hypotheses.svg

Through OV, SETH implies n^2−o(1) lower bounds for many sequence and string problems: edit distance,^[7] longest common subsequence,^[15] Fréchet distance,^[16] dynamic time warping,^[15] and regular expression matching,^[17] among others. SETH also implies lower bounds for graph problems, including better-than-3/2 approximations to the diameter of sparse graphs.^[13]

In practice, most "SETH-based" lower bounds are really OV-based: the proof reduces from OV, and SETH enters only because SETH implies OV.^[2] Beyond the problems above, OV is the source of lower bounds for graph radius, sequence local alignment, and Hamming closest pair.^[2]

The 3-SUM hypothesis implies n^2−o(1) lower bounds for an extensive list of computational geometry problems: deciding whether three of n points in the plane are collinear, GeomBase, polygonal containment, and several motion planning variants.^[5] Pătrașcu (2010) and follow-up work also established 3-SUM-hardness for many dynamic data structure problems.^[12]

The APSP hypothesis implies n^3−o(1) lower bounds for Negative Triangle (which is in fact equivalent to APSP^[11]), graph radius and median in dense graphs, second shortest path, replacement paths, and shortest cycle.^[11] The equivalence between APSP, Negative Triangle, and (min,+)-matrix multiplication^[11] is one of the most well-known equivalence classes in the field.

The main technical tool is the fine-grained reduction itself. Given problems A and B with conjectured time bounds a(n) and b(n), a fine-grained reduction from A to B is an algorithm that solves A-instances of size n by making calls to B on instances of sizes n₁, …, n_k, such that the total work, or the time for the calls plus the overhead of the reduction, is below a(n) whenever each call to B runs faster than b(n_i).^[2] The point is that any subpolynomial improvement in B's running time would yield a subpolynomial improvement in A's.

A few techniques recur. Gadget reductions encode instances of one problem as structured instances of another, often by building graphs whose distances or other properties encode the answer to the original problem.^[10] Self-reductions reduce a problem to smaller instances of itself; the 3-SUM self-reduction via hashing is vital for worst-case-to-average-case results.^[18] On the algorithm side, the polynomial method (used by Williams in 2014 to break the n³ barrier for APSP)^[25] and fast matrix multiplication (with the matrix multiplication exponent ω) are responsible for most of the known improvements over textbook algorithms.^[2]

Most of the field studies worst-case running times, but a more recent line of work studies average-case complexity, or how hard problems are on random inputs rather than carefully chosen adversarial ones.^[18] There are two main motivations. First, worst-case lower bounds may not match what we see in practice; understanding average-case complexity gives a more nuanced picture of when problems are actually hard. Second, average-case fine-grained hardness opens up the possibility of cryptography based on these assumptions: one-way functions, proofs of work, and similar primitives whose security rests on plausible algorithmic hardness within polynomial time, rather than on the conjectured difficulty of factoring or discrete logarithm.^[18]

Ball, Rosen, Sabin, and Vasudevan (2017) gave the first worst-case-to-average-case reductions in fine-grained complexity, for variants of OV, 3-SUM, and APSP.^[18] Subsequent work by Boix-Adserà, Brennan, and Bresler (2019), among others, extended and refined these reductions.^[19] The area is still relatively young, and many basic questions are open.

Every major hardness hypothesis is open. Among the most consequential questions:

Is SETH true? This is the biggest one, since refuting SETH would simultaneously knock out a large fraction of the field's lower bound results.^[2] Substantially better-than-brute-force algorithms for k-SAT exist for any fixed k, but none break the 2^(1−ε)n barrier for unbounded k.^[8]

Are the major hypotheses independent of each other? Also open. There is no known reduction in either direction between, for example, the 3-SUM and APSP hypotheses. Carmosino et al. (2016) gave evidence that no such reduction exists in certain restricted forms,^[20] but this is not a proof of independence.

Closing gaps for specific problems. For many problems, large gaps remain between the best known upper and lower bounds. Closing these gaps — either by improving algorithms or by proving hardness from stronger hypotheses — is an active research direction.^[2]

• Computational complexity theory
• Exponential time hypothesis
• 3SUM
• Fine-grained reduction
• Parameterized complexity
• NP-completeness
• Shortest path problem

• Fine-Grained Complexity course page (Josh Alman, Columbia University)

Category:Computational complexity theory Category:Analysis of algorithms Category:Conjectures