# Is APSP verification easier than APSP?

In APSP, the input is an $$n$$-node directed weighted graph $$G$$, and the output is an $$n \times n$$ matrix holding pairwise shortest path distances between nodes in $$G$$. Define "APSP-Verification" as the problem where we get a graph $$G$$ and a matrix $$D$$, and the goal is to decide whether or not $$D$$ is the correct output of APSP on $$G$$. Is there an algorithm that solves this problem in $$O(n^{3-c})$$ time, for any absolute constant $$c>0$$? Alternately, taking the standard conjecture in fine-grained complexity that no algorithm solves APSP in $$O(n^{3-c})$$ time, can we prove that there is no such algorithm for APSP-Verification?

• It's a great and natural question. I don't think that this is known (I would be very interested if it is), but, as I'm sure you know, the answer to the analogous question is "yes" for 3-SUM (people.csail.mit.edu/virgi/6.s078/papers/nseth.pdf). – Huck Bennett Nov 6 at 23:05
• While I don't know how to solve APSP-verification in sub-cubic time, note that APSP can be verified in truly sub-cubic time with some additional short witness: Corollary 3 in the paper pointed out by Huck. – Alex Golovnev Nov 7 at 1:10