<p><a href="https://doi.org/10.1145/2840728.2840746" rel="nofollow noreferrer">This paper</a> shows that there are verification algorithms for <strong>both</strong> YES and NO instances for 3 problems, including Max flow, 3SUM, and APSP, which are faster by a <strong>polynomial factor</strong> than the known bounds for computing the solution itself.</p>
<p>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.</p>

CC BY-SA 4.0
2015-11-01T01:27:39.457Z
2021-11-29T09:50:06.570Z
2021-11-29T09:50:06.570Z
Thatchaphol
<p>For some problems there seems to be no difference. In particular, <a href="http://ieee-focs.org/FOCS-2010-Proceedings/Subcubic-Equivalences-Between-Path-Matrix-and-Triangle-Problems.pdf">Vassilevska Williams &amp; Williams</a> show:</p>

<ul>
<li><p>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. </p></li>
<li><p>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). </p></li>
</ul>

<p>(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.)</p>

CC BY-SA 3.0
2015-11-01T10:10:23.400Z
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
CC BY-SA 3.0
2015-11-01T15:41:10.080Z
@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
CC BY-SA 3.0
2015-11-01T02:47:46.380Z
2015-11-01T02:47:46.380Z
Joshua Grochow
<ul>
<li><p>Deciding if a value exists in an array takes time $\Omega(n)$  (or $\Omega(\log n)$ if the array is sorted).</p>

<p>Verifying that an array contains the given value at a given position is possible in time $O(1)$.</p></li>
<li><p>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)$.</p></li>
</ul>

CC BY-SA 3.0
2015-11-02T08:15:43.233Z
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
CC BY-SA 3.0
2015-11-03T06:47:02.517Z
@SamM: You mean verified in $O(n)$? What are you given exactly? I feel like you're making an unfair comparison.
user541686
CC BY-SA 3.0
2015-11-03T10:14:57.563Z
@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
CC BY-SA 3.0
2015-11-01T19:03:36.477Z
2015-11-01T19:03:36.477Z
Raphael
<p>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 :))</p>

CC BY-SA 3.0
2015-11-02T00:44:13.703Z
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
CC BY-SA 3.0
2015-11-02T00:52:05.870Z
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
CC BY-SA 3.0
2015-11-01T03:07:18.040Z
2015-11-01T16:32:07.667Z
2015-11-01T16:32:07.667Z
Suresh Venkat
<p>I think that many examples come from NP-complete problems that fall in P when we <a href="https://en.wikipedia.org/wiki/Parameterized_complexity">fix one or more parameters</a>.</p>

<p>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.</p>

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

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

CC BY-SA 3.0
2015-11-03T08:51:41.463Z
2015-11-03T08:51:41.463Z
Marzio De Biasi
<p>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)$.</p>

CC BY-SA 3.0
2015-11-20T18:04:41.833Z
the complement (compositeness) is even easier to witness!
Yonatan N
CC BY-SA 3.0
2015-11-03T07:32:15.967Z
2015-11-03T07:32:15.967Z
Joe Bebel
<p>A <a href="http://arxiv.org/abs/1510.04622" rel="nofollow">paper by Abboud et al.</a> 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.</p>

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

<p>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.</p>

CC BY-SA 3.0
2015-11-20T10:12:36.057Z
2015-11-20T10:12:36.057Z
SamM
<p>For (search versions) of <strong>NP</strong>-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. </p>

<p>In <strong>P</strong>, 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: </p>

<ol>
<li><p><strong>3SUM:</strong> 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 <em>verification</em> 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. </p></li>
<li><p><strong>All-Pairs Shortest Paths:</strong>  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 <strong>3SUM.</strong> </p></li>
<li><p><strong>Linear Programming.</strong> 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.</p></li>
</ol>

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

