# P3144: Is there a truly subcubic algorithm for weighted APSP?

- ID: `P3144`
- Reference: `truly-subcubic-apsp`
- Page: https://theoremdb.org/statements/P3144
- Record maturity: Reviewed problem with recorded work

## Problem

Does there exist \(\varepsilon>0\) and an \(O(n^{3-\varepsilon})\)-time algorithm for all-pairs shortest paths in directed \(n\)-vertex graphs with integer edge weights of polynomial magnitude and no negative cycle?

### Context

Known frontier: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP.

Open boundary: A fixed positive exponent saving remains unknown.

### Problem setup

- **Definition (APSP).** Compute the shortest-path distance for every ordered pair of vertices.
- **Definition (truly subcubic).** O(n^{3−ε}) for one fixed ε>0.
- **Remark.** The standard dynamic-programming and min-plus product approaches are cubic up to lower-order improvements. The target fixes polynomially bounded weights so bit complexity is explicit.

### What counts as a solution

- Give a correct truly subcubic algorithm in the stated word-RAM or bit model.
- Or prove an n^{3−o(1)} lower bound in a clearly specified standard model.

## Status

OPEN as checked on 2026-08-01. Strongest checked neighboring result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Exact unresolved remainder: A fixed positive exponent saving remains unknown. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (Current status and exact unresolved remainder).** OPEN as checked on 2026-08-01. Strongest checked neighboring result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Exact unresolved remainder: A fixed positive exponent saving remains unknown.

The problem was checked as open on 2026-08-01.

The strongest neighboring result found in the cited sources is: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP.

The exact unresolved remainder is: A fixed positive exponent saving remains unknown.

A complete resolution must meet the following acceptance conditions:
- Give a correct truly subcubic algorithm in the stated word-RAM or bit model.
- Or prove an n^{3−o(1)} lower bound in a clearly specified standard model.

### Background and intake notes

- Original intake status: OPEN as checked on 2026-08-01. Strongest checked neighboring result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Exact unresolved remainder: A fixed positive exponent saving remains unknown.
- The release review checked 2 structured sources on 2026-08-01.
- Equivalent-formulation queries: truly subcubic APSP open problem 2026; weighted all pairs shortest paths n 3 epsilon
- Strongest checked neighboring result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP.
- Exact unresolved remainder: A fixed positive exponent saving remains unknown.

### Other known results

- **Claim 2** (supported): The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. [1](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): The exact target, equivalent terminology, and 2025-2026 status evidence were checked on 2026-08-01. Strongest checked result: The best general algorithms improve cubic time by subpolynomial factors; many problems are subcubic-equivalent to APSP. Unresolved remainder: A fixed positive exponent saving remains unknown. [1](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): A fixed positive exponent saving remains unknown.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `truly-subcubic-apsp`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>R. Williams, Faster all-pairs shortest paths via circuit complexity, STOC 2014. main theorem https://arxiv.org/abs/1312.6680
   - Also cited at R. Williams, Faster all-pairs shortest paths via circuit complexity, STOC 2014. main theorem
   - preprint; primary source; arXiv:1312.6680, checked 2026-08-01; checked 2026-08-01
   - Source use: original_summary
   - Gives a subcubic improvement by a subpolynomial factor and explains the circuit connection.
   - Source used to assess the problem's recorded status.
   - For Is there a truly subcubic algorithm for weighted APSP?: This is the dated publication status for the canonical target Is there a truly subcubic algorithm for weighted APSP?.
   - Source named by the research packet.
2. <a id="reference-2"></a>Virginia Vassilevska Williams and Ryan Williams, “Subcubic Equivalences between Path, Matrix and Triangle Problems”. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science (2010), 645-654. DOI 10.1109/FOCS.2010.67. subcubic equivalence theorems https://doi.org/10.1109/FOCS.2010.67
   - journal_article; primary source; checked 2026-08-01
   - Source use: original_summary
   - Shows that a breakthrough would transfer to several central weighted graph problems.
   - Source used to assess the problem's recorded status.
   - For Is there a truly subcubic algorithm for weighted APSP?: Shows that a breakthrough would transfer to several central weighted graph problems.