4
$\begingroup$

The most common method of proving that some problem, P, is at least as difficult as some other problem, Q, is to demonstrate that Q can be solved in terms of P (with the usual caveats for the complexity of the reduction itself).

In particular, I'm thinking about the fact that breaking RSA encryption is believed to be at least as difficult as factoring a composite number into primes, but nobody has ever figured out how to express prime factorization in terms of RSA decryption. My question is: if somebody wanted to go about proving that breaking RSA is at least as difficult as prime factorization without relying on reduction, what techniques might be available to them?

$\endgroup$
  • 1
    $\begingroup$ While a proof may not need to involve a reduction, the very notion of hardness is usually defined in terms of reducibility. That being said, descriptive complexity theory may serve as an example for how one might prove class membership without a reduction. $\endgroup$ – tobwin Feb 19 '18 at 1:34
1
$\begingroup$

As mentioned on Wikipedia, there is no known proof that breaking RSA is at least as difficult as prime factorization -- and there are reasons to believe it might not be. In other words, we don't currently expect any such proof to exist. See the reference listed in Wikipedia.

$\endgroup$
  • $\begingroup$ I think I may have worded the question confusingly. I know that there's no proof, but my question is: if somebody were interested in trying to find a proof that didn't involve a reduction, what methods might be available to them? I'm just using RSA breaking and prime factorization as an example, but the question is more general - what methods of proving relative complexity (ie, A is at least as hard as B) that don't involve reductions? $\endgroup$ – joshlf Jan 20 '18 at 0:31
  • $\begingroup$ @joshlf, there is reason to believe no such proof is likely to exist -- i.e., no method seems likely to work. If you're asking what's "available", of course all the axioms of mathematics are "available". Reductions are essentially the only tool we know for proving that problem A is at least as hard as problem B. $\endgroup$ – D.W. Jan 20 '18 at 1:24
  • $\begingroup$ Yeah, my question was essentially whether what you said - "Reductions are essentially the only tool we know for proving that problem A is at least as hard as problem B." - was true, and if not, what other tools were available. But that answers my question :) $\endgroup$ – joshlf Jan 20 '18 at 20:34

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.