Décidez si le noyau d'une matrice contient un vecteur différent de zéro dont toutes les entrées sont -1, 0 ou 1

Étant donné une matrice binaire par (les entrées sont ou 1 ), le problème est de déterminer s'il existe deux vecteurs binaires v 1 ≠ v 2 tels que M v 1 = M v 2 (toutes les opérations effectuées sur Z ). Ce problème est-il difficile à NP?n M $m$$n$$M$$0$$1$$v_1 \ne v_2$$Mv_1 = Mv_2$$\mathbb{Z}$

C'est clairement dans NP car vous pouvez donner deux vecteurs comme témoins.

---

De manière équivalente: étant donné $M$ , existe-t-il un vecteur non nul $v\in \{-1,0,1\}^n$ tel que $Mv=0$ ?

De manière équivalente: étant donné $n$ vecteurs $X=\{x_1,\dots,x_n\}$ sur $\{0,1\}^m$ , existe-t-il deux sous-ensembles différents $A,B \subseteq X$ tels que $\sum_{x \in A} x = \sum_{x \in B} x$ ?

J'utilise la formulation équivalente user17410:

Entrée: vecteurs X = { x 1 , … , x m } sur { 0 , 1 } n , n fait partie de l'entrée Question: Y a-t-il deux sous-ensembles différents A , B ⊆ X tels 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 preuve de dureté implique de nombreuses réductions intermédiaires qui suivent la même "chaîne" utilisée pour prouver la dureté du problème standard EQUAL SUBSET SUM:

X3c SUBSET SUM de l'PARTITION ≤ pair-impair PARTITION ≤ EQUAL SUM SUBSET$\leq$$\leq$$\leq$$\leq$

(Je suis toujours en train de le vérifier donc ça peut être faux :)

ÉTAPE 1

Le problème suivant ( 0-1 VECTOR SUBSET SUM ) est NP-complet: étant donné les vecteurs , x i sur { 0 , 1 } n et un vecteur de somme cible t , décidez s'il y a A ⊆ X tel que ∑ x ∈ A x = t Preuve : réduction directe de la COUVERTURE EXACTE PAR 3 ENSEMBLES (X3C): étant donné un ensemble de n éléments Y = { $X = \{ x_1, \dots, x_m \}$$x_i$$\{0,1\}^n$$t$$A \subseteq X$

$$\sum_{x \in A} x = t$$ $n$ et un ensemble C de m trois éléments de C = { C 1 , . . . , C m } nous construisons le paramètre d'instance 0-1 VECTOR SUM correspondant x i [ j ] = 1 si et seulement si l'élément j est inclus dans 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]$

ÉTAPE 2 Trouver deux sous-ensembles à somme égale parmi m vecteurs 0-1 sur { 0 , 1 } n , équivaut à trouver deux sous-ensembles à somme égale A , B de vecteurs avec un élément de taille bornée x 1 . . . x m où m a x { x i } = O ( ( m n ) k ) pour k fixe .$A,B$$m$$\{0,1\}^n$$A,B$$x_1 ... x_m$$max\{x_i\} = O((mn)^k)$$k$

Par exemple l'ensemble des vecteurs:

x1 2 1 0 1
x2 1 2 3 1

Est équivalent aux vecteurs 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

Informellement, les vecteurs 0-1 sont regroupés (si vous sélectionnez un vecteur du groupe x2 et l'ajoutez au sous-ensemble , vous êtes alors obligé d'inclure dans A les deux autres et de mettre le dernier dans le sous-ensemble B ) et les sommes sont faites dans unaire (c'est la raison pour laquelle les vecteurs non binaires correspondants doivent contenir des éléments qui sont polynomialement liés par rapport à m n ).$A$$A$$B$$mn$

Le problème suivant est donc NP-complet.

ÉTAPE 3

Le problème suivant ( 0-1 VECTOR PARTITION ) est NP-complet: étant donné , x i vecteurs sur { 0 , 1 } n décident si X peut être partitionné en deux sous-ensembles B 1 , B 2 tel 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$$

Preuve : réduction de 0 à 1 SOMME DE VECTEURS: étant donné et le vecteur de somme cible t ; soit S = ∑ x i , on ajoute à X les vecteurs suivants: b ′ = - t + 2 S et 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''\}$

