52
$\begingroup$

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?

$\endgroup$
  • 7
    $\begingroup$ I think that many examples come from NP-complete problems that fall in P when we fix some parameters. For example, checking if a graph contains a clique of size $k$ for fixed $k$. The verification takes linear time, but unless P=NP, the search problem (polynomial) complexity depends on $k$ $\endgroup$ – Marzio De Biasi Oct 31 '15 at 20:06
  • 16
    $\begingroup$ We can verify that a list of $n$ integers is sorted with $n-1$ comparisons, but it takes $\Theta(n \log n)$ comparisons to sort an unsorted list. $\endgroup$ – Thomas supports Monica Nov 1 '15 at 1:15
  • 7
    $\begingroup$ Do you want it to be easy to verify both yes and no instances for decision problems? For 3SUM, while it is easy to verify yes instances in constant time, I don't know if it is easy to verify a no instance. Or are you thinking more along the lines of problems where there's a non-Boolean output, like matrix multiplication? (Matrix multiplication is an example of what you want if you allow randomized algorithms.) $\endgroup$ – Robin Kothari Nov 1 '15 at 2:14
  • 3
    $\begingroup$ "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." -- We also need to check that the 3 found numbers are actually part of the input. $\endgroup$ – hvd Nov 1 '15 at 16:34
  • 3
    $\begingroup$ Are there problems for which we know that verification is not easier? $\endgroup$ – Raphael Nov 1 '15 at 19:04
24
$\begingroup$

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 :))

$\endgroup$
  • 4
    $\begingroup$ Maybe it's fair to add that there is a randomized algorithm that runs in expected linear time (the Karger-Klein-Tarjan algorithm). $\endgroup$ – Sasho Nikolov Nov 2 '15 at 0:44
  • 2
    $\begingroup$ Also, in case anyone wants a link, this is the simplest linear-time MST verification algorithm I am aware of: webhome.cs.uvic.ca/~val/Publications/Algorithmica-MSTverif.ps. $\endgroup$ – Sasho Nikolov Nov 2 '15 at 0:52
20
$\begingroup$

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.

$\endgroup$
18
$\begingroup$

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.)

$\endgroup$
  • 2
    $\begingroup$ On the other hand, for matrix multiplication in a large enough field, there is a quadratic time randomized algorithm for verification, while the fastest running time for computing the product is n^omega. $\endgroup$ – Thatchaphol Nov 1 '15 at 10:10
  • 2
    $\begingroup$ @Thatchaphol: Yes, although many people believe omega=2... Also, it's widely recognized that Boolean matrix multiplication (i.e. computing matrix mult over the Boolean and-or semi-ring) has somewhat of a different nature than matrix multiplication over a field. $\endgroup$ – Joshua Grochow Nov 1 '15 at 15:41
16
$\begingroup$
  • 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)$.

$\endgroup$
  • 2
    $\begingroup$ Similar: determining if there is a duplicate element is $\Omega(n \log n)$ in the comparison model, but of course can be verified in $O(1)$. $\endgroup$ – SamM Nov 2 '15 at 8:15
  • $\begingroup$ @SamM: You mean verified in $O(n)$? What are you given exactly? I feel like you're making an unfair comparison. $\endgroup$ – Mehrdad Nov 3 '15 at 6:47
  • $\begingroup$ @Mehrdad good point; if you're given the value (rather than indices) it's $\Theta(n)$ to verify. I can see a good argument that this is the better way to look at it. $\endgroup$ – SamM Nov 3 '15 at 10:14
10
$\begingroup$

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, ...

$\endgroup$
9
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ the complement (compositeness) is even easier to witness! $\endgroup$ – Yonatan N Nov 20 '15 at 18:04
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.