9

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

8
  • 5
    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? Commented Dec 5, 2010 at 1:35
  • 3
    PS: I'm interested in your motivation. Could you please tell us why you care? Commented Dec 5, 2010 at 1:39
  • 3
    You may be interested in the following paper of Pavan Aduri et al: cs.iastate.edu/~pavan/papers/acwcnc.pdf Commented Dec 5, 2010 at 2:04
  • 2
    @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. Commented Dec 23, 2010 at 13:20
  • 2
    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. Commented Jan 5, 2011 at 2:18

0

Your Answer

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