Set which is easy to sample, but difficult to sample from its complement

Question

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

Answer 1

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.