Skip to main content
MathOverflow

Return to Answer

edited body
Source Link
Ville Salo
Ville Salo
  • 6.7k
  • 1
  • 17
  • 40

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_i$$s_1$ contains one copy of $b_i$ while $s_1$$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, 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_i$ contains one copy of $b_i$ while $s_1$ 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, 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).

Source Link
Ville Salo
Ville Salo
  • 6.7k
  • 1
  • 17
  • 40

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_i$ contains one copy of $b_i$ while $s_1$ 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.)