  Feedback shift registers(FSRs) are a fundamental component in electronics and
secure communication. An FSR $f$ is said to be reducible if all the output
sequences of another FSR $g$ can also be generated by $f$ and the FSR $g$ has
less memory than $f$. An FSR is said to be decomposable if it has the same set
of output sequences as a cascade connection of two FSRs. It is proved that
deciding whether FSRs are irreducible/indecomposable is NP-hard.
