 Theoretical Computer Science

# NP-Complete Hard-on-Average Problems

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$$.)

• $$\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-hard and hard-on-average (unless NP = coNP)? ## Solution

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.