<p>No. For example, if your input is a CNF with few solutions, then you can randomly generate non-satisfying assignment: just generate an assignment and keep it if it's non-satisfying. But generating a satisfying assignment is NP-hard.</p>

CC BY-SA 4.0
2019-12-06T07:56:57.203Z
I realize it's my fault for not having a clear definition of "transducer BPP", but intuitively if there are only a few satisfying assignments, the complement is (exponentially) well approximated by the empty set. Perhaps specifying that $g$'s output can only have polynomially many collisions or that Im(g) is at most a polynomially small fraction of $F_2^n$ would clarify the issue, i.e. $\frac{|Im(g)|}{2^n} > \frac{1}{poly(n)}$. As a specific problem, we could specify that $g$ has at most two collisions per output and that $\frac{|Im(g)|}{2^n} = \frac{1}{2}$.
botsina
CC BY-SA 4.0
2019-12-06T08:23:35.330Z
The fraction should be $\frac{3}{4}$ not $\frac{1}{2}$.
botsina
CC BY-SA 4.0
2019-12-06T08:25:07.270Z
@botsina You can edit your previous comment to fix this, and also your question to make it more clear.
domotorp
CC BY-SA 4.0
2019-12-07T09:39:54.257Z
I like this answer, but you can consider pointing out that this is a promise problem. The promise is that the input CNF satisfies a hard-to-check property, namely being sparse. That said, this answer does prove that Promise-Transducer-BPP is not closed under complement unless $NP\subseteq BPP$.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2019-12-05T19:50:19.847Z
2019-12-05T19:50:19.847Z
domotorp
<p>I believe that the answer to your question is still no when <span class="math-container">$|Im(g)|$</span> is a constant fraction of <span class="math-container">$F_2^n$</span>.
Consider quadratic residues mod <span class="math-container">$N$</span>. It is easy to generate them: Pick a random number <span class="math-container">$x$</span> mod <span class="math-container">$N$</span>, and if <span class="math-container">$(x,N)=1$</span>, then <span class="math-container">$x^2$</span> mod <span class="math-container">$N$</span> is a quadratic residue. But how can we generate quadratic non-residues? For this, we would need to find a quadratic non-residue for which we probably need to know the prime factorization of <span class="math-container">$N$</span>. (Note that it is not known how to efficiently decide whether a random <a href="https://en.wikipedia.org/wiki/Quadratic_residuosity_problem" rel="nofollow noreferrer">number is a quadratic residue or not</a>.)</p>

CC BY-SA 4.0
2019-12-06T08:35:38.413Z
2019-12-06T08:35:38.413Z
domotorp
<p><strong>No.</strong> Generating such strings is <span class="math-container">$NP$</span>-Hard.</p>

<p>Morally, this question is akin to, "is there an input <span class="math-container">$x$</span> to this machine which will make it output <span class="math-container">$y$</span>?", and such questions are almost always <span class="math-container">$\text{(co)-NP}$</span>-Complete. Our construction follows this line of thought, asking whether a machine which guesses an assignment to a CNF formula ever outputs ``Satisfiable''. The details follow.</p>

<p>If you could generate strings from the complement of the range of a polynomial-time machine, then you can solve <span class="math-container">$\text{SAT}$</span> as follows. </p>

<p>Let <span class="math-container">$T$</span> be a probabilistic polynomial-time machine which, on input CNF formula <span class="math-container">$\phi$</span>, generates a random assignment <span class="math-container">$x$</span> for <span class="math-container">$\phi$</span>, and then outputs the bit <span class="math-container">$\phi(x)$</span> (i.e., whether the assignment it guessed satisfies <span class="math-container">$\phi$</span>). Hence the range of <span class="math-container">$T$</span> is <span class="math-container">$\{0,1\}$</span>. More precisely, the range of <span class="math-container">$T$</span> is <span class="math-container">$\{0,1\}$</span> on inputs <span class="math-container">$\phi$</span> that are satisfiable, and it is just <span class="math-container">$\{0\}$</span> on unsatisfiable inputs.</p>

