<p>for Question 1, the answer is Yes, and can be shown as follows.  (I will also be implicitly sketching an affirmative answer to Q4, since the argument is uniform and will treat all input lengths at once.)  </p>

<p>Fix any NP-complete language $L$, and a family of good binary error-correcting codes (with rate 1/4 and correcting from a .1 fraction of errors, say).  Let $Enc_n: \{0, 1\}^n \rightarrow \{0, 1\}^{4n}$ be the encoding function for length $n$; we use some such code where $Enc = \{Enc_n\}$ is computable by a uniform polynomial-time algorithm.</p>

<p>Define $L'$ as the set of strings $z$ that are within distance at most $.05 |z|$ from a codeword $y \in Enc(L)$ encoding some element of $L$.  Note that $L'$ is in NP, as you can guess and check the nearby codeword, the decoded word, and the NP certificate for the decoded word's membership in $L$.  </p>

<p>Then the claim is that any "approximation" of $L'$ in your sense is NP-hard for $\varepsilon = .01$.  For if we consider a valid codeword $y = Enc(x)$ of some length $4n$, then with probability $1 - o(1)$ over a random $\varepsilon$-perturbed version $y'$ of $y$, it will disagree with $y$ in at most a .05 fraction of coordinates, and will therefore disagree with any other codeword of $Enc_n$ in a more than $.05$ fraction of coords.  For such $y'$ we have $y' \in L'$ iff $x \in L$.  So if $h$ is any approximation to the $\varepsilon$-smoothed version of $L'$ in your sense, then we must have $h(y) = L(x)$.  As $Enc$ is efficiently computable, this gives us a way to efficiently reduce membership questions for $L$ to ones for $h$.  So $h$ is NP-hard.</p>

<p>Two notes:  </p>

<p>(1) error-correcting encodings of NP instances have been used before in several papers, notably<br>
D. Sivakumar: <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.648">On Membership Comparable Sets.</a> J. Comput. Syst. Sci. 59(2): 270-280 (1999).</p>

<p>(2) the argument above of course says nothing about the average-case complexity of any NP problem, since error-correction is being applied on an instance-by-instance basis.  </p>

CC BY-SA 3.0
2013-09-04T15:47:06.047Z
The software will not let me begin my answer with "Hi Gil," and I am a bit creeped out by this level of micromanagement.
Andy Drucker
CC BY-SA 3.0
2013-09-04T15:58:52.827Z
This is because your answer should *not* begin with "Hi Gil". It's not a personal e-mail, it's a post on a public website. Of course, the likes of you are not the ones targeted by this; it is rather new users who are not aware of these conventions which the software aims to control.
Yuval Filmus
CC BY-SA 3.0
2013-09-04T18:56:48.177Z
My view is that it's fine to acknowledge when one is writing in response to someone else's contribution.  This is normal and positive in many online settings.  I tried to do so in the briefest possible way, by personal address; don't see anything wrong with that.
Andy Drucker
CC BY-SA 3.0
2013-09-04T20:57:45.253Z
Under your suggestion, all answers would start with "Hi Gil", and this will look somewhat silly. In any case, this is a matter of convention, and the convention on stackexchange is that such addresses not appear.
Yuval Filmus
CC BY-SA 3.0
2013-09-04T21:58:53.467Z
Nice construction! I have a question: let f be the indicator function of L', and h be as in Gil's question. Now, your argument shows that h agrees with f on y's that are legal codewords. But how about y's that are not legal codewords?
Or Meir
CC BY-SA 3.0
2013-09-05T04:46:42.657Z
No, under my suggestion answers would occasionally begin with "Hi Gil," as authors see fit.  Such minor and personal choices would be left to users' discretion.
Andy Drucker
CC BY-SA 3.0
2013-09-05T04:50:26.220Z
Oh hai, Or. The function h would have to equal 0 on y's that are far enough away from legal codewords.  And its behavior would be dictated by that of L on y's that are very close to legal codewords.  There would be an intermediate range on which h's behavior is not determined by Gil's requirement.
Andy Drucker
CC BY-SA 3.0
2013-10-12T19:35:54.137Z
Can you implement such a thing with monotone $f$?
Gil Kalai
CC BY-SA 3.0
2013-10-19T03:10:10.710Z
Good question!  I think the answer is Yes.  In my example, $L'$ (which at input length $n$ plays the role of $f$) can be modified in its definition to: the set of all strings that are within Hamming dist. at most .05|z| from a string *dominating* an encoding of some x in L.  We also require that the encoding that we use has all nonzero codewords be pairwise-incomparable (it's easy to ensure this).  The resulting L' is monotone and I believe it has the desired property.
Andy Drucker
CC BY-SA 3.0
2013-09-04T15:33:04.067Z
2013-09-05T06:21:21.657Z
2013-09-05T06:21:21.657Z
Andy Drucker
<p>Let $f$ be a Boolean function  of $n$ Boolean variables. Let $g(x)=T_\epsilon (f) (x)$ be the expected value of $f(y)$ when $y$ is obtained from $x$ by flipping each coordinate with probability $\epsilon/2$.</p>