CC BY-SA 3.0
2015-10-31T15:53:54.540Z
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
CC BY-SA 3.0
2015-10-31T20:06:45.367Z
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
CC BY-SA 3.0
2015-11-01T01:15:03.040Z
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 Steinke
CC BY-SA 3.0
2015-11-01T02:14:13.593Z
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
CC BY-SA 3.0
2015-11-01T02:52:28.133Z
@RobinKothari Good question! Originally, I only had yes instances in mind, but no instances can also be interesting.
Andras Farago
CC BY-SA 3.0
2015-11-01T16:34:11.080Z
"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
CC BY-SA 3.0
2015-11-01T19:04:28.440Z
Are there problems for which we *know* that verification is not easier?
Raphael
CC BY-SA 3.0
2015-11-02T02:32:30.303Z
Related question: http://cstheory.stackexchange.com/q/115/129
Joshua Grochow
CC BY-SA 3.0
2015-11-02T17:16:44.843Z
Answer to my earlier comment: rank selection resp. verification both have worst-case time complexity $\Theta(n)$.
Raphael
CC BY-SA 3.0
2015-11-03T02:33:08.720Z
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
CC BY-SA 3.0
2015-11-03T07:43:59.627Z
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
CC BY-SA 3.0
2015-11-03T17:22:08.423Z
@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
CC BY-SA 3.0
2015-11-05T04:42:19.213Z
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
CC BY-SA 3.0
2015-11-06T22:29:50.327Z
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
<cc.complexity-theory><ds.algorithms><reference-request>
For which problems in P is it easier to verify the result than to find it?
Andras Farago
# For which problems in P is it easier to verify the result than to find it?

(Asked by: username_0 on 2015-10-31)

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?

**Tags:** cc.complexity-theory, ds.algorithms, reference-request

> **Comments:**
> **username_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.  
> **username_2**: 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$  
> **username_3**: 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.  
> **username_4**: 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.)  
> **username_0**: @RobinKothari Good question! Originally, I only had yes instances in mind, but no instances can also be interesting.  
> **username_5**: "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.  
> **username_6**: Are there problems for which we *know* that verification is not easier?  
> **username_7**: Related question: http://cstheory.stackexchange.com/q/115/129  
> **username_6**: Answer to my earlier comment: rank selection resp. verification both have worst-case time complexity $\Theta(n)$.  
> **username_8**: 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?)  
> **username_9**: 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.  
> **username_10**: @username_6: 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.  
> **username_11**: 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  
> **username_12**: 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  

---

## 7 answers

### Answer by username_16 on 2015-11-01. Score: 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 :))

> **Comments:**
> **username_17**: Maybe it's fair to add that there is a randomized algorithm that runs in expected linear time (the Karger-Klein-Tarjan algorithm).  
> **username_17**: 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.  

---

### Answer by username_13 on 2015-11-01. Score: 23

[This paper](https://doi.org/10.1145/2840728.2840746) 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 by username_7 on 2015-11-01. Score: 20

For some problems there seems to be no difference. In particular, [Vassilevska Williams & Williams](http://ieee-focs.org/FOCS-2010-Proceedings/Subcubic-Equivalences-Between-Path-Matrix-and-Triangle-Problems.pdf) 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.)

> **Comments:**
> **username_13**: 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.  
> **username_7**: @username_13: 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.  

---

### Answer by username_6 on 2015-11-01. Score: 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)$.

> **Comments:**
> **username_14**: 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)$.  
> **username_15**: @username_14: You mean verified in $O(n)$? What are you given exactly? I feel like you're making an unfair comparison.  
> **username_14**: @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.  

---

### Answer by username_2 on 2015-11-03. Score: 12

I think that many examples come from NP-complete problems that fall in P when we [fix one or more parameters](https://en.wikipedia.org/wiki/Parameterized_complexity).

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 by username_18 on 2015-11-03. Score: 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)$.

> **Comments:**
> **username_19**: the complement (compositeness) is even easier to witness!  

---

### Answer by username_14 on 2015-11-20. Score: 3

A [paper by Abboud et al.](http://arxiv.org/abs/1510.04622) 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.


---

