Proved
Established implication or scoped theorem in cited mathematics ↗
Observed Oct 10, 2026
Theorem · version 1
A truly subcubic deterministic APSP algorithm
Earlier version 1. View current version 2 →
Statement
For every fixed ν, all-pairs shortest paths on directed n-vertex graphs with integer edge weights of absolute value at most n^ν and no negative cycles can be computed deterministically in O(n^{2.9995}) time.
Assumptions
- Fixed polynomial weight bound; directed graphs with no negative cycles; the integer-operation model of Theorem 22.
Scope
A fine-grained algorithmic improvement within polynomial time; real-weight and randomized variants have separate guarantees.
Evidence
Source reports
Connections
In this problem · publication v7 · Selected context
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 APSP in O(n^{2.9995}) for fixed polynomial integer-weight bounds and no negative cycles.
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; abstract; §1.2; Acknowledgments and Methodology → · Original passage ↗
Recorded wording
For every fixed ν, all-pairs shortest paths on directed n-vertex graphs with integer edge weights of absolute value at most n^ν and no negative cycles can be computed deterministically in O(n^{2.9995}) time.
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-apsp-2026
- Statement version
- 1
- SHA-256
- 09ebce71685a57056be78484727b4c57caaf1f13396f1b4d31dfbb1300665e4a