( ) Supposons qu'il existe A ⊆ X tel que ∑ x ∈ A x = t ; nous posons B 1 = A ∪ { b ′ } et B 2 = B ∖ B 1 = X ∖ { A } ∪ { b ″ } ; on a ∑ 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$$

( ) Supposons que B 1 et B 2 ont une somme égale. b ' , b " ne peuvent pas tous deux appartenir au même ensemble (sinon leur somme est ≥ 3 S et ne peut pas être" équilibrée "par les éléments de l'autre ensemble). Supposons que b ′ = - t + 2 S ∈ B 1 ; on a:$\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$$

Par conséquent, nous devons avoir et B 1 ∖ { b ′ } est une solution valide pour la SOMME DE VECTEURS 0-1.$\sum_{x \in B_1 \setminus\{b'\}} x = t$$B_1 \setminus\{b'\}$

Nous autorisons uniquement les vecteurs 0-1 dans l'ensemble , donc les vecteurs b ' , b " doivent être" représentés en unaire "comme indiqué à l'ÉTAPE 2.$B$$b', b''$

ÉTAPE 3

$x_1,...,x_2n$$X_1,X_2$$X_1$$x_{2i-1},x_{2i}$$1 \leq i \leq n$$X_2$

$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 

$2i$$x'_{2i-1}$$x'_{2i}$

ÉTAPE 4

$A = \{x_1,...,x_{2m}\}$$2m$$\{0,1\}^n$$Y$$3m$$\{0,1\}^{2m+n}$

$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}

$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}

$x_{2m}$

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

$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

$> 1$

$Y$$Y_1,Y_2$$X$

EDIT: Ma preuve d'origine avait un bug. Je crois maintenant que c'est corrigé.

$m$

$n$

$n$

C'est assez facile à faire. Pour chaque paire de positions de bits adjacentes, ajoutez trois vecteurs de la forme suivante. Ici, les deux derniers bits sont des coordonnées qui ne sont pas nulles uniquement dans ces trois vecteurs, et chaque bit non explicitement donné ci-dessous est 0.

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

Permettez-moi de faire un exemple. Nous voulons montrer comment fonctionne 5 + 3 = 8.

Voici 8 = 5 + 3 en binaire:

1000

=

0101
0011

Ces chaînes de bits donnent la même somme en binaire, mais pas en addition vectorielle.

Maintenant, nous avons des portées aux 1, 2, 4 endroits, nous devons donc ajouter trois ensembles de trois vecteurs à l'équation afin d'effectuer ces portées.

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

Ces ensembles ont désormais la même somme en addition vectorielle. Les sommes sont:

1222 11 11 11

dans les deux cas.

$n$$n$

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

vous avez le problème d'obtenir deux ensembles de vecteurs différents donnant la même somme:

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

travaux. Vous pouvez facilement vérifier que la relation

11000
00100
00010
00001

=

10001
01110

est la seule relation possible entre ces six vecteurs car la matrice formée par ces six rangées a le rang 5.

Cela ne répond pas à la question mais peut contenir des observations utiles. Je ne voulais pas le mettre en commentaire car je trouve des commentaires longs et fragmentés gênants à lire

La reformulation du problème comme indiqué dans mon commentaire à la question:

$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}$

Je propose d'appeler ce problème 2SUBSET-BINARY-VECTOR-SUM car nous recherchons 2 sous-ensembles de vecteurs binaires.

Quelques observations:

• Si contient un vecteur plusieurs fois, la réponse devient triviale. Soit x i , $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$

Ces points signifient essentiellement que vous recherchez une partition de en deux ensembles ( A ∪ B = X ) ou trois ensembles. Le troisième ensemble représente les vecteurs qui ont été non sélectionnée soit pour A ou B . Soit S $X$$A \cup B = X$$A$$B$$S(n,k)$$n$$k$$S(n,3)+S(n,2)$ solutions possibles, donc la force brute n'est pas possible ici.

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

Considérez . Ce n'est pas dans UNIQUE-PARTITION mais A = { $\{1,2,3,5\}$$A=\{1,2\} , B = \{3\}$$m>1$$A,B$