For which problems in P is it easier to verify the result than to find it?

Question

For (search versions) of NP-complete problems, verifying a solution is clearly easier than finding it, since the verification can be done in polynomial time, while finding a witness takes (probably) exponential time.

In P, however, the solution can also be found in polynomial time, so it does not seem obvious when is the verification faster than finding the solution. In fact, different problems seem to behave differently from this point of view. Some examples:

1. 3SUM: given $n$ input numbers, find 3 among them that sum to 0. As far as I know, the fastest known algorithm runs in $O(n^{2-o(1)})$ time, and this order is conjectured optimal. On the other hand, the verification of a solution is much faster, since all we need to do is just to check that the 3 found numbers indeed sum to 0.

2. All-Pairs Shortest Paths: given a graph with edge weights, compute its shortest path distance matrix. Once such a matrix is given, can it be checked faster that it is indeed the correct distance matrix, than re-computing it? My guess is that the answer is perhaps yes, but it is certainly less obvious than for 3SUM.

3. Linear Programming. If a claimed optimal solution is given, checking it is easier than re-computing it, when auxiliary information is also given (an optimal dual solution). On the other hand, if only the primal solution is available, it is not clear if one can check it faster, than actually solving the LP.

Question: what is known about this subject? That is, when is it easier to verify a solution for a problem in P, than finding the solution?

Answer 1

it is known that given a graph G and a tree T, it can be verified in linear time that T is a minimum spanning tree of G. But we don't yet have a deterministic linear time algorithm to compute the MST. Of course the gap is tiny (1 vs $\alpha(n)$), but it's still there :))

Answer 2

This paper shows that there are verification algorithms for both YES and NO instances for 3 problems, including Max flow, 3SUM, and APSP, which are faster by a polynomial factor than the known bounds for computing the solution itself.

There is a class of problems, namely the ones which improving the running time is SETH-hard, whose the running time for verifying NO instances is unlikely to be significantly faster than the time for computing the solution, otherwise the conjecture from this paper called Nondeterministic Strong Exponential Time Hypothesis would fail.

Answer 3

For some problems there seems to be no difference. In particular, Vassilevska Williams & Williams show:

• for Boolean matrix multiplication, computing the matrix product and verifying the matrix product subcubic-equivalent, meaning that they either both have subcubic-time algorithms or neither of them do.

• The same is true for matrix product computation and verification over any "extended (min,+) structure" (see paper for the definition, but this includes lots of natural problems).

(Now, of course, it's possible that these problems all have subcubic algorithms, and then there might be a polynomial difference between computing and verifying, but for these problems there can't be a cubic difference. And it seems plausible to me that in fact they all require essentially cubic time.)

Answer 4

• Deciding if a value exists in an array takes time $\Omega(n)$ (or $\Omega(\log n)$ if the array is sorted).

  Verifying that an array contains the given value at a given position is possible in time $O(1)$.

• Sorting (in the comparison model) takes time $\Omega(n \log n)$, but verifying that an array or list is sorted is possible in time $O(n)$.

Answer 5

I think that many examples come from NP-complete problems that fall in P when we fix one or more parameters.

For example, checking if a graph contains a clique of size $k$ is NP-complete if $k$ is part of the input, polynomial-time solvable if $k$ is fixed.

For any fixed $k$, the verification takes linear time, but unless $P=NP$, the search problem (polynomial) complexity depends on $k$ ( $\Omega(n^k) )$.

Other examples: finding an Hamiltonian path of length $k$, coloring on bounded treewidth graphs, ...

Answer 6

Deciding primality: the best known variant of AKS appears to decide primality in time $\tilde{O}(n^6)$, whereas the classical Pratt certificate of primality implies primality can be decided in nondeterministic time $\tilde{O}(n^3)$.

Answer 7

A paper by Abboud et al. recently accepted to SODA 2016 shows that subtree isomorphism cannot be solved in $O(n^{2-\epsilon})$ time unless the strong exponential time hypothesis is false. Of course, we can verify an isomorphism in linear time.

In other words, the SETH gives us a natural problem in $\sf{P}$ with an $\Omega(n^{1-\epsilon})$ gap between finding and verifying.

In particular, a $O(n^2/\log n)$ algorithm is known for rooted, constant-degree trees (for which Abboud et al.'s lower bound results still apply). So under SETH, the almost linear find-verify gap is essentially tight for this problem.