- cc.complexity-theory np-hardness cr.crypto-security one-way-function average-case-complexity
- Updated Sun, 29 May 2022 17:39:43 GMT

This question considers a special class of problems in (NP,P-samplable). The question is:

Do there exists a problem $(L,\mu) \in \mbox{(NP,P-samplable)}$ such that:

- $L$ is $\rm{NP}$-complete, and
- $L$ is hard on instances sampled by $\mu$; That is, for any $\rm{BPP}$ algorithm $A$, any polynomial $p(\cdot)$, and any all sufficiently large $n$: $\Pr_{x \leftarrow \mu(1^n)}[A(1^n,x) = \chi_L(x)] < 1/p(n)$. (Here, $\chi_L(\cdot)$ denotes the characteristic function of $L$.)

Your answer can be based on any reasonable assumption, like:

- $\rm{P} \ne \rm{NP}$;
- one-way functions (or permutations) exist;
- factoring is hard;
- etc.

Another question is based on the following quote from On Basing One-Way Functions on NP-Hardness:

`More than two decades ago, Brassard ("Relativized Cryptography") observed that the inverting task associated with a one-way permutation cannot be NP-hard, unless NP = coNP.`

Is my understanding correct: It is saying that, there does not exist polynomial-time-computable permutations whose inverting is

worst-case NP-hardandhard-on-average(unless NP = coNP)?

If there exist some NP language L that's hard on the average on some distribution $\mu$, then by applying the standard reduction $f$ from L to 3SAT you get that 3SAT is hard on $f(\mu)$.

Your understanding is wrong. By saying that the inverting task for a function f is NP hard, one means that there is a polynomial-time algorithm A such that A can solve 3SAT on every input given black-box access to an inverter I that inverts f on a non-negligible fraction of the inputs.

- +1 – Thanks Boaz. I think I get it now. For self-reference, I'll summarize it here: The existence of any hard-on-average problem implies the existence of NPC hard-on-average problems. Moreover, since the inverter works correctly on a non-negligible fraction of the inputs, it is a heuristic (without efficiency constraints) as defined in Bogdanov's lecture notes. — Nov 27, 2010 at 06:14

External links referenced by this document: