I was reading the Wikipedia page https://en.m.wikipedia.org/wiki/Random_self-reducibility and it states: "If an NP-complete problem is non-adaptively random self-reducible the polynomial hierarchy collapses to Σ3". I am trying to understand that statement. It seems to say if we find a problem where a random instance is hard a bunch of complexity classes are equal. Is this correct? Which complexity classes?

  • 1
    $\begingroup$ I don't think this question belongs to crypto.stackexchange: it is a question related to complexity, not cryptography, which might be more suited for the theoretical computer science stackexchange site. $\endgroup$ – Geoffroy Couteau Dec 31 '17 at 16:54
  • $\begingroup$ The search for hard random problems is inherint in cryptography. We have random self reduciability for discrete log. The difference between random and worst case is what makes knapsack crypto not work so well. This is very crypto oriented. $\endgroup$ – Meir Maor Dec 31 '17 at 17:53
  • $\begingroup$ Well, I've not downvoted your question or flagged it because I'm indeed not entirely sure, but I maintain my position: random self-reducibility is important in cryptography, sure, but not only and it is not the subject of cryptography. The type of question you ask is not studied in the cryptographic community, but in the complexity community, as is in general the case for questions related to complexity classes. My point is not to reject your question in principle, but rather to say that I think you'll have more chances of getting the answer you want if you ask the right community. $\endgroup$ – Geoffroy Couteau Dec 31 '17 at 18:40
  • $\begingroup$ Though my interest in this question stems from crypto, I will not oppose finding it a better home. $\endgroup$ – Meir Maor Dec 31 '17 at 21:13
  • $\begingroup$ Then I would suggest to leave this question here for some time if you feel like to, and if you do not end up getting answers, ask a moderator to move it - perhaps on cstheory.stackexchange.com. $\endgroup$ – Geoffroy Couteau Jan 2 '18 at 7:30

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.