Proved
Established implication or scoped theorem in cited mathematics ↗
Observed Oct 10, 2026
Theorem · version 1
A truly subquadratic deterministic 3SUM algorithm
Earlier version 1. View current version 2 →
Statement
For every fixed ν, 3SUM on n integers with absolute value at most n^ν has a deterministic O(n^{1.9992})-time algorithm in the paper’s integer-operation model.
Assumptions
- Polynomially bounded integers; fixed ν; the algorithm and model of Theorem 22 and Corollary 26.
Scope
A fine-grained improvement for a problem already solvable in polynomial time; no SAT speedup or P versus NP resolution is claimed.
Evidence
Source reports
Connections
In this problem · publication v7
P versus NP →
Related result · Proved
This statement contributes context in its stated scope; it does not settle the canonical P versus NP question.
Scope: Deterministic 3SUM in O(n^{1.9992}) for polynomially bounded integers, in the cited integer-operation model.
This is one indexed assertion in its own scope. No disjoint solved fraction, strongest-known ranking or additional parent resolution is inferred.
Relationship not independently reviewed. This concerns its use in this problem.
Sources
Alman–Vassilevska Williams · Truly subquadratic 3SUM and subcubic APSP →
- Theorem 22 using Corollary 26; §1, numeric bounds; Acknowledgments and Methodology → · Original passage ↗
Recorded wording
For every fixed ν, 3SUM on n integers with absolute value at most n^ν has a deterministic O(n^{1.9992})-time algorithm in the paper’s integer-operation model.
paraphrase · Only metadata and original OpenMath paraphrases are published; proof PDFs remain at their source.
Josh Alman · Virginia Vassilevska Williams · Preprint · Publication date Oct 5, 2026
Source-reported preprint/project; independent mathematical assessment pending.
Alman–Vassilevska Williams · Truly subquadratic 3SUM and subcubic APSP — proof text ↗Manuscript / exposition · external
Revision & attribution
Source revision: arXiv-2610.06783v1. Observed Oct 10, 2026.
The authors credit an internal Anthropic Claude model with algorithm discovery and later Lean formalization. They describe their simplification, strengthening, extensions and mathematical responsibility.
Alman–Vassilevska Williams · Truly subquadratic 3SUM and subcubic APSP — proof text: arXiv-2610.06783v1. External source text. Its mathematical claims and independent OpenMath review are assessed separately.
History
Statement versions
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessment history · 1
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Proved
Established implication or scoped theorem in cited mathematics ↗
Observed Oct 10, 2026 · Source passage →
Record details
- Claim ID
- claim-pnp-three-sum-2026
- Statement version
- 1
- SHA-256
- 7b2889b2024a1d029b4da412b1e7c6d5d0338a7c291321e62647ae8a7582e957