# A generalisation of one-wayness

$\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?

• 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? – M.S. Dousti Dec 5 '10 at 1:35
• PS: I'm interested in your motivation. Could you please tell us why you care? – M.S. Dousti Dec 5 '10 at 1:39
• You may be interested in the following paper of Pavan Aduri et al: cs.iastate.edu/~pavan/papers/acwcnc.pdf – Aaron Sterling Dec 5 '10 at 2:04
• @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. – M.S. Dousti Dec 23 '10 at 13:20
• 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. – Tsuyoshi Ito Jan 5 '11 at 2:18