2
$\begingroup$

Given a set $S \subseteq \{0,1\}^*$, the algorithm $A$ is a generator for $S$ if given $n$ random bits $x \in \{0,1\}^n$, $A$ generates an element of $S$ of size $n$, and $A$ can generate at least $\frac{2}{3}$ members of $S$ of size $n$ (for all $n$). $A$ does not have to be uniform.

Is there a set $S$ such that there exists an efficient algorithm $A$ such that for all $n$, $A$ generates at least $\frac{2}{3}$ members of $S$ (of size $n$), but any efficient algorithm for $S^C$ can only generate at most $\frac{1}{3}$ elements from $S^C$ of size $n$ (under complexity asuumptions)?

$\endgroup$
2
$\begingroup$

We can construct $S$ such that polynomial-time generators for $A$ exist, while no generator exists for $S^{c}$. Pick $S$ such that all strings starting with $1$ are in it, and exactly half of all strings starting with $0$ are in it.

A sampler that sets the first bit of $x$ to $1$ and outputs it always generates an element in $S$, and generates exactly $\frac{2}{3}$ of the elements in $S$.

However, sampling from the complement of $S$ in the general case is even harder than you require: there exist sets $S$ such that there exists no Turing machine that given $n, x = 0^{n}$ as input outputs any string in $S$ of length $n$ starting with $1$. Furthermore, we can explicitly construct such a set $S$.

This is easy to prove by a diagonalisation argument. Let $K_{w, n}$ be the set of strings of length $n$ starting with $w$. There is a countable number of Turing machines, so let $M_{i}$ be the $i$th Turing machine. For $n \geq 2$, if $M_{n-1}$ on input $n, x = 0^{n}$ doesn't halt or outputs a string in $K_{00, n}$, set $S_{n} = K_{1, n} \cup K_{00, n}$. Otherwise set $S_{n} = K_{1, n} \cup K_{01, n}$. Then $S = \{\epsilon, 1\} \cup \bigcup_{i = 2}^{\infty} S_{i}$ is one such set.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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