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?

  • 5
    $\begingroup$ 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. $\endgroup$ Dec 9, 2014 at 6:01
  • $\begingroup$ 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. $\endgroup$
    – xivaxy
    Dec 9, 2014 at 6:18
  • $\begingroup$ 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... $\endgroup$ Dec 10, 2014 at 7:21
  • $\begingroup$ The same question was asked again here and got many insightful answers. $\endgroup$
    – badboul
    Nov 24, 2021 at 12:26


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.