Proving Algorithmic Optimality via Complexity Conjectures

392 concepts324 papers2 proposals

For decades, theoretical computer science has faced a frustrating impasse. We want to prove exactly how much time an algorithm requires to solve a problem, but proving absolute, unconditional lower bounds—such as showing a problem definitely cannot be solved in linear time—is notoriously difficult. It often requires resolving deep, open questions like $P \neq NP$.

To bypass this barrier, researchers have developed a powerful paradigm: conjecture-dependent hardness. Instead of trying to prove absolute lower bounds from scratch, we anchor the difficulty of a problem to a few widely believed, highly scrutinized computational hypotheses. By constructing precise reductions from these foundational conjectures, we can declare an algorithm "optimal" relative to the state of the art. If you want to beat the algorithm, you first have to prove a foundational conjecture false.

The Impasse of Absolute Lower Bounds

In classical complexity theory, we typically classify problems into broad buckets like $P$ (efficiently solvable) and $NP$-hard (likely intractable). But this framework is too coarse for practical algorithm design. If a problem is in $P$, is it solvable in linear time $O(n)$, quadratic time $O(n^2)$, or cubic time $O(n^3)$?

To answer this, we need fine-grained lower bounds. However, proving that a problem requires quadratic time unconditionally is currently beyond our mathematical reach. As noted by Iyad A. Kanj et al. in their work on constraint satisfaction, this reliance on unproven conjectures stems from our inability to provide absolute guarantees on computational hardness. Stefan Mengel similarly points out that without these assumptions, a significant gap remains in our fundamental understanding of whether algorithmic bottlenecks are inherent mathematical properties or merely limits of current human ingenuity.

Conjecture-dependent hardness solves this by building a web of relative difficulty. We assume a core problem is hard, and then we prove that if our target problem could be solved any faster, the core problem would also become easier.

The Workhorse Conjectures

To establish these conditional lower bounds, the field relies on a handful of central hypotheses. Each serves as an anchor for a different regime of complexity.

The Exponential Time Hypothesis (ETH)

ETH posits that the classic 3-SAT problem cannot be solved in subexponential time ($2^{o(n)}$). This hypothesis is frequently used to prove that existing "slow" algorithms are actually the best possible.

For instance, Michal Pilipczuk et al. used ETH to establish a double-exponential lower bound ($2^{2^{o(k)}}$) for the Edge Clique Cover problem, demonstrating that existing, seemingly sluggish parameterized algorithms are optimal. Similarly, Alexander Golovnev et al. leveraged ETH to show that fundamental graph embedding problems cannot be solved faster than a brute-force $n^{O(n)}$ search.

The Strong Exponential Time Hypothesis (SETH)

While ETH focuses on exponential boundaries, SETH sharpens the focus to exact polynomial exponents. It asserts that as the clause size $k$ grows, $k$-SAT requires $2^{n(1-o(1))}$ time.

This assumption is a powerful tool for analyzing problems inside $P$. For example, Josh Alman et al. applied SETH to the fine-grained complexity of training Large Language Models, proving a sharp transition where gradient computation becomes fundamentally quadratic when matrix entries are large. In string processing, Laurent Feuilloley et al. used SETH to explain why text indexing with errors suffers from an inescapable exponential dependency on the number of allowed mismatches.

The Unique Games Conjecture (UGC)

Introduced by Subhash Khot, the UGC serves as the bedrock for understanding the limits of approximation algorithms. Instead of asking how fast we can find an exact solution, UGC helps define the mathematical boundaries of how close an efficient algorithm can get to the optimal answer for graph partitioning and cut problems.

[ Foundational Conjectures ]
       /        |        \
     ETH      SETH       UGC
      |         |         |
[Graph Embed.] [LLM Training] [Graph Cuts]
[Clique Cover] [Text Indexing] [Approx. Coloring]

Building Intuition: Fine-Grained Reductions

The mechanism that makes conjecture-dependent hardness work is the fine-grained reduction.

In classical complexity, a reduction can introduce significant polynomial overhead (e.g., transforming an input of size $n$ into an instance of size $n^4$). This is perfectly fine if you only care about distinguishing polynomial time from exponential time.

However, if you want to prove that a problem requires exactly quadratic time ($O(n^2)$), a classical reduction is too blunt. A fine-grained reduction must preserve the exact quantitative relationship between the problems. It ensures that an algorithmic speedup of even a tiny factor ($n^{\epsilon}$) on the target problem would immediately yield a forbidden speedup on the source conjecture.

Consider the Viterbi algorithm, a cornerstone of sequence decoding in machine learning. For decades, its quadratic runtime went unimproved. Arturs Backurs et al. explained this stagnation by demonstrating a fine-grained reduction from fundamental graph problems to sequence decoding. They showed that any significant improvement to the Viterbi runtime would imply a breakthrough in solving All-Pairs Shortest Paths, effectively proving that the standard implementation is conditionally optimal.

A similar dynamic occurs in automated planning and verification. Krishnendu Chatterjee et al. mapped the fine-grained complexity of fundamental planning problems, showing that their exact polynomial requirements are tightly bound to unverified but widely accepted combinatorial conjectures like Boolean Matrix Multiplication (BMM).

The Web of Hardness

The ultimate power of this approach lies in its interconnectedness. By tying the hardness of disparate problems back to a few core hypotheses, computer scientists create a unified landscape of complexity.

If an algorithmist manages to design a faster algorithm for counting graph patterns, or approximating graph coloring, or parsing non-semiring frameworks, they do not just solve a single isolated problem. Because of the tight reductions established by researchers, that breakthrough would ripple backward, collapsing the foundational conjectures themselves.

As long as those core conjectures stand up to scrutiny, conditional lower bounds give us the confidence to stop searching for faster algorithms where none can exist, proving that our current approaches are already as good as they can get.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 328 papers
  2. Version 1 · 2026-10-04 · 401 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_conjecture_dependent_hardness_d8fd7bf3,
  title = {conjecture-dependent hardness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/conjecture-dependent-hardness/rdr_d8fd7bf33b414d7e8bbba957e56fb5a7},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_conjecture_dependent_hardness_d8fd7bf3_v2,
  title = {conjecture-dependent hardness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/conjecture-dependent-hardness/rdr_d8fd7bf33b414d7e8bbba957e56fb5a7/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake