8

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

Turbo
  • 12,812
  • 1
  • 19
  • 68
Pooya Farshim
  • 119
  • 3
  • 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? – Sadeq Dousti Dec 05 '10 at 01:35
  • 3
    PS: I'm interested in your motivation. Could you please tell us why you care? – Sadeq Dousti Dec 05 '10 at 01:39
  • 3
    You may be interested in the following paper of Pavan Aduri et al: http://www.cs.iastate.edu/~pavan/papers/acwcnc.pdf – Aaron Sterling Dec 05 '10 at 02:04
  • @Aaron: Thanks for the reference. It seems to be dealing with a lot of relevant topics. – Pooya Farshim Dec 22 '10 at 01:59
  • @Pooya: From CLRS: "We define an abstract problem $Q$ to be a binary relation on a set $I$ of problem instances and a set $S$ of problem solutions." So, a problem is not a function, and a hard-on-average problem is not necessarily a one-way function. – Sadeq Dousti Dec 22 '10 at 09:15
  • 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 http://cstheory.stackexchange.com/q/1026/873. – Sadeq Dousti Dec 23 '10 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. – Tsuyoshi Ito Jan 05 '11 at 02:18
  • Thanks. So the difference is if instance/solution pairs can be generated easily. Now if we always require this on top of average-case hardness, do we arrive at a reasonable generalisation of OWFs? – Pooya Farshim Sep 22 '11 at 19:22

0 Answers0