Fine grained complexity
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 (most known through the P versus NP problem), fine-grained complexity seeks to distinguish problems solvable in O(n) time from those requiring Θ(n2) or Θ(n3) 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. 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.
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. 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. Hundreds of problems across computational geometry, string algorithms, dynamic graph algorithms, and data structures have been shown hard under one or more of these.
Wikipedia contributors, "Fine grained complexity", Wikipedia, revision 1386048549, retrieved 20 November 2026, source, CC BY-SA 4.0.