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?
-
5While 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 DoustiCommented Dec 5, 2010 at 1:35
-
3PS: I'm interested in your motivation. Could you please tell us why you care?– Sadeq DoustiCommented Dec 5, 2010 at 1:39
-
3You may be interested in the following paper of Pavan Aduri et al: cs.iastate.edu/~pavan/papers/acwcnc.pdf– Aaron SterlingCommented 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.– Sadeq DoustiCommented Dec 23, 2010 at 13:20
-
2As 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 ItoCommented Jan 5, 2011 at 2:18
|
Show 3 more comments