<p>I am interested in cases where it is computationally hard to approximate $g$. Let me fixed a notion of "approximation" (but there may be others): A Boolean function $h$ approximates $g$ if $h(x)=1$ when $g(x)\ge 0.9$ and $h(x)=0 $ when $g(x)\le 0.1$.A counting argument (based on the existence of positive rate error correcting codes) seem to give that there are Boolean functions for which any such approximation requires an exponential size circuit. But the question is what happens when $f$ to start with is in NP or in its neighborhood. </p>

<p>Q1: Is there an example of $f$ described by NP circuit (or P-space) so that every $h$ is NP hard, or hard in some weaker sense.</p>

<p>To see that $h$ might not always be easy (I thank Johan Hastad for useful discussion about it) we can consider the property of graphs of having a clique of size $n^{1/4}$, for random input, it is conceivable that it is hard to detect if there is a large clique but this is manifested by having more than expected cliques of size log n in the noisy graph. In this case any $h$ will be likely-hard (but not provably, and not terribly hard as quasi-polynomial circuits will be telling).</p>

<p>Q2: What is the situation if $f$ to start with is low complexity. ($AC^0$, monotone $TC^0$, $ACC$ etc.)</p>

<p>Q3: What is the situation for some basic examples of Boolean functions. (The question can be extended also to real-valued function.)</p>

<p>Q4: Can the above question be asked formally for the uniform (Turing-machine) model of computation?</p>

<p><strong>Update:</strong> In view of Andy's answer (Hi there, Andy) I think that the most interesting question is to understand the situation for various specific functions.</p>

