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.

Improve this question
$\endgroup$
3
  • $\begingroup$ An interesting question that would certainly get more traction in math.SE or even mathoverflow. These are often famous problems. $\endgroup$
    – user20857
    Nov 21, 2020 at 1:51
  • $\begingroup$ I would say that having the same complexity is the exception, not the rule. $\endgroup$
    – Federico Poloni
    Nov 22, 2020 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$
    – Yaroslav Bulatov
    Nov 22, 2020 at 18:32

2 Answers 2

Reset to default
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.)

Improve this answer
$\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.

Improve this answer
$\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$
    – Federico Poloni
    Nov 22, 2020 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$
    – Yaroslav Bulatov
    Nov 22, 2020 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$
    – Wolfgang Bangerth
    Nov 22, 2020 at 19:01

Your Answer

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

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