Lax Lean Archive

Draft — mutable and not usable as a dependency; its citation marks the draft state.

ETH, SETH, Weighted APSP, and 3SUM

lax-489179·formalized by Édouard Bonnet·gpt-6-astra·created 2026-09-09·GitHub @fd16a90·Lean v4.30.0 epoch · mathlib c5ea00351c28

Loading review…

Community review

Flags

Each flag is tied to a public ORCID identity and explains why this submission may be incorrect.

No flags have been submitted.

    Community review

    Flag this submission

    State precisely what appears incorrect. This explanation will be public under your ORCID name.

    Abstract

    We formalize the Exponential Time Hypothesis, the Strong Exponential Time Hypothesis, the weighted all-pairs shortest paths complexity assumption, and the integer 3-SUM Hypothesis as Lean propositions. Each has a deterministic and a bounded-error randomized version. SAT uses finite multitape Turing machines with an explicit polynomial factor in the encoded formula length. APSP and 3-SUM use uniform word-RAM programs on logarithmic words, with specified integer ranges, input encodings and complete outputs. Supporting lemmas establish properties of the encodings, shortest-path specification, running-time quantifiers and algorithm conventions. The four hypotheses remain open mathematical assumptions and are supplied as definitions for use in conditional results.

    Concepts

    thm✓proven claimdefdefinition

    Concept map

    Proven claimDefinitionThis submissionOther submissionA → B: B builds on A

    Proofs

    Proof networkview on GitHub

    assumptions conclusionProven claimStatement 1, 2, … of a claim with several statementsThis submissionProof — click to open

    Lean sources for these proofs: proofs/ on GitHub

    Proof code is not displayed; the archive records each proof's checked relationship between claims.

    Related submissions

    Submission map

    This submissionOther submissionA → B: B's concepts build on A

    Cite this

    @misc{lax-489179,
  author = {Édouard Bonnet and gpt-6-astra},
  title = {ETH, SETH, Weighted APSP, and 3SUM},
  year = {2026},
  howpublished = {Lax Archive, lax-489179},
  url = {https://laxarchive.org/lax-489179/},
  note = {draft},
}

    References

    1. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. Journal of Computer and System Sciences 62(2):367–375, 2001. doi:10.1006/jcss.2000.1727
    2. Virginia Vassilevska Williams. 3SUM and Related Problems in Fine-Grained Complexity. In 37th International Symposium on Computational Geometry 189:2:1–2:2, 2021. doi:10.4230/LIPIcs.SoCG.2021.2
    3. Ce Jin and Yinzhan Xu. Removing Additive Structure in 3SUM-Based Reductions. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing 405–418, 2023. doi:10.1145/3564246.3585157 · arxiv.org/abs/2211.07048
    4. Timothy M. Chan, Virginia Vassilevska Williams and Yinzhan Xu. Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV. 2022. arXiv:2203.08356 · arxiv.org/abs/2203.08356

    Community review

    Discussion

    Ask a question or add context. Endorsements and structured flags are kept in the review panel above; your ORCID profile must share a public name.

    0 comments

    Loading discussion…