Generating bit sequence containing every possible of length 1...n
Such a sequence (for arbitrary $k$-ary encodings) is known as a De Bruijn sequence. For the case of the binary encodings, the De Bruijn sequence has length $2^n$. As the output is exponential, this problem is clearly not in $P$, but it lies in $EXP$, as it can be constructed via a Hamiltonian path along the De Bruijn graph (see also here)