Given $n$ binary sequences $s\_i$ ($1\le i\le n$) with common period $T$. Let $s\_i^{t\_i}$ denote the sequence obtained by cyclically shifting $s\_i$ for $t\_i$ bits. The $n$ sequences form a **good** system if under any combination of $\{t\_i\}\_{i=1}^n$, for each sequence $s\_i$ there always exists $\tau\_i$ such that $s\_i^{t\_i}(\tau\_i)=1$ and $s\_j^{t\_j}(\tau\_j)=0$ for $j\ne i$. For example, $s\_1=1010$ and $s\_2=1100$ is a good system, while $s\_1=0001$ and $s\_2=1000$ is not a good system.


Is the problem of deciding whether a system is good NP-hard?


The background of the problem is below. We want to design a code for each of the $n$ users. User $i$ with code $s\_i$ transmits its packet in slot $t$ if $s\_i(t)=1$. We want to check whether a set of codes can ensure that even the users are not time-synchronized, each of them can successfully transmit a packet under any clock drift among users. If two or more users transmit at the same slot, none of them succeeds.



NP-hardness of a sequence problem
I assume you mean "there always exist $\tau\_i$ such that $s\_i^{t\_i}(\tau\_i) = 1$ and $s\_j^{t\_j}(\tau\_i) = 0$ for $i \neq j$", i.e. you want that no matter how the sequences are shifted, each sequence has at least one bit which is zero in the other shifted sequences, and that's the slot when it manages to send its packet in your application.


(What you have written currently is "there always exist $\tau\_i$ such that $s\_i^{t\_i}(\tau\_i) = 1$ and $s\_j^{t\_j}(\tau\_j) = 0$ for $i \neq j$". If they are chosen separately for each $i$ this just means each of the $s\_i$ contain both $1$ and $0$. If they are chosen once and for all, this is impossible unless $n = 1$.)


Your problem as I interpret it is clearly in co-NP, as you check that all ($\forall$) shifts satisfy a (polynomial-time checkable) constraint, so it is probably not NP-hard, as that would collapse the polynomial hierarchy. I'll complement your problem and sketch a proof of NP-hardness of the resulting problem, meaning your problem is co-NP-complete.


Notation: On the set $X = \{0,1\}^{\mathbb{Z}\_T}$ we have the shift action of $\mathbb{Z}\_T = \mathbb{Z}/T\mathbb{Z}$ by $\sigma(s)\_i = s\_{i+1}, \sigma : X \to X$. For $s, s' \in X$ define $(s \cup s')\_i = \max(s\_i, s'\_i)$. Write $s \leq s'$ for $\forall i: s\_i \leq s'\_i$.


The complemented problem: Consider a set of sequences $S = (s\_i)\_i$, $s\_i \in X$. We say $i$ is a *bad index* for $S$ if $s\_i \leq \bigcup\_{j \neq i} \sigma^{t\_j}(s\_j)$ for some $t\_j \in \mathbb{Z}\_T$. We say $S$ is *bad* if there exists a bad index. Clearly $S$ is bad if and only if it is not good. The problem we prove NP-complete is identifying bad sets of sequences.


First, we will make sure $i = 1$ is the only possible bad index, i.e. $s\_1$ is the only sequence that could possibly be the union of the others. For this, we will put an arithmetic progression $a\_i$ in $s\_i$, $i > 1$. This progression should be longer than $n$ and such that any other $s\_j$ covers at most one element of it. I'll write some formulas for completeness.


Pick some $M$ (a parameter for future purposes). If $a\_i$ is the sequence with support $\{kM(n^2+i) \;|\; k = 0,1,...,n+1\}$, then any shift of $a\_i$ covers at most one position of any other $a\_{i'}$: if $kM(n^2+i) = k'M(n^2+i')$, $k, k' \in \{1, ..., n+1\}$, $i, i' \in \{2, ..., n\}$ and $i' > i$, then $k/k' = (n^2+i')/(n^2+i) \in (1, \frac{n^2+n}{n^2+2}] \subset (1, \frac{n+1}{n})$, but clearly $k/k' > 1 \implies k/k' \geq (n+1)/n$. Now just include $a\_i \leq s\_i$ for each $i \geq 2$, and make sure that all other remaining things we include in the sequences $s\_i$ fit within a single interval of length $Mn^2$ which is sufficiently far from $0$ (pick e.g. $T = 100 M n^3$ and there's plenty of space left, since the total length of $a\_i$ is less than $2Mn^3$).


Now, consider a SAT instance with $n-1$ variables and clauses, $x\_i, \phi\_i, i \in \{2,...,n\}$. To reduce SAT, we want $\exists$ to have to make a binary choice for each $i > 1$, which will represent a choice between $x\_i$ and $\neg x\_i$. Pick arithmetic progressions $b\_i$ similarly as we did with $a\_i$ (but on a smaller scale; pick a suitable $M$ so we can do all that follows in an interval of length $Mn^2$ as we promised ourselves in the previous paragraph). The sequence $s\_1$ contains one copy of $b\_i$ while $s\_i$ contains two copies of $b\_i$ at distance $h$ from each other. If $\exists$ is to win, the copy of $b\_i$ in $s\_1$ has to be covered by one of the copies in $s\_i$ (note that as long as $b\_i$ fits in an interval of length $Mn^2$, the existing $a\_j$-bits in the $s\_j$ are not helpful for covering it).


Now, we can add for each clause of the SAT instance a single bit in $s\_1$. These bits are in arithmetic progression with distance $2h$ between them. Depending on whether $x\_j$ or $\neg x\_j$ appears in the clause (or neither), we put a $1$ in the position in $s\_j$ such that the correct clause bit is covered. (The bits coming from the choice $x\_i = \top$ do not touch any clause bits if we choose the $x\_i = \bot$ alignment for $s\_i$, since this gives only a displacement of $h$; and vice versa for the $x\_i = \top$ alignment.)


