Decidir si el núcleo de una matriz contiene algún vector distinto de cero, cuyas entradas son -1, 0 o 1

Dada una matriz binaria por (las entradas son o ), el problema es determinar si existen dos vectores binarios modo que (todas las operaciones se realizan sobre ). ¿Es este problema NP-hard?$m$$n$$M$$0$$1$$v_1 \ne v_2$$Mv_1 = Mv_2$$\mathbb{Z}$

Está claramente en NP, ya que puede dar dos vectores como testigos.

---

Equivalente: dado , ¿hay un vector distinto de cero tal que ?$M$$v\in \{-1,0,1\}^n$$Mv=0$

Equivalente: dados vectores sobre , ¿hay dos subconjuntos diferentes tales que ?$n$$X=\{x_1,\dots,x_n\}$$\{0,1\}^m$$A,B \subseteq X$$\sum_{x \in A} x = \sum_{x \in B} x$

Yo uso la formulación equivalente user17410:

Entrada: vectores X = { x 1 , ... , x m } sobre { 0 , 1 } n , n es parte de la entrada Pregunta: ¿Hay dos subconjuntos diferentes A , B ⊆ X tales que ∑ x ∈ A x = ∑ x ∈ B$n$$X = \{ x_1, \dots, x_m \}$$\{0,1\}^n$$n$
$A,B \subseteq X$

$$\sum_{x \in A} x = \sum_{x \in B} x$$

La prueba de dureza involucra muchas reducciones intermedias que siguen la misma "cadena" utilizada para probar la dureza del problema estándar EQUAL SUBSET SUM:

X3c SUBSET SUM ≤ PARTITION ≤ PARTITION par-impar ≤ EQUAL SUBSET SUM$\leq$$\leq$$\leq$$\leq$

(Todavía lo estoy revisando, así que puede estar mal :)

PASO 1

