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

<p>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.</p>

CC BY-SA 2.5
2010-11-27T06:14:18.177Z
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](http://dimacs.rutgers.edu/~adib/538/lec10.pdf).
Sadeq Dousti
CC BY-SA 2.5
2010-11-27T04:30:03.467Z
2010-11-27T04:30:03.467Z
Boaz Barak
<p>This question considers a special class of problems in <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo:N#nppsamp" rel="nofollow noreferrer">(NP,P-samplable)</a>. The question is:</p>
<blockquote>
<p>Do there exists a problem <span class="math-container">$(L,\mu) \in \mbox{(NP,P-samplable)}$</span> such that:</p>
<ul>
<li><span class="math-container">$L$</span> is <span class="math-container">$\rm{NP}$</span>-complete, and</li>
<li><span class="math-container">$L$</span> is hard on instances sampled by <span class="math-container">$\mu$</span>; That is, for any <span class="math-container">$\rm{BPP}$</span> algorithm <span class="math-container">$A$</span>, any polynomial <span class="math-container">$p(\cdot)$</span>, and any all sufficiently large <span class="math-container">$n$</span>:
<span class="math-container">$\Pr_{x \leftarrow \mu(1^n)}[A(1^n,x) = \chi_L(x)] &lt; 1/p(n)$</span>. (Here, <span class="math-container">$\chi_L(\cdot)$</span> denotes the characteristic function of <span class="math-container">$L$</span>.)</li>
</ul>
</blockquote>
<p>Your answer can be based on any reasonable assumption, like:</p>
<ul>
<li><span class="math-container">$\rm{P} \ne \rm{NP}$</span>;</li>
<li>one-way functions (or permutations) exist;</li>
<li>factoring is hard;</li>
<li>etc.</li>
</ul>
<p>Another question is based on the following quote from <a href="http://www.wisdom.weizmann.ac.il/%7Eoded/p_aggm.html" rel="nofollow noreferrer">On Basing One-Way Functions on NP-Hardness</a>:</p>
<p><code>More than two decades ago, Brassard (&quot;Relativized Cryptography&quot;) observed that the inverting task associated with a one-way permutation cannot be NP-hard, unless NP = coNP.</code></p>
<blockquote>
<p>Is my understanding correct: It is saying that, there does not exist polynomial-time-computable permutations whose inverting is <strong>worst-case NP-hard</strong> and <em>hard-on-average</em> (unless NP = coNP)?</p>
</blockquote>

<cc.complexity-theory><np-hardness><cr.crypto-security><one-way-function><average-case-complexity>
NP-Complete Hard-on-Average Problems
Sadeq Dousti
# NP-Complete Hard-on-Average Problems

(Asked by: username_0 on 2010-11-26)

This question considers a special class of problems in [(NP,P-samplable)](http://qwiki.stanford.edu/index.php/Complexity_Zoo:N#nppsamp). 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](http://www.wisdom.weizmann.ac.il/%7Eoded/p_aggm.html):

`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)?

**Tags:** cc.complexity-theory, np-hardness, cr.crypto-security, one-way-function, average-case-complexity


---

## 1 answers

### Answer by username_1 on 2010-11-27. Score: 13 | Accepted answer

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.

> **Comments:**
> **username_0**: 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](http://dimacs.rutgers.edu/~adib/538/lec10.pdf).  

---

