<p>I don't know the answer to Question (1)---I suspect there is no such reduction.  But I have a couple of points to make.</p>

<p>A non-adaptive random self-reduction (to the uniform distribution) is a poly-time randomized algorithm $R$ which, given an arbitrary instance $x$ of length $n$ for the decision problem for $L$, produces a list $y^1, \ldots, y^{q(n)}$ of instances of some second length $\ell(n)$.  We have the properties that </p>

<p>(i) each $y^i$ generated by $R$ is individually uniformly distributed, for any fixed input $x$ (although there may be complicated dependence between the $y^i$s, which in some way "encodes" $x$);</p>

<p>(ii) there is a second poly-time algorithm $R'$ which, given $y^1, \ldots, y^q$ along with their $L$-membership values $b^1, \ldots, b^q$ ($b_i = [y_i \in L]$), outputs the desired value $[x \in L]$.</p>

<p>Feigenbaum and Fortnow <a href="http://www.cs.uchicago.edu/~fortnow/papers/rsr.pdf" rel="nofollow">prove</a> that if an $NP$-complete language has such a reduction then the Polynomial Hierarchy collapses. The argument applies to other target distributions, not just the uniform distribution. </p>

<p>Now my first point (regarding your Question (2)) is that their result directly gives evidence for the difficulty of showing a worst-case to average-case connection for proof systems certifying unsatisfiability of Boolean formulas.  Because the most natural way you'd try to argue that random unsatisfiable formulas are hard to refute (assuming $NP \neq coNP$), is by exhibiting a random self-reduction as above.  Now in the study of proof systems, it might be natural to allow the recovery algorithm $R'$ to be nondeterministic, for example; I believe the [FF] analysis techniques would still apply, but this would take verification after defining things carefully.</p>

<p>My second point is that non-adaptive random self-reductions as above are not the only way to establish average-case hardness of a language $L$ (assuming its worst-case hardness).  There is also the more general notion of a <em>self-correction</em> reduction, which converts any mostly-correct algorithm for $L$ into a fully-correct algorithm, but which does not guarantee that its individual queries be distributed according to any particular distribution (they may depend heavily on the input $x$).  Bogdanov and Trevisan <a href="http://theory.stanford.edu/~trevisan/pubs/redux-sicomp.pdf" rel="nofollow">proved</a> that non-adaptive self-correctors for $NP$-complete languages would also collapse the Polynomial Hierarchy.<br>
But it is completely open whether <em>adaptive</em> self-correctors exist for $NP$-complete languages.  I believe the question of adaptive random self-reductions for SAT is also open.
Even if all of these could be ruled out (under the assumption $PH$ does not collapse, say), there might conceivably still be some other, less constructive proof of a worst-case to average-case hardness connection for $NP$.  Bogdanov-Trevisan give a good discussion of the issues here (see also their <a href="http://arxiv.org/abs/cs/0606037" rel="nofollow">survey</a> on average-case complexity).</p>

CC BY-SA 3.0
2013-11-29T18:52:30.707Z
Thankyou for the answer. After seeing your post, I did a brief search. The following popped up http://research.microsoft.com/en-us/um/redmond/groups/theory/jehkim/a-yspapers/unsat.pdf It seems to say for almost all 3CNF formulas of a certain size, we can have short certificates for non-satsifiability. So may be the $\mathsf{NP}=\mathsf{coNP}$ issue is not random self-reducible.
Turbo
CC BY-SA 3.0
2013-11-30T01:28:22.967Z
Yes, under particular input distributions, 3SAT may be easy on average.  However, I believe that for random 3-CNFs very near the satisfiability threshold, it is unknown whether the problem is easy on average or even if short refutations exist.  In any case, there is no evidence that such a simple model of random NP instances might be NP-hard (even assuming it is intractable).  For PSPACE-complete languages, which *are* r.s.r. (see Feigenbaum-Fortnow), the known PSPACE-hard input distributions are more complicated.
Andy Drucker
CC BY-SA 3.0
2013-11-29T15:50:33.853Z
2013-11-29T15:50:33.853Z
Andy Drucker
<p>Permanent is random self-reducible. $\mathsf{SAT}$ is not random self-reducible since otherwise the polynomial hierarchy collapses to $\mathsf{\Sigma_3}$.</p>

<p><strong>1) Is $k$-sum random self-reducible?</strong></p>

<p>That is if $k$-sum can be computed in time $n^{O(k^b)}$ for some $0&lt;b&lt;1$ on $\frac{1}{2}+\epsilon$ of inputs where $n$ is the number of input integers, then can $k$-sum be computed time $n^{O(k^b)}$ for all inputs of $n$ input integers in a randomized sense?</p>

<p>The Patrascu-Williams paper <a href="http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf" rel="nofollow">http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf</a> talks about deterministic algorithms and does not imply hierarchy collapse but only tells that the ETH fails (somewhat mildly) when we have a deterministic $n^{O(k^b)}$ algorithm. We have a randomized setting here and even if we have such a random self-reducible condition satisfied, we may still not upset the big picture.</p>

<p><strong>2)Likewise can the $\mathsf{NP=coNP}$ problem be random self reducible?</strong></p>

<p>That is, if for an $\mathsf{NP}$ complete problem we have short certificates for $\frac{1}{2}+\epsilon$ of the $\mathsf{NO}$ instances, then we have short certificates for all $\mathsf{NO}$ instances in a randomized sense?</p>