El siguiente problema ( SUMA DEL SUBSETO DEL VECTOR 0-1 ) es NP-completo: dado , x i vectores sobre { 0 , 1 } ny un vector de suma objetivo t , decida si hay A ⊆ X tal que ∑ x ∈ A x = t Prueba : reducción directa de la CUBIERTA EXACTA POR 3-SETS (X3C): dado un conjunto de n elementos Y = { $X = \{ x_1, \dots, x_m \}$$x_i$$\{0,1\}^n$$t$$A \subseteq X$

$$\sum_{x \in A} x = t$$ $n$ y una colección C de m tres elementos subconjuntos C = { C 1 , . . . , C m } construimos la configuración de instancia 0-1 VECTOR SUM correspondiente x i [ j ] = 1 si y solo si el elemento j está incluido en C i ; t = [ 1 , 1 , . . $Y = \{y_1,...,y_n\}$$C$$m$$C = \{C_1,...,C_m\}$$x_i[j] = 1$$j$$C_i$ .$t = [1,1,...1]$

PASO 2 Encontrar dos subconjuntos de suma igual entre m 0-1 vectores sobre { 0 , 1 } n , es equivalente a encontrar dos subconjuntos de suma igual A , B de vectores con elemento de tamaño acotado x 1 . . . x m donde m a x { x i } = O ( ( m n ) k ) para k fijo .$A,B$$m$$\{0,1\}^n$$A,B$$x_1 ... x_m$$max\{x_i\} = O((mn)^k)$$k$

Por ejemplo el conjunto de vectores:

x1 2 1 0 1
x2 1 2 3 1

Es equivalente a los vectores 0-1:

x1  1 1 0 1   1 0   0 0 0
    1 0 0 0   0 1   0 0 0 
    0 0 0 0   1 1   0 0 0 
              ^ ^
                +-- 0 elsewhere

x2  1 1 1 1   0 0   1 0 0
    0 1 1 0   0 0   0 1 0
    0 0 1 0   0 0   0 0 1
    0 0 0 0   0 0   1 1 1
                    ^ ^ ^
                      +-- 0 elsewhere

Informalmente, los vectores 0-1 se agrupan (si selecciona un vector del grupo x2 y lo agrega al subconjunto , entonces se ve obligado a incluir en A los otros dos y colocar el último en el subconjunto B ) y las sumas se hacen en unario (esta es la razón por la cual los vectores no binarios correspondientes deben contener elementos que están polinómicamente delimitados con respecto a m n ).$A$$A$$B$$mn$

Entonces, el siguiente problema es NP-completo.

PASO 3

El siguiente problema ( 0-1 PARTICIÓN VECTORIAL ) es NP-completo: dado , x i vectores sobre { 0 , 1 } n deciden si X puede dividirse en dos subconjuntos B 1 , B 2 tal que ∑ x ∈ B 1 x = ∑ x ∈ B 2$B = \{ x_1, \dots, x_m \}$$x_i$$\{0,1\}^n$$X$$B_1, B_2$

$$\sum_{x \in B_1} x = \sum_{x \in B_2} x$$

Prueba : Reducción de 0-1 SUMA DEL VECTOR: dado y el vector de suma objetivo t ; sea S = ∑ x i , agregamos a X los siguientes vectores: b ′ = - t + 2 S y b ″ = t + $X = \{ x_1, \dots, x_m \}$$t$$S = \sum x_i$$X$$b' = -t + 2S$$b'' = t + S\;$: .$B = X \cup \{b',b''\}$

( ) Suponga que existe A ⊆ X tal que ∑ x ∈ A x = t ; establecemos B 1 = A ∪ { b ′ } y B 2 = B ∖ B 1 = X ∖ { A } ∪ { b ″ } ; tenemos ∑ x ∈ B 1 = b ′ + ∑ x ∈ $\Rightarrow$$A \subseteq X$$\sum_{x \in A} x= t$$B_1 = A \cup \{b'\}$$B_2 =B \setminus B_1 = X \setminus \{A\} \cup \{b''\}$∑ x ∈ B 2 = b ″ + ∑ x ∈ X ∖ A x = b ″ + S - ∑ x ∈ A x = 2

$$\sum_{x \in B_1} = b'+\sum_{x \in A} x = t - t + S = 2S$$ $$\sum_{x \in B_2} = b'' + \sum_{x \in X\setminus A} x = b'' + S - \sum_{x \in A} x=2S$$

( ) Suponga que B 1 y B 2 tienen la misma suma. b ′ , b ″ no pueden pertenecer al mismo conjunto (de lo contrario, su suma es ≥ 3 S y los elementos del otro conjunto no pueden "equilibrarla"). Supongamos que b ′ = - t + 2 S ∈ B 1 ; tenemos:$\Leftarrow$$B_1$$B_2$$b', b''$$\geq 3S$$b' = -t + 2S \in B_1$

$$-t +2S+ \sum_{x \in B_1 \setminus\{b'\}} x = t + S + \sum_{x \in B_2 \setminus\{b''\}} x$$

Por lo tanto tenemos que tener y B 1 ∖ { b ' } es una solución válida para el 0-1 VECTOR SUM.$\sum_{x \in B_1 \setminus\{b'\}} x = t$$B_1 \setminus\{b'\}$

Solo permitimos 0-1 vectores en el conjunto , por lo que los vectores b ' , b ″ deben estar "representados en unario" como se muestra en el PASO 2.$B$$b', b''$

PASO 3

El problema es todavía NP-completo si los vectores se numeran de los dos subconjuntos X 1 , X 2 deben tener el mismo tamaño y se requiere que X 1 contenga exactamente uno de x 2 i - 1 , x 2 i para 1 ≤ i ≤ n (entonces, por la restricción de igual tamaño , el otro elemento del par debe incluirse en X 2 ) ( 0-1 VECTOR INCLUSO-PARTICIÓN ).$x_1,...,x_2n$$X_1,X_2$$X_1$$x_{2i-1},x_{2i}$$1 \leq i \leq n$$X_2$

Prueba: La reducción es de 0-1 PARTICIÓN DE VECTOR y es similar a la reducción de PARTICIÓN a PARTICIÓN INCLUSO. Si son m vectores sobre { 0 , 1 } n reemplaza cada vector con dos vectores sobre { 0 , 1 } 2 n + 2 m :$X = \{x_1,...,x_m\}$$m$$\{0,1\}^n$$\{0,1\}^{2n+2m}$

       1   2       n
 --------------------
 x_i  b_1 b_2 ... b_n

 becomes:

           1 2 ... 2i ... 2m
  --------------------------
  x'_2i-1  0 0 ...  1 ...  0  b_1 b_2 ... b_n   0   0  ...  0  
  x'_2i    0 0 ...  1 ...  0   0   0  ...  0   b_1 b_2 ... b_n 

Debido al elemento , los vectores x ′ 2 i - 1 y x ′ 2 i no pueden estar contenidos en el mismo subconjunto; y una solución válida para la PARTICIÓN INCLUSIVA DEL VECTOR 0-1 corresponde a una solución válida de la PARTICIÓN DEL VECTOR 0-1 original (solo seleccione los elementos 2m + 1..2m + n de cada vector de la solución descartando los vectores que contienen todos ceros en esas posiciones).$2i$$x'_{2i-1}$$x'_{2i}$

ETAPA 4

0-1 VECTOR IGUAL SUBSET SUM (el problema en la pregunta) es NP-complete: reducción de 0-1 VECTOR PARTICIÓN INCLUSIVA similar a la reducción de EVEN-ODD PARTITION a EQUAL SUM SUBSET, como se demostró en Gerhard J. Woeginger , Zhongliang Yu, sobre el problema de igual subconjunto de suma : dado un conjunto ordenado de 2 m vectores sobre { 0 , 1 } n , construimos un conjunto Y de 3 m vectores sobre { 0 $A = \{x_1,...,x_{2m}\}$$2m$$\{0,1\}^n$$Y$$3m$ .$\{0,1\}^{2m+n}$

Para cada vector construimos un vector y 2 i - 1 sobre { 0 , 1 } 2 m + n de esta manera:$x_{2i-1}, 1 \leq i \leq m$$y_{2i-1}$$\{0,1\}^{2m+n}$

  1 2 ... i i+1 ... m  m+1 m+2 ... m+i ... 2m  2m+1 ... 2m+n
  ------------------------------------------------------
  0 0 ... 2  0  ... 0   0   0       1       0  x_{2i-1}

Para cada vector construimos un vector y 2 i sobre { 0 , 1 } 2 m + n de esta manera:$x_{2i}, 1 \leq i \leq m-1$$y_{2i}$$\{0,1\}^{2m+n}$

  1 2 ... i i+1 ... m  m+1 m+2 ... m+i ... 2m  2m+1 ... 2m+n
  ------------------------------------------------------
  0 0 ... 0  2  ... 0   0   0       1       0  x_{2i}

Mapeamos el elemento para$x_{2m}$

  1 2 ...       ... m  m+1 m+2 ...  . 2m  2m+1 ... 2m+n
  ------------------------------------------------------
  2 0 ...       ... 0   0   0          1  x_{2m}

Finalmente agregamos elementos ficticios:$m$

  1 2 ...       ... m  m+1 m+2 ...  ... 2m  2m+1 ... 2m+n
  ------------------------------------------------------
  4 0 ...       ... 0   0   0            0  0    ... 0
  0 4 ...       ... 0   0   0            0  0    ... 0
  ...
  0 0 ...       ... 4   0   0            0  0    ... 0

Observe nuevamente que los vectores que contienen valores pueden representarse en "unario" usando un grupo de vectores 0-1 como se muestra en el PASO 2.$> 1$

tiene dos subconjuntos disjuntos Y 1 , Y 2 que tienen la misma suma si y solo si X tiene una partición par-impar. $Y$$Y_1,Y_2$$X$

EDITAR: Mi prueba original tenía un error. Ahora creo que está arreglado.

Reducimos el problema de los EQUIPOS DE SUMA IGUAL a este problema. El problema de: SUBSETOS DE SUMA IGUAL es: dado un conjunto de enteros, encontrar dos subconjuntos disjuntos que tengan la misma suma. Se sabe que los SUBSETOS DE IGUAL SUMA son NP completos.$m$

Supongamos que estas cadenas de bits no son vectores, sino representaciones de números de bits en binario. Entonces el problema sería NP-completo mediante una reducción de SUBSETES DE SUMA IGUAL. Mostraré cómo hacer que estos vectores se comporten como si fueran números binarios. Lo que necesitamos es poder hacer acarreos; es decir, para cada par de coordenadas adyacentes, necesitamos poder reemplazar el vector ..02 .. por ..10 ...$n$

¿Cómo podemos hacer eso? Necesitamos un gadget que nos permita hacer eso. En particular, necesitamos dos subconjuntos cuyas sumas son ..02 .. x y ..10 .. x, donde x es una cadena de bits que utiliza nuevas coordenadas (es decir, coordenadas que no son ninguna de las coordenadas que forman el binario representaciones), y donde solo hay una forma de crear dos subconjuntos con la misma suma en las nuevas posiciones de bit correspondientes a x.$n$

Esto es bastante fácil de hacer. Para cada par de posiciones de bits adyacentes, agregue tres vectores de la siguiente forma. Aquí los dos últimos bits son coordenadas que no son cero solo en estos tres vectores, y cada bit que no se proporciona explícitamente a continuación es 0.

..10 .. 11
..01 .. 10
..01 .. 01

Déjame hacer un ejemplo. Queremos mostrar cómo funciona 5 + 3 = 8.

Aquí hay 8 = 5 + 3 en binario:

1000

=

0101
0011

Estas cadenas de bits dan la misma suma en binario, pero no en la suma de vectores.

Ahora, tenemos acarreos en los lugares 1, 2, 4, por lo que necesitamos agregar tres conjuntos de tres vectores a la ecuación para realizar estos acarreos.

1000 00 00 00
0001 00 00 01
0001 00 00 10
0010 00 01 00
0010 00 10 00
0100 01 00 00
0100 10 00 00

=

0101 00 00 00
0011 00 00 00
0010 00 00 11
0100 00 11 00
1000 11 00 00

Estos conjuntos ahora tienen la misma suma en la suma de vectores. Las sumas son:

1222 11 11 11

en ambos casos.

$n$$n$

..01 .. 01 00
..01 .. 10 00
..10 .. 11 00
..01 .. 00 01
..01 .. 00 10
..10 .. 00 11

tienes el problema de que obtienes dos conjuntos diferentes de vectores que dan la misma suma:

..01 .. 01 00
..01 .. 10 00
..10 .. 00 11

=

..01 .. 00 01
..01 .. 00 10
..10 .. 11 00

$\ldots$$^{\lfloor \log n \rfloor}$$n$

..01 .. 11000
..01 .. 00100
..01 .. 00010
..01 .. 00001
..10 .. 10001
..10 .. 01110

trabajos. Puede verificar fácilmente que la relación

11000
00100
00010
00001

=

10001
01110

es la única relación posible entre estos seis vectores porque la matriz formada por estas seis filas tiene rango 5.

Esto no responde la pregunta, pero puede contener algunas observaciones útiles. No quería ponerlo como un comentario porque los comentarios largos y fragmentados son molestos de leer

La reformulación del problema como se indica en mi comentario a la pregunta:

$n$$X = \{ x_1, \dots, x_n \}$$\{0,1\}^m$$m$

$A,B \subseteq X$

$$\sum_{x \in A} x = \sum_{x \in B} x$$

$X,A,B$$\mathbb{N}$

Propongo llamar a este problema 2SUBSET-BINARY-VECTOR-SUM debido al hecho de que estamos buscando 2 subconjuntos de vectores binarios.

Algunas observaciones

• $X$$x_i,x_j \in X$$x_i = x_j$$A = \{x_i\}, B = \{x_j\}$

• $X$$0 \in X$$A \subseteq X \setminus \{ 0 \}$$B = A \cup \{ 0 \}$

• $A \subset B$$B$$A$

• $A,B$$A \subset B$$X$

• $A,B$$A \cap B \neq \emptyset$

$X$$A \cup B = X$$A$$B$$S(n,k)$$n$$k$$S(n,3)+S(n,2)$ posibles soluciones, por lo que la fuerza bruta no es factible aquí.

$\mathbb{N}^m$$m=1$$A,B$

$\{1,2,3,5\}$$A=\{1,2\} , B = \{3\}$$m>1$$A,B$