3
$\begingroup$

Are there interesting examples of (systems) of equations where it is known to be harder to find a solution (in terms of scaling with respect to problem size) than verifying a provided solution for correctness?

A non-expert may find it surprising that Stein, Riccati, Sylvester matrix equations with $d\times d$ matrices all have the same $O(d^3)$ complexity for solving as for verifying, wondering if this is a rule that holds more generally.

$\endgroup$
3
  • $\begingroup$ An interesting question that would certainly get more traction in math.SE or even mathoverflow. These are often famous problems. $\endgroup$ Nov 21 '20 at 1:51
  • $\begingroup$ I would say that having the same complexity is the exception, not the rule. $\endgroup$ Nov 22 '20 at 9:28
  • 1
    $\begingroup$ Might be a hard problem....sounds similar in spirit to P!=NP which is still unproved. Gradient descent and other iterative methods have same per-iteration complexity as verifying, so proving this would need establishing that for every cheap iteration method, the number of iterations to convergence grows with problem size $\endgroup$ Nov 22 '20 at 18:32
3
$\begingroup$

Your first paragraph is essentially the basis for the field of numerical cryptology. There, you want it to be very hard to crack an encryption (find solution), but you want it to be easy to decript a message for the person who holds the private keys (verify solution). Essentially you may look at all the mathematical problems underlying modern encryption (Elliptic Curves, RSA etc.)

$\endgroup$
2
$\begingroup$

Just take a linear system $Ax=b$ with given $A$ and $b$: If I give you a solution $x$, it takes $O(N^2)$ operations to verify that the left and right hand sides are equal. But for general matrices, it will take $O(N^3)$ operations to find a solution.

$\endgroup$
3
  • 1
    $\begingroup$ Good example. Remark: the true complexity of solving linear systems, however, is lower than that and still an open problem, because of Strassen-like sheananigans. One can see that the complexity of solving a linear system is bounded above by that of matrix multiplication (which current state-of-the-art results ensure is between $O(n^2 \log n)$ and $O(n^{2.38})$, if I am not mistaken, so strictly larger than that of verification). But as far as I know the complexity of solving a linear system and that of matrix multiplication are not proved to be equal. $\endgroup$ Nov 22 '20 at 9:32
  • $\begingroup$ Hm, this suggests that $\omega$ (for complexity of matrix multiplication) is not known to be greater than 2 - "[2007.10254] Solving Sparse Linear Systems Faster than Matrix Multiplication" arxiv.org/abs/2007.10254 $\endgroup$ Nov 22 '20 at 18:25
  • 1
    $\begingroup$ @FedericoPoloni Yes, that is correct. There are conjectures that state that matrix-matrix multiplication can be done in $O(n^{2+\epsilon})$ and it is conceivable that that is then also the complexity of solving a linear system. That would reduce the gap between solution and verification. At the same time, for problems of "reasonable" size, the gap stated above is probably a reasonably good guess: $O(N^3)$ vs $O(N^2)$ unless $N$ becomes large enough to make Strassen or Vinogradov algorithms competitive. $\endgroup$ Nov 22 '20 at 19:01

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.