7

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?

xivaxy
  • 243
  • 1
  • 4
  • 5
    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 Dec 09 '14 at 06:01
  • 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 Dec 09 '14 at 06:18
  • 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 Dec 10 '14 at 07:21
  • The same question was asked again here and got many insightful answers. – badboul Nov 24 '21 at 12:26

0 Answers0