1
$\begingroup$

Generating sequence containing every possible bit sequence of lengths from $1$ to $n$ is trivial - just generate every possible sequence of length $n$.

But how do you generate the shortest sequence containing every possible bit subsequence of lengths from $1$ to $n$ (using the fact that subsequences may partially overlap)?

What complexity class does that problem belong to?

$\endgroup$

1 Answer 1

3
$\begingroup$

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)

$\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.