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

27

É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 1v 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 0mnM01v1v2Mv1=Mv2Z

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{1,0,1}n tel que Mv=0 ?

De manière équivalente: étant donné n vecteurs X={x1,,xn} sur {0,1}m , existe-t-il deux sous-ensembles différents A,BX tels que xAx=xBx ?

Mohammad Al-Turkistany
la source
À moins que je ne comprenne mal la question, cela ne revient-il pas à déterminer s'il existe un non nul vtel que Mv=0 ? Et cela n'est-il pas résolu en déterminant le rang de M ?
mhum
8
@mhum non, c'est équivalent à déterminer s'il existe un différent de zéro v{1,0,1}ntel que Mv=0 .
Sasho Nikolov
Ah. J'ai manqué que vi devait aussi être binaire. Mon erreur.
mhum
2
Semble comme le problème de faisabilité pour la programmation 0/1-Integer. Les opérations sont-elles sur Z ou sur Z2 ?
Kaveh
3
Reformulation du problème: Soit n vecteurs X={x1,,xn} sur {0,1}m . Existe-t-il deux sous-ensembles différents tels que ? Je pense qu'il est plus probable que NP soit difficile si les sommes ne sont pas prises modulo deux, c'est-à-dire que les opérations sont terminéesx A x = x B xA,BXxAx=xBxZ
John D.

Réponses:

7

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 xnX={x1,,xm}{0,1}nn
A,BX

xAx=xBx

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

(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 = { yX={x1,,xm}xi{0,1}ntAX

xAx=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 , . . .1Y={y1,...,yn}CmC={C1,...,Cm}xi[j]=1jCi .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 mm a x { x i } = O ( ( m n ) k ) pour k fixe .A,Bm{0,1}nA,Bx1...xmmax{xi}=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 ).AABmn

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 xB={x1,,xm}xi{0,1}nXB1,B2

xB1x=xB2x

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 + SX={x1,,xm}tS=xiXb=t+2Sb=t+S: .B=X{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 AAXxAx=tB1=A{b}B2=BB1=X{A}{b}x B 2 = b + x X A x = b + S - x A x = 2 S

xB1=b+xAx=tt+S=2S
xB2=b+xXAx=b+SxAx=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:B1B2b,b3Sb=t+2SB1

t+2S+xB1{b}x=t+S+xB2{b}x

Par conséquent, nous devons avoir et B 1{ b } est une solution valide pour la SOMME DE VECTEURS 0-1.xB1{b}x=tB1{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.Bb,b

ÉTAPE 3

x1,...,x2nX1,X2X1x2i1,x2i1inX2

X={x1,...,xm}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 

2ix2i1x2i

ÉTAPE 4

A={x1,...,x2m}2m{0,1}nY3m{0,1}2m+n

x2i1,1imy2i1{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}

x2i,1im1y2i{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}

x2m

  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

YY1,Y2X

Marzio De Biasi
la source
ce que vous appelez une partition vectorielle 0-1 équivaut au problème de déterminer si un système d'ensemble a une divergence 0. c'est NP difficile, car il capture par exemple le problème de division 2-2, voir thm 9 dans cet article de guruswami cs.cmu.edu/~venkatg/pubs/papers/ss-jl.ps ; mon article a un peu plus sur la dureté de l'écart paul.rutgers.edu/~anikolov/Files/charikarM.pdf
Sasho Nikolov
|Xi{x2j1,x2j}|=1i{1,2}1jm
(x2i1,x2i)(x2i1,x2i)X1
8

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.

nn

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

lognn

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

Peter Shor
la source
Une précision, vous dites "Maintenant, nous avons des portées aux 1, 2, 4 places"; mais dans le problème, nous ne savons pas quels vecteurs sont sélectionnés, nous devons donc ajouter le gadget de transport à chaque position de bit adjacente? Et dans la première liste de l'exemple, il y a 7 vecteurs, est-ce correct?
Marzio De Biasi
Supposons avoir une solution au problème de somme de sous-ensemble. C'est-à-dire: nous avons 3 + 5 = 8. Maintenant, nous pouvons regarder l'addition dans ce témoin et découvrir où sont les portées. Cela nous donne la solution au problème d'addition vectorielle. Un problème a une solution si et seulement si l'autre le fait.
Peter Shor
2,3,5,78
PS J'ai aussi trouvé une preuve que le problème est NP-complet, mais il est beaucoup plus long que le vôtre, donc j'essaie de le comprendre ... plus simple c'est mieux :-)
Marzio De Biasi
n1n1
3

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:

nX={x1,,xn}{0,1}mm

A,BX

xAx=xBx

X,A,BN

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 , xXxi,xjXxi=xjA={xi},B={xj}

  • X0XAX{0}B=A{0}

  • ABBA

  • A,BABX

  • A,BAB

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 (XAB=XABS(n,k)nkS(n,3)+S(n,2) solutions possibles, donc la force brute n'est pas possible ici.

Nmm=1A,B

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

John D.
la source