<p>Thinking of (seemingly) very different complexity of finding a solution to a NP problem and verifying it as the basis of practical cryptography, I am wondering if such separation is possible among deterministic polynomial class problems (P, FP, BPP).</p>

<p>For instance, solving a system of linear equations in <code>n</code> variables (by Gaussian elimination) has time complexity $C_s=O(n^3)$. However, verifying a solution obviously requires only $C_v=O(n^2)$.
Similarly for linear programming problems: $C_s=O(n^{3.5})$ for solving, $C_v=O(n^2)$ for verifying.</p>

<p>What are other polynomial problems with this property with respect to the best known solving and verifying algorithms? Are there any problems with much larger gap, e.g. $C_s=\Theta(C_v^2)$ or more?</p>

<p>More generally, which problems have the best known polynomial-time algorithms with complexity $\Theta(n^6)$ or more, where $n$ is the input size?</p>

CC BY-SA 3.0
2014-12-09T06:01:56.100Z
Solving linear equations has the same complexity as matrix multiplication so it might have complexity $n^{2 + o(1)}$. I am saying this to point out that without an appropriate notion of a reduction the evidence that the kind of gap you are talking about is inherent is very very weak.
Sasho Nikolov
CC BY-SA 3.0
2014-12-09T06:18:36.467Z
Surely, I assume the best _known_ algorithms, and hence the best _known_ gaps. Most practical algorithms are not shown to be the fastest possible. I put n^3 for linear system solution just for illustration of the idea.
xivaxy
CC BY-SA 3.0
2014-12-10T07:21:42.613Z
Rather than considering a gap in the time complexity - which, as Sasho points out, is hard to say anything about with certainty, even under reasonable complexity assumptions - it might make more sense to consider gaps in *parallel* time. For example, verifying a solution to a linear system can surely be done low down in the $\mathsf{NC}$ hierarchy, but finding a solution is $\mathsf{P}$-complete under $\mathsf{NC}$ (and even weaker, if I recall) reductions, so assuming $\mathsf{P} \neq \mathsf{NC}$ there is quite a complexity gap there...
Joshua Grochow
CC BY-SA 4.0
2021-11-24T12:26:21.083Z
The same question was asked again [here](https://cstheory.stackexchange.com/questions/32946/for-which-problems-in-p-is-it-easier-to-verify-the-result-than-to-find-it) and got many insightful answers.
badboul
<time-complexity><polynomial-time>
Complexity of solving vs verifying in P
xivaxy
# Complexity of solving vs verifying in P

(Asked by: username_0 on 2014-12-09)

Thinking of (seemingly) very different complexity of finding a solution to a NP problem and verifying it as the basis of practical cryptography, I am wondering if such separation is possible among deterministic polynomial class problems (P, FP, BPP).

For instance, solving a system of linear equations in `n` variables (by Gaussian elimination) has time complexity $C\_s=O(n^3)$. However, verifying a solution obviously requires only $C\_v=O(n^2)$.
Similarly for linear programming problems: $C\_s=O(n^{3.5})$ for solving, $C\_v=O(n^2)$ for verifying.

What are other polynomial problems with this property with respect to the best known solving and verifying algorithms? Are there any problems with much larger gap, e.g. $C\_s=\Theta(C\_v^2)$ or more?

More generally, which problems have the best known polynomial-time algorithms with complexity $\Theta(n^6)$ or more, where $n$ is the input size?

**Tags:** time-complexity, polynomial-time
> **Comments:**
> **username_1**: Solving linear equations has the same complexity as matrix multiplication so it might have complexity $n^{2 + o(1)}$. I am saying this to point out that without an appropriate notion of a reduction the evidence that the kind of gap you are talking about is inherent is very very weak.  
> **username_0**: Surely, I assume the best _known_ algorithms, and hence the best _known_ gaps. Most practical algorithms are not shown to be the fastest possible. I put n^3 for linear system solution just for illustration of the idea.  
> **username_2**: Rather than considering a gap in the time complexity - which, as Sasho points out, is hard to say anything about with certainty, even under reasonable complexity assumptions - it might make more sense to consider gaps in *parallel* time. For example, verifying a solution to a linear system can surely be done low down in the $\mathsf{NC}$ hierarchy, but finding a solution is $\mathsf{P}$-complete under $\mathsf{NC}$ (and even weaker, if I recall) reductions, so assuming $\mathsf{P} \neq \mathsf{NC}$ there is quite a complexity gap there...  
> **username_3**: The same question was asked again [here](https://cstheory.stackexchange.com/questions/32946/for-which-problems-in-p-is-it-easier-to-verify-the-result-than-to-find-it) and got many insightful answers.  

---

## 0 answers

