Supongo que quiere decir que "siempre existen $\tau_i$ tal que $s_i^{t_i}(\tau_i) = 1$ y $s_j^{t_j}(\tau_i) = 0$ para $i \neq j$ ", es decir, quiere que, independientemente de cómo se desplacen las secuencias, cada una de ellas tenga al menos un bit que sea cero en las otras secuencias desplazadas, y que sea la ranura cuando consiga enviar su paquete en su aplicación.
(Lo que ha escrito actualmente es "siempre existen $\tau_i$ tal que $s_i^{t_i}(\tau_i) = 1$ y $s_j^{t_j}(\tau_j) = 0$ para $i \neq j$ ". Si se eligen por separado para cada $i$ esto sólo significa que cada uno de los $s_i$ contienen tanto $1$ y $0$ . Si se eligen de una vez por todas, esto es imposible a menos que $n = 1$ .)
Su problema, tal y como yo lo interpreto, está claramente en el co-NP, ya que comprueba que todo ( $\forall$ ) satisfacen una restricción (comprobable en tiempo polinómico), por lo que probablemente no sea NP-difícil, ya que eso colapsaría la jerarquía polinómica. Complementaré tu problema y esbozaré una prueba de la dureza NP del problema resultante, lo que significa que tu problema es co-NP-completo.
Notación: En el conjunto $X = \{0,1\}^{\mathbb{Z}_T}$ tenemos la acción de desplazamiento de $\mathbb{Z}_T = \mathbb{Z}/T\mathbb{Z}$ por $\sigma(s)_i = s_{i+1}, \sigma : X \to X$ . Para $s, s' \in X$ definir $(s \cup s')_i = \max(s_i, s'_i)$ . Escriba $s \leq s'$ para $\forall i: s_i \leq s'_i$ .
El problema complementado: Considere un conjunto de secuencias $S = (s_i)_i$ , $s_i \in X$ . Nosotros decimos $i$ es un índice malo para $S$ si $s_i \leq \bigcup_{j \neq i} \sigma^{t_j}(s_j)$ para algunos $t_j \in \mathbb{Z}_T$ . Nosotros decimos $S$ es mal si existe un índice malo. Claramente $S$ es malo si y sólo si no es bueno. El problema que demostramos que es NP-completo es identificar conjuntos malos de secuencias.
En primer lugar, nos aseguraremos de que $i = 1$ es el único índice malo posible, es decir $s_1$ es la única secuencia que podría ser la unión de las otras. Para ello, pondremos una progresión aritmética $a_i$ en $s_i$ , $i > 1$ . Esta progresión debe ser más larga que $n$ y tal que cualquier otro $s_j$ cubre como máximo un elemento de la misma. Voy a escribir algunas fórmulas para completar.
Elige algunos $M$ (un parámetro para el futuro). Si $a_i$ es la secuencia con soporte $\{kM(n^2+i) \;|\; k = 0,1,...,n+1\}$ , entonces cualquier desplazamiento de $a_i$ cubre como máximo una posición de cualquier otra $a_{i'}$ : si $kM(n^2+i) = k'M(n^2+i')$ , $k, k' \in \{1, ..., n+1\}$ , $i, i' \in \{2, ..., n\}$ y $i' > i$ entonces $k/k' = (n^2+i')/(n^2+i) \in (1, \frac{n^2+n}{n^2+2}] \subset (1, \frac{n+1}{n})$ pero claramente $k/k' > 1 \implies k/k' \geq (n+1)/n$ . Ahora sólo hay que incluir $a_i \leq s_i$ para cada $i \geq 2$ y asegurarnos de que el resto de cosas que incluimos en las secuencias $s_i$ encajan en un único intervalo de longitud $Mn^2$ que está lo suficientemente lejos de $0$ (elija, por ejemplo $T = 100 M n^3$ y queda mucho espacio, ya que la longitud total de $a_i$ es menor que $2Mn^3$ ).
Ahora, consideremos una instancia SAT con $n-1$ variables y cláusulas, $x_i, \phi_i, i \in \{2,...,n\}$ . Para reducir el SAT, queremos $\exists$ tener que hacer una elección binaria para cada $i > 1$ que representará una elección entre $x_i$ y $\neg x_i$ . Elegir progresiones aritméticas $b_i$ de manera similar a como lo hicimos con $a_i$ (pero a menor escala; elija un $M$ por lo que podemos hacer todo lo que sigue en un intervalo de longitud $Mn^2$ como nos prometimos en el párrafo anterior). La secuencia $s_1$ contiene una copia de $b_i$ mientras que $s_i$ contiene dos copias de $b_i$ a distancia $h$ entre sí. Si $\exists$ es ganar, la copia de $b_i$ en $s_1$ tiene que ser cubierto por una de las copias en $s_i$ (tenga en cuenta que mientras $b_i$ cabe en un intervalo de longitud $Mn^2$ El actual $a_j$ -bits en el $s_j$ no son útiles para cubrirlo).
Ahora, podemos añadir para cada cláusula de la instancia SAT un único bit en $s_1$ . Estos bits están en progresión aritmética con la distancia $2h$ entre ellos. Dependiendo de si $x_j$ o $\neg x_j$ aparece en la cláusula (o ninguna), ponemos un $1$ en la posición en $s_j$ de manera que se cubra el bit de la cláusula correcta. (Los bits procedentes de la elección $x_i = \top$ no tocan ningún bit de la cláusula si elegimos el $x_i = \bot$ alineación para $s_i$ ya que esto sólo da un desplazamiento de $h$ y viceversa para el $x_i = \top$ alineación).
