$\mathbf{NP}$-complete problems are worst-case hard. Their average-case counterpart are one-way functions. Is there an analogous one-wayness notion for $\mathbf{coNP}$-complete problems? More generally, a standard one-way function can be viewed as an average-case-hard (search) problem in $\mathbf{NP}$ relative to $\mathbf{P}$. Can this notion be extended to two arbitrary complexity classes?

  • 5
    $\begingroup$ While inverting a one-way function is hard-on-average, it does not mean that every hard-on-average problem represents a one-way function. Am I right? $\endgroup$ – M.S. Dousti Dec 5 '10 at 1:35
  • 3
    $\begingroup$ PS: I'm interested in your motivation. Could you please tell us why you care? $\endgroup$ – M.S. Dousti Dec 5 '10 at 1:39
  • 3
    $\begingroup$ You may be interested in the following paper of Pavan Aduri et al: cs.iastate.edu/~pavan/papers/acwcnc.pdf $\endgroup$ – Aaron Sterling Dec 5 '10 at 2:04
  • 2
    $\begingroup$ @Pooya: In addition, it might be the case that hard-on-average problems exist, but one-way functions do not. See the definition of Pessiland in cstheory.stackexchange.com/q/1026/873. $\endgroup$ – M.S. Dousti Dec 23 '10 at 13:20
  • 2
    $\begingroup$ As Sadeq said, it is not justified to call one-way functions the “average-case counterpart” of NP-complete problems. Inverting a fixed one-way function is an example of hard-on-average problems (by definition), but there are other problems which are hard on average. Because of this, I do not know what you are looking for. $\endgroup$ – Tsuyoshi Ito Jan 5 '11 at 2:18

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.