6
$\begingroup$

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-hard and hard-on-average (unless NP = coNP)?

$\endgroup$
12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – M.S. Dousti Nov 27 '10 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.