<p><strong>Update</strong> The results in <a href="http://research.microsoft.com/en-us/um/redmond/groups/theory/jehkim/a-yspapers/unsat.pdf" rel="nofollow">http://research.microsoft.com/en-us/um/redmond/groups/theory/jehkim/a-yspapers/unsat.pdf</a> seems to indicate the $\mathsf{NP}=\mathsf{coNP}$ issue is not random self-reducible. </p>

<cc.complexity-theory><randomized-algorithms><reductions><parameterized-complexity><fixed-parameter-tractable>
On Random Self-reducible properties
Turbo
# On Random Self-reducible properties

(Asked by: username_0 on 2013-11-28)

Permanent is random self-reducible. $\mathsf{SAT}$ is not random self-reducible since otherwise the polynomial hierarchy collapses to $\mathsf{\Sigma\_3}$.

**1) Is $k$-sum random self-reducible?**

That is if $k$-sum can be computed in time $n^{O(k^b)}$ for some $0

The Patrascu-Williams paper <http://people.csail.mit.edu/mip/papers/sat-lbs/paper.pdf> talks about deterministic algorithms and does not imply hierarchy collapse but only tells that the ETH fails (somewhat mildly) when we have a deterministic $n^{O(k^b)}$ algorithm. We have a randomized setting here and even if we have such a random self-reducible condition satisfied, we may still not upset the big picture.

**2)Likewise can the $\mathsf{NP=coNP}$ problem be random self reducible?**

That is, if for an $\mathsf{NP}$ complete problem we have short certificates for $\frac{1}{2}+\epsilon$ of the $\mathsf{NO}$ instances, then we have short certificates for all $\mathsf{NO}$ instances in a randomized sense?

**Update** The results in <http://research.microsoft.com/en-us/um/redmond/groups/theory/jehkim/a-yspapers/unsat.pdf> seems to indicate the $\mathsf{NP}=\mathsf{coNP}$ issue is not random self-reducible.

**Tags:** cc.complexity-theory, randomized-algorithms, reductions, parameterized-complexity, fixed-parameter-tractable


---

## 1 answers

### Answer by username_1 on 2013-11-29. Score: 3 | Accepted answer

I don't know the answer to Question (1)---I suspect there is no such reduction. But I have a couple of points to make.

A non-adaptive random self-reduction (to the uniform distribution) is a poly-time randomized algorithm $R$ which, given an arbitrary instance $x$ of length $n$ for the decision problem for $L$, produces a list $y^1, \ldots, y^{q(n)}$ of instances of some second length $\ell(n)$. We have the properties that

(i) each $y^i$ generated by $R$ is individually uniformly distributed, for any fixed input $x$ (although there may be complicated dependence between the $y^i$s, which in some way "encodes" $x$);

(ii) there is a second poly-time algorithm $R'$ which, given $y^1, \ldots, y^q$ along with their $L$-membership values $b^1, \ldots, b^q$ ($b\_i = [y\_i \in L]$), outputs the desired value $[x \in L]$.

Feigenbaum and Fortnow [prove](http://www.cs.uchicago.edu/~fortnow/papers/rsr.pdf) that if an $NP$-complete language has such a reduction then the Polynomial Hierarchy collapses. The argument applies to other target distributions, not just the uniform distribution.

Now my first point (regarding your Question (2)) is that their result directly gives evidence for the difficulty of showing a worst-case to average-case connection for proof systems certifying unsatisfiability of Boolean formulas. Because the most natural way you'd try to argue that random unsatisfiable formulas are hard to refute (assuming $NP \neq coNP$), is by exhibiting a random self-reduction as above. Now in the study of proof systems, it might be natural to allow the recovery algorithm $R'$ to be nondeterministic, for example; I believe the [FF] analysis techniques would still apply, but this would take verification after defining things carefully.

My second point is that non-adaptive random self-reductions as above are not the only way to establish average-case hardness of a language $L$ (assuming its worst-case hardness). There is also the more general notion of a *self-correction* reduction, which converts any mostly-correct algorithm for $L$ into a fully-correct algorithm, but which does not guarantee that its individual queries be distributed according to any particular distribution (they may depend heavily on the input $x$). Bogdanov and Trevisan [proved](http://theory.stanford.edu/~trevisan/pubs/redux-sicomp.pdf) that non-adaptive self-correctors for $NP$-complete languages would also collapse the Polynomial Hierarchy.  
But it is completely open whether *adaptive* self-correctors exist for $NP$-complete languages. I believe the question of adaptive random self-reductions for SAT is also open.
Even if all of these could be ruled out (under the assumption $PH$ does not collapse, say), there might conceivably still be some other, less constructive proof of a worst-case to average-case hardness connection for $NP$. Bogdanov-Trevisan give a good discussion of the issues here (see also their [survey](http://arxiv.org/abs/cs/0606037) on average-case complexity).

> **Comments:**
> **username_0**: Thankyou for the answer. After seeing your post, I did a brief search. The following popped up http://research.microsoft.com/en-us/um/redmond/groups/theory/jehkim/a-yspapers/unsat.pdf It seems to say for almost all 3CNF formulas of a certain size, we can have short certificates for non-satsifiability. So may be the $\mathsf{NP}=\mathsf{coNP}$ issue is not random self-reducible.  
> **username_1**: Yes, under particular input distributions, 3SAT may be easy on average.  However, I believe that for random 3-CNFs very near the satisfiability threshold, it is unknown whether the problem is easy on average or even if short refutations exist.  In any case, there is no evidence that such a simple model of random NP instances might be NP-hard (even assuming it is intractable).  For PSPACE-complete languages, which *are* r.s.r. (see Feigenbaum-Fortnow), the known PSPACE-hard input distributions are more complicated.  

---