<p><strong>Update</strong> Another question Q5 [Q1 for monotone functions] (also in view of Andy's answer). What is the situation if $f$ is monotone? Can we still encode robustly an NP complete questions></p>

CC BY-SA 3.0
2013-09-02T16:02:41.897Z
imho this [question on circuit approximation](http://cstheory.stackexchange.com/questions/17239/k-cnf-k-dnf-conversion-to-minimize-errors) is related. your question seems to be similar to the P/poly vs NP question.
vzn
<cc.complexity-theory><circuit-complexity><boolean-functions>
Hardness of noisy Boolean functions
Gil Kalai
# Hardness of noisy Boolean functions

(Asked by: username_0 on 2013-09-01)

Let $f$ be a Boolean function of $n$ Boolean variables. Let $g(x)=T\_\epsilon (f) (x)$ be the expected value of $f(y)$ when $y$ is obtained from $x$ by flipping each coordinate with probability $\epsilon/2$.

I am interested in cases where it is computationally hard to approximate $g$. Let me fixed a notion of "approximation" (but there may be others): A Boolean function $h$ approximates $g$ if $h(x)=1$ when $g(x)\ge 0.9$ and $h(x)=0 $ when $g(x)\le 0.1$.A counting argument (based on the existence of positive rate error correcting codes) seem to give that there are Boolean functions for which any such approximation requires an exponential size circuit. But the question is what happens when $f$ to start with is in NP or in its neighborhood.

Q1: Is there an example of $f$ described by NP circuit (or P-space) so that every $h$ is NP hard, or hard in some weaker sense.

To see that $h$ might not always be easy (I thank Johan Hastad for useful discussion about it) we can consider the property of graphs of having a clique of size $n^{1/4}$, for random input, it is conceivable that it is hard to detect if there is a large clique but this is manifested by having more than expected cliques of size log n in the noisy graph. In this case any $h$ will be likely-hard (but not provably, and not terribly hard as quasi-polynomial circuits will be telling).

Q2: What is the situation if $f$ to start with is low complexity. ($AC^0$, monotone $TC^0$, $ACC$ etc.)

Q3: What is the situation for some basic examples of Boolean functions. (The question can be extended also to real-valued function.)

Q4: Can the above question be asked formally for the uniform (Turing-machine) model of computation?

**Update:** In view of Andy's answer (Hi there, Andy) I think that the most interesting question is to understand the situation for various specific functions.

**Update** Another question Q5 [Q1 for monotone functions] (also in view of Andy's answer). What is the situation if $f$ is monotone? Can we still encode robustly an NP complete questions>

**Tags:** cc.complexity-theory, circuit-complexity, boolean-functions
> **Comments:**
> **username_1**: imho this [question on circuit approximation](http://cstheory.stackexchange.com/questions/17239/k-cnf-k-dnf-conversion-to-minimize-errors) is related. your question seems to be similar to the P/poly vs NP question.  

---

## 1 answers

### Answer by username_2 on 2013-09-04. Score: 14

for Question 1, the answer is Yes, and can be shown as follows. (I will also be implicitly sketching an affirmative answer to Q4, since the argument is uniform and will treat all input lengths at once.)

Fix any NP-complete language $L$, and a family of good binary error-correcting codes (with rate 1/4 and correcting from a .1 fraction of errors, say). Let $Enc\_n: \{0, 1\}^n \rightarrow \{0, 1\}^{4n}$ be the encoding function for length $n$; we use some such code where $Enc = \{Enc\_n\}$ is computable by a uniform polynomial-time algorithm.

Define $L'$ as the set of strings $z$ that are within distance at most $.05 |z|$ from a codeword $y \in Enc(L)$ encoding some element of $L$. Note that $L'$ is in NP, as you can guess and check the nearby codeword, the decoded word, and the NP certificate for the decoded word's membership in $L$.

Then the claim is that any "approximation" of $L'$ in your sense is NP-hard for $\varepsilon = .01$. For if we consider a valid codeword $y = Enc(x)$ of some length $4n$, then with probability $1 - o(1)$ over a random $\varepsilon$-perturbed version $y'$ of $y$, it will disagree with $y$ in at most a .05 fraction of coordinates, and will therefore disagree with any other codeword of $Enc\_n$ in a more than $.05$ fraction of coords. For such $y'$ we have $y' \in L'$ iff $x \in L$. So if $h$ is any approximation to the $\varepsilon$-smoothed version of $L'$ in your sense, then we must have $h(y) = L(x)$. As $Enc$ is efficiently computable, this gives us a way to efficiently reduce membership questions for $L$ to ones for $h$. So $h$ is NP-hard.

Two notes:

(1) error-correcting encodings of NP instances have been used before in several papers, notably  
D. Sivakumar: [On Membership Comparable Sets.](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.16.648) J. Comput. Syst. Sci. 59(2): 270-280 (1999).

(2) the argument above of course says nothing about the average-case complexity of any NP problem, since error-correction is being applied on an instance-by-instance basis.

> **Comments:**
> **username_2**: The software will not let me begin my answer with "Hi Gil," and I am a bit creeped out by this level of micromanagement.  
> **username_3**: This is because your answer should *not* begin with "Hi Gil". It's not a personal e-mail, it's a post on a public website. Of course, the likes of you are not the ones targeted by this; it is rather new users who are not aware of these conventions which the software aims to control.  
> **username_2**: My view is that it's fine to acknowledge when one is writing in response to someone else's contribution.  This is normal and positive in many online settings.  I tried to do so in the briefest possible way, by personal address; don't see anything wrong with that.  
> **username_3**: Under your suggestion, all answers would start with "Hi Gil", and this will look somewhat silly. In any case, this is a matter of convention, and the convention on stackexchange is that such addresses not appear.  
> **username_4**: Nice construction! I have a question: let f be the indicator function of L', and h be as in Gil's question. Now, your argument shows that h agrees with f on y's that are legal codewords. But how about y's that are not legal codewords?  
> **username_2**: No, under my suggestion answers would occasionally begin with "Hi Gil," as authors see fit.  Such minor and personal choices would be left to users' discretion.  
> **username_2**: Oh hai, Or. The function h would have to equal 0 on y's that are far enough away from legal codewords.  And its behavior would be dictated by that of L on y's that are very close to legal codewords.  There would be an intermediate range on which h's behavior is not determined by Gil's requirement.  
> **username_0**: Can you implement such a thing with monotone $f$?  
> **username_2**: Good question!  I think the answer is Yes.  In my example, $L'$ (which at input length $n$ plays the role of $f$) can be modified in its definition to: the set of all strings that are within Hamming dist. at most .05|z| from a string *dominating* an encoding of some x in L.  We also require that the encoding that we use has all nonzero codewords be pairwise-incomparable (it's easy to ensure this).  The resulting L' is monotone and I believe it has the desired property.  

---