<p>The range of this machine is just <span class="math-container">$\{0,1\}$</span>, whereas you asked about <span class="math-container">$\{0,1\}^n$</span>, so we modify the construction a bit (also the complement is sometimes <em>empty</em>, which we should also repair). (I'm assuming that by <span class="math-container">$n$</span> you mean the lenght of the input)</p>

<p>The modification will be that we will simply pad the output with random bits, as follows.</p>

<p>This time, let <span class="math-container">$T^\prime$</span> be like <span class="math-container">$T$</span>, except that on an input of length <span class="math-container">$n$</span>, it generates <span class="math-container">$n-1$</span> more bits, say <span class="math-container">$r\in \{0,1\}^{n-1}$</span>, and then outputs the concatentation <span class="math-container">$T(x).r$</span>. One exception: for technical reasons, if <span class="math-container">$r=1^{n-1}$</span>, then <span class="math-container">$T^\prime$</span> will output <span class="math-container">$T(x)0^{n-1}$</span> instead of <span class="math-container">$T(x)1^{n-1}$</span>. This is to avoid the range of <span class="math-container">$T^\prime$</span> being all of <span class="math-container">$\{0,1\}^n$</span>, in which case its complement would be empty.</p>

<p>Now the range of <span class="math-container">$T^\prime$</span> is <span class="math-container">$\{0,1\}^n\setminus \{01^{n-1},11^{n-1}\}$</span> when <span class="math-container">$\phi$</span> is satisfiable, and is <span class="math-container">$0\{0,1\}^{n-1}\setminus\{01^{n-1}\}$</span> when <span class="math-container">$\phi$</span> is unsatisfiable. 
So the complement of the range is <span class="math-container">$\{0,1\}1^{n-1}$</span> when <span class="math-container">$\phi$</span> is satisfiable, and is <span class="math-container">$\{0,1\}1^{n-1}\cup 1\{0,1\}^{n-1}$</span> when <span class="math-container">$\phi$</span> is unsatisfiable.</p>

<p>Hence if we could sample strings from the complement of <span class="math-container">$T^\prime$</span>'s output, then we could decide whether <span class="math-container">$\phi$</span> is satisfiable. Namely, if, except <span class="math-container">$1^n$</span>, any string in the complement starts with a <span class="math-container">$1$</span>, then <span class="math-container">$\phi$</span> is unsatisfiable; otherwise <span class="math-container">$\phi$</span> is satisfiable.</p>

<p>So to be more precise, Transducer <span class="math-container">$\text{BPP}$</span> is closed under complement if and only if <span class="math-container">$\text{P}=\text{NP}$</span>. I like this question; it is a cute problem, keep them coming. :)</p>

