Return to Question

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=101$ and $s_2=110$ is a good system, while $s_1=001$ and $s_2=100$ 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.

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.

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=101$ and $s_2=110$ is a good system, while $s_1=001$ and $s_2=100$ 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. Note that if two or more users transmit at the same slot, none of them succeeds.

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=101$ and $s_2=110$ is a good system, while $s_1=001$ and $s_2=100$ 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.