5
$\begingroup$

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.

$\endgroup$
17
  • 2
    $\begingroup$ Why are 101 and 011 good? Shifting one gives 101, 101 so doesn't seem so. $\endgroup$
    – Ville Salo
    Jul 27, 2020 at 14:51
  • 1
    $\begingroup$ And it seems picking the $\tau_i$ makes the shifting meaningless, so I still don't understand what you are after. $\endgroup$
    – Ville Salo
    Jul 27, 2020 at 14:55
  • 1
    $\begingroup$ Ok so should it say 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$? $\endgroup$
    – Ville Salo
    Jul 27, 2020 at 15:08
  • 1
    $\begingroup$ If I understand correctly that good means no sequence in the set is a union of shifts of others, I'm guessing you can ensure only one of the sequences has small enough support that it's possible to cover with the others, and then there should be some easy reduction. It's pretty much clear that goodness is (co-)NP-complete. (Even if not as I suggest here.) $\endgroup$
    – Ville Salo
    Jul 27, 2020 at 15:21
  • 2
    $\begingroup$ I agree with @fedja that if you want to find such a code, then you could've just asked for such a code. If you need many such codes, or are not sure yet what kind of additional properties you want for the codes, then it's useful to know the problem is in co-NP because computers are good at solving problems in co-NP. Knowing it's co-NP-complete is useful because it means you're not missing an obvious polynomial-time algorithm, unless we all are. $\endgroup$
    – Ville Salo
    Jul 28, 2020 at 7:11

1 Answer 1

5
$\begingroup$

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.)

$\endgroup$
4
  • $\begingroup$ Thank you so much. Although I can see the intuition and logic of relating the problem to SAT, I fail to understand the intuition of proving $s_i$ as the only possible bad index, and the notion of $a_i$ (and the next paragraph). $\endgroup$
    – lchen
    Jul 28, 2020 at 14:59
  • $\begingroup$ If $s_1$ is the only one that could be covered, I just have to make sure, it's coverable iff the SAT instance is solvable. Otherwise I'd have to think about all $n$ sequnces. $\endgroup$
    – Ville Salo
    Jul 28, 2020 at 16:28
  • $\begingroup$ The sequences $a_i$ are a simple set of sequences such that one is not covered by a union of others. I doubt the quadratic length is optimal, but the proof is very simple algebra for them (I wrote it). $\endgroup$
    – Ville Salo
    Jul 28, 2020 at 16:30
  • $\begingroup$ Dunno what to clarify about the next paragraph (the one about $b_i$s I guess), except I'll fix a typo. $\endgroup$
    – Ville Salo
    Jul 28, 2020 at 16:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.