CC BY-SA 4.0
2019-12-07T10:28:47.640Z
2019-12-07T10:28:47.640Z
Lieuwe Vinkhuijzen
<p>Obviously, recognizing BPP languages is closed under complement. For primes and composite integers both recognizing primes/composites and generating primes/composites can be done in "BPP". Is this true generally for BPP languages, i.e. can generating random words in a BPP language (and it's complement) be done in probabilistic polynomial time?</p>

<p>Specifically, given a probabilistic polynomial time algorithm which outputs strings in <span class="math-container">$F_2^n$</span> by computing the functions <span class="math-container">$g_i(x_k)$</span>, where <span class="math-container">$i = 1 .. n$</span> and <span class="math-container">$x_k$</span> are random bits, is it possible to output (uniformly or otherwise) strings from the complement of the image of <span class="math-container">$g_i$</span>, <span class="math-container">$F_2^n \setminus Im(g)$</span> in probabilistic polynomial time?</p>

<p>If so, is there a known practical algorithm to find the complement and what is its computational complexity and is that complexity bound optimal? If only an approximate complement can be computed efficiently, what are the upper bounds on approximation? Could there be a PCP theorem?</p>

<probabilistic-circuits><probabilistic-complexity>
Is the transducer version of BPP closed under complement?
botsina
# Is the transducer version of BPP closed under complement?

(Asked by: username_0 on 2019-12-05)

Obviously, recognizing BPP languages is closed under complement. For primes and composite integers both recognizing primes/composites and generating primes/composites can be done in "BPP". Is this true generally for BPP languages, i.e. can generating random words in a BPP language (and it's complement) be done in probabilistic polynomial time?

Specifically, given a probabilistic polynomial time algorithm which outputs strings in $F\_2^n$ by computing the functions $g\_i(x\_k)$, where $i = 1 .. n$ and $x\_k$ are random bits, is it possible to output (uniformly or otherwise) strings from the complement of the image of $g\_i$, $F\_2^n \setminus Im(g)$ in probabilistic polynomial time?

If so, is there a known practical algorithm to find the complement and what is its computational complexity and is that complexity bound optimal? If only an approximate complement can be computed efficiently, what are the upper bounds on approximation? Could there be a PCP theorem?

**Tags:** probabilistic-circuits, probabilistic-complexity

---

## 3 answers

### Answer by username_1 on 2019-12-05. Score: 3

No. For example, if your input is a CNF with few solutions, then you can randomly generate non-satisfying assignment: just generate an assignment and keep it if it's non-satisfying. But generating a satisfying assignment is NP-hard.

> **Comments:**
> **username_0**: I realize it's my fault for not having a clear definition of "transducer BPP", but intuitively if there are only a few satisfying assignments, the complement is (exponentially) well approximated by the empty set. Perhaps specifying that $g$'s output can only have polynomially many collisions or that Im(g) is at most a polynomially small fraction of $F_2^n$ would clarify the issue, i.e. $\frac{|Im(g)|}{2^n} > \frac{1}{poly(n)}$. As a specific problem, we could specify that $g$ has at most two collisions per output and that $\frac{|Im(g)|}{2^n} = \frac{1}{2}$.  
> **username_0**: The fraction should be $\frac{3}{4}$ not $\frac{1}{2}$.  
> **username_1**: @botsina You can edit your previous comment to fix this, and also your question to make it more clear.  
> **username_2**: I like this answer, but you can consider pointing out that this is a promise problem. The promise is that the input CNF satisfies a hard-to-check property, namely being sparse. That said, this answer does prove that Promise-Transducer-BPP is not closed under complement unless $NP\subseteq BPP$.  

---

### Answer by username_1 on 2019-12-06. Score: 3

I believe that the answer to your question is still no when $|Im(g)|$ is a constant fraction of $F\_2^n$.
Consider quadratic residues mod $N$. It is easy to generate them: Pick a random number $x$ mod $N$, and if $(x,N)=1$, then $x^2$ mod $N$ is a quadratic residue. But how can we generate quadratic non-residues? For this, we would need to find a quadratic non-residue for which we probably need to know the prime factorization of $N$. (Note that it is not known how to efficiently decide whether a random [number is a quadratic residue or not](https://en.wikipedia.org/wiki/Quadratic_residuosity_problem).)


---

### Answer by username_2 on 2019-12-07. Score: 2

**No.** Generating such strings is $NP$-Hard.

Morally, this question is akin to, "is there an input $x$ to this machine which will make it output $y$?", and such questions are almost always $\text{(co)-NP}$-Complete. Our construction follows this line of thought, asking whether a machine which guesses an assignment to a CNF formula ever outputs ``Satisfiable''. The details follow.

If you could generate strings from the complement of the range of a polynomial-time machine, then you can solve $\text{SAT}$ as follows.

Let $T$ be a probabilistic polynomial-time machine which, on input CNF formula $\phi$, generates a random assignment $x$ for $\phi$, and then outputs the bit $\phi(x)$ (i.e., whether the assignment it guessed satisfies $\phi$). Hence the range of $T$ is $\{0,1\}$. More precisely, the range of $T$ is $\{0,1\}$ on inputs $\phi$ that are satisfiable, and it is just $\{0\}$ on unsatisfiable inputs.

The range of this machine is just $\{0,1\}$, whereas you asked about $\{0,1\}^n$, so we modify the construction a bit (also the complement is sometimes *empty*, which we should also repair). (I'm assuming that by $n$ you mean the lenght of the input)

The modification will be that we will simply pad the output with random bits, as follows.

This time, let $T^\prime$ be like $T$, except that on an input of length $n$, it generates $n-1$ more bits, say $r\in \{0,1\}^{n-1}$, and then outputs the concatentation $T(x).r$. One exception: for technical reasons, if $r=1^{n-1}$, then $T^\prime$ will output $T(x)0^{n-1}$ instead of $T(x)1^{n-1}$. This is to avoid the range of $T^\prime$ being all of $\{0,1\}^n$, in which case its complement would be empty.

Now the range of $T^\prime$ is $\{0,1\}^n\setminus \{01^{n-1},11^{n-1}\}$ when $\phi$ is satisfiable, and is $0\{0,1\}^{n-1}\setminus\{01^{n-1}\}$ when $\phi$ is unsatisfiable.
So the complement of the range is $\{0,1\}1^{n-1}$ when $\phi$ is satisfiable, and is $\{0,1\}1^{n-1}\cup 1\{0,1\}^{n-1}$ when $\phi$ is unsatisfiable.

Hence if we could sample strings from the complement of $T^\prime$'s output, then we could decide whether $\phi$ is satisfiable. Namely, if, except $1^n$, any string in the complement starts with a $1$, then $\phi$ is unsatisfiable; otherwise $\phi$ is satisfiable.

So to be more precise, Transducer $\text{BPP}$ is closed under complement if and only if $\text{P}=\text{NP}$. I like this question; it is a cute problem, keep them coming. :)


---

