2
$\begingroup$

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?

$\endgroup$

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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}$. $\endgroup$
    – botsina
    Dec 6, 2019 at 7:56
  • $\begingroup$ The fraction should be $\frac{3}{4}$ not $\frac{1}{2}$. $\endgroup$
    – botsina
    Dec 6, 2019 at 8:23
  • $\begingroup$ @botsina You can edit your previous comment to fix this, and also your question to make it more clear. $\endgroup$
    – domotorp
    Dec 6, 2019 at 8:25
  • $\begingroup$ 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$. $\endgroup$ Dec 7, 2019 at 9:39
3
$\begingroup$

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.)

$\endgroup$
2
$\begingroup$

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. :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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