55

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?

Andras Farago
  • 11,396
  • 37
  • 70
  • 1
    We may also wonder what are the "easily checkable" instances. For example, one can turn the Circuit Value Problem into a search for a proof tree (a subcircuit proving the output is 0 or 1) then we may wonder what are the the pairs $\langle$circuits, input$\rangle$ that have a small (log?) proof tree. – Michaël Cadilhac Oct 31 '15 at 15:53
  • 7
    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$ – Marzio De Biasi Oct 31 '15 at 20:06
  • 17
    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. – Thomas Nov 01 '15 at 01:15
  • 7
    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.) – Robin Kothari Nov 01 '15 at 02:14
  • @RobinKothari Good question! Originally, I only had yes instances in mind, but no instances can also be interesting. – Andras Farago Nov 01 '15 at 02:52
  • 3
    "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. – hvd Nov 01 '15 at 16:34
  • 3
    Are there problems for which we know that verification is not easier? – Raphael Nov 01 '15 at 19:04
  • Related question: http://cstheory.stackexchange.com/q/115/129 – Joshua Grochow Nov 02 '15 at 02:32
  • 2
    Answer to my earlier comment: rank selection resp. verification both have worst-case time complexity $\Theta(n)$. – Raphael Nov 02 '15 at 17:16
  • 1
    For LP-- NO need for the dual solution.. Just construct the Simplex tableau corresponding to the primal solution $P$ that you have.. The tableau is just $B^{-1}A$ where $B$ is the $m \times m$ basis (for $P$) and $A$ is the given $m \times n$ coefficient matrix.. See the last row (the "reduced cost" row).. If every element in this row is non-negative (non-positive, depending on whether you are maximizing or minimizing), then your solution is optimal.. (Am I missing something?) – Sameer Gupta Nov 03 '15 at 02:33
  • 2
    If you augment the solution appropriately it becomes a linear task (in the size of augmented solution) to verify it. This is because NP is equal to the set of projections of LinTime: NP = $\exists$LinTime. So the more interesting problems are those where the size of the output is smaller than the running time of the fastest known algorithm. – Kaveh Nov 03 '15 at 07:43
  • 1
    @Raphael: Calculate the number of primes p <= N. A solution can be rejected if it is badly wrong, I think a solution with the wrong parity can be rejected relatively easily, but I think if I tell you the number is X, and the correct number might be X+2 or X-2, then there is nothing you can do other than doing the same calculation that I did. – gnasher729 Nov 03 '15 at 17:22
  • I think there are three things that matter: the finding time, the verification time, and the witness size. There are some problems where the finding time has to be large because the witness size is large, but the verification time is small relative to the witness size. An example of this is DFA Intersection Non-Emptiness. Link: http://cstheory.stackexchange.com/a/22563/14207 – Michael Wehar Nov 05 '15 at 04:42
  • 2
    There has been a lot of work on problems whose solution is easier to verify than to find, and on finding such "certifiers" efficiently, under the name "certifying algorithms" by Kurt Mehlhorn and collaborators, see e.g. https://www.mpi-inf.mpg.de/~mehlhorn/ftp/CertifyingAlgorithms.pdf – László Kozma Nov 06 '15 at 22:29

7 Answers7

27

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

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
  • 4
    Maybe it's fair to add that there is a randomized algorithm that runs in expected linear time (the Karger-Klein-Tarjan algorithm). – Sasho Nikolov Nov 02 '15 at 00:44
  • 2
    Also, in case anyone wants a link, this is the simplest linear-time MST verification algorithm I am aware of: http://webhome.cs.uvic.ca/~val/Publications/Algorithmica-MSTverif.ps. – Sasho Nikolov Nov 02 '15 at 00:52
23

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.

Emil Jeřábek
  • 17,430
  • 3
  • 61
  • 90
Thatchaphol
  • 1,130
  • 8
  • 18
20

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

Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • 2
    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. – Thatchaphol Nov 01 '15 at 10:10
  • 2
    @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. – Joshua Grochow Nov 01 '15 at 15:41
18

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

Raphael
  • 4,565
  • 28
  • 48
  • 2
    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)$. – SamM Nov 02 '15 at 08:15
  • @SamM: You mean verified in $O(n)$? What are you given exactly? I feel like you're making an unfair comparison. – user541686 Nov 03 '15 at 06:47
  • @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. – SamM Nov 03 '15 at 10:14
12

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

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
10

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

Joe Bebel
  • 2,295
  • 18
  • 18
3

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.

SamM
  • 1,685
  • 2
  • 14
  • 21