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$ – Sasho Nikolov Dec 9 '14 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 '14 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$ – Joshua Grochow Dec 10 '14 at 7:21

Your Answer

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

Browse other questions tagged or ask your own question.