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

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

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.