Entscheiden Sie, ob der Kernel einer Matrix einen Vektor ungleich Null enthält, dessen Einträge alle -1, 0 oder 1 sind

27

Bei einem gegebenen m von n binären Matrix M (Einträge sind 0 oder 1 ), ist das Problem , zu bestimmen , ob es existiert zwei binäre Vektoren v1v2 , so daß Mv1=Mv2 (alle Operationen durchgeführt über Z ). Ist das Problem NP-schwer?

Es ist eindeutig in NP, da Sie zwei Vektoren als Zeugen angeben können.


Äquivalent: Gibt es bei gegebenem M einen Nicht-Null-Vektor v{1,0,1}n so dass Mv=0 ?

Äquivalent: Wenn Vektoren X = { x 1 , , x n } über { 0 , 1 } m gegeben sind , gibt es zwei verschiedene Teilmengen A , B X, so dass x A x = x B x ?nX={x1,,xn}{0,1}mA,BXxAx=xBx

Mohammad Al-Turkistany
quelle
Wenn ich die Frage nicht falsch verstehe, ist dies nicht gleichbedeutend mit der Feststellung, ob es ein ungleich Null gibt, so dass M v = 0 ist ? Und ist dies nicht durch die Bestimmung des Ranges von M gelöst ? vMv=0M
mhum
8
@mhum nein, es ist äquivalent zu bestimmen, ob es ein von Null verschiedenes so dass M v = 0 ist . v{1,0,1}nMv=0
Sasho Nikolov
Ah. Ich vermisste , dass musste auch binär sein. Mein Fehler. vi
mhum
2
Scheint das Machbarkeitsproblem für die 0/1-Integer-Programmierung zu sein. Liegen Operationen über oder über Z 2 ? ZZ2
Kaveh
3
Umformulierung des Problems: Gegeben sind Vektoren X = { x 1 , , x n } über { 0 , 1 } m . Gibt es zwei verschiedene Teilmengen A , B X, so dass x A x = x B x ? Ich würde denken, dass es wahrscheinlicher ist, NP-schwer zu sein, wenn die Summen nicht modulo zwei genommen werden, das heißt Operationen sind über ZnX={x1,,xn}{0,1}mEIN,BXxEINx=xBxZ
John D.

Antworten:

7

Ich verwende die äquivalente Formulierung user17410:

Eingabe: Vektoren X = { x 1 , , x m } über { 0 , 1 } n , n ist Teil der Eingabe Frage: Gibt es zwei verschiedene Teilmengen A , B X, so dass x A x = x B xnX={x1,,xm}{0,1}nn
A,BX

xAx=xBx

Der Härtenachweis beinhaltet viele Zwischenreduktionen, die der gleichen "Kette" folgen, die zum Nachweis der Härte des Standardproblems EQUAL SUBSET SUM verwendet wird:

X3C SUBSET SUM PARTITION Gerade-Ungerade - PARTITION EQUAL SUBSET SUM

(Ich überprüfe es immer noch, damit es falsch sein kann :)

SCHRITT 1

Das folgende Problem ( 0-1 VECTOR SUBSET SUM ) ist NP-vollständig: Wenn , x i Vektoren über { 0 , 1 } n und ein Zielsummenvektor t gegeben sind , entscheiden Sie, ob es existiert A x , so daß Σ x A x = t Proof : Direktreduktion von EXACT COVER BY 3-SETS (X3C): ein Satz von gegebenen n Elemente Y = { yX={x1,,xm}xi{0,1}ntAX

xAx=t
n und eine Sammlung C von mY={y1,...,yn}Cm drei Elementen Subsets erstellen wir die entsprechende 0-1 VECTOR SUM-Instanzeinstellung x i [ j ] = 1, wenn und nur wenn das Element j in C i enthalten ist ; t = [ 1 , 1 , . . ] .C={C1,...,Cm}xi[j]=1jCit=[1,1,...1]

SCHRITT 2 Das Finden von zwei gleichen Summenteilmengen unter m 0-1 Vektoren über { 0 , 1 } n entspricht dem Finden von zwei gleichen Summenteilmengen A , B von Vektoren mit einem Element der begrenzten Größe x 1 . . . x m mit m a x { x i } = O ( ( m n ) k ) für festes k .A,Bm{0,1}nA,Bx1...xmmax{xi}=O((mn)k)k

Zum Beispiel die Menge der Vektoren:

x1 2 1 0 1
x2 1 2 3 1

Entspricht den 0-1 Vektoren:

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

Informell werden die 0-1-Vektoren gruppiert (wenn Sie einen Vektor der x2-Gruppe auswählen und zu Untergruppe hinzufügen , müssen Sie die anderen beiden in A aufnehmen und die letzten in Untergruppe B einfügen ) und die Summen werden in erstellt unär (dies ist der Grund, warum die entsprechenden nicht-binären Vektoren Elemente enthalten müssen, die in Bezug auf m n polynomiell begrenzt sind ).AABmn

Das folgende Problem ist also NP-vollständig.

SCHRITT 3

Das folgende Problem ( 0-1 VECTOR PARTITION ) ist NP-vollständig: Wenn , x i Vektoren über { 0 , 1 } n gegeben sind, entscheidet dies, ob X in zwei Teilmengen B 1 aufgeteilt werden kann. B 2 so, dass x B 1 x = x B 2 xB={x1,,xm}xi{0,1}nXB1,B2

xB1x=xB2x

Beweis : Reduktion von 0-1 VEKTORSUMME: gegebenes und der Zielsummenvektor t ; sei S = x i , addieren wir zu X die folgenden Vektoren: b = - t + 2 S und b = t + SX={x1,,xm}tS=xiXb=t+2Sb=t+S: .B=X{b,b}

( ) Angenommen , dass es existiert A X , so daß Σ x A x = t ; wir setzen B 1 = A { b } und B 2 = B B 1 = X { A } { b } ; wir haben 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

xB1=b+xAx=tt+S=2S
xB2=b+xXAx=b+SxAx=2S

( ) Angenommen, B 1 und B 2 haben die gleiche Summe. b ' , b' ' können nicht beide zu derselben Menge gehören (andernfalls ist ihre Summe 3 S und kann nicht durch die Elemente in der anderen Menge "ausgeglichen" werden). Nehmen wir an, dass b ' = - t + 2 S B 1 ; wir haben:B1B2b,b3Sb=t+2SB1

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

Wir müssen also und B 1{ b } ist eine gültige Lösung für die 0-1-VEKTORSUMME.xB1{b}x=tB1{b}

Wir erlauben nur 0-1 Vektoren in dem Satz , also Vektoren , b ' , b " müssen„in unäre dargestellt“ , wie in Schritt 2 gezeigt ist .Bb,b

SCHRITT 3

Das Problem ist noch NP-vollständig , wenn die Vektoren aus nummeriert sind und die beiden Teilmengen X 1 , X 2 müssen gleich groß sein, und wir fordern, dass X 1 genau eines von x 2 i - 1 , x 2 i für 1 i n enthält (also durch die Bedingung gleicher Größe) muss das andere Element des Paares in X enthalten seinx1,...,x2nX1,X2X1x2i1,x2i1in ) enthalten sein (0-1 VECTOR EVEN-ODD PARTITION).X2

Beweis: Die Verkleinerung erfolgt von 0-1 VECTOR PARTITION und ähnelt der Verkleinerung von PARTITION auf EVEN-ODD PARTITION. Wenn sind m Vektoren über { 0 , 1 } n Ersetzen Sie jeden Vektor durch zwei Vektoren über { 0 , 1 } 2 n + 2 m :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 

Aufgrund des -Elements können die Vektoren x ' 2 i - 1 und x ' 2 i nicht in derselben Teilmenge enthalten sein; und eine gültige Lösung für die 0-1 VECTOR EVEN-ODD PARTITION entspricht einer gültigen Lösung der ursprünglichen 0-1 VECTOR PARTITION (wählen Sie einfach die Elemente 2m + 1..2m + n jedes Vektors der Lösung aus und verwerfen Sie Vektoren, die alle enthalten Nullen in diesen Positionen).2ix2i1x2i

SCHRITT 4

0-1 VECTOR EQUAL SUBSET SUM (das Problem in der Frage) ist NP-vollständig: Reduktion von 0-1 VECTOR EVEN-ODD PARTITION ähnlich der Reduktion von EVEN-ODD PARTITION auf EQUAL SUM SUBSET, wie in Gerhard J. Woeginger bewiesen , Zhongliang Yu, auf dem Gleich-Subset-sum Problem : Bei einer gegebenen Satz bestellen von 2 m Vektoren über { 0 , 1 } n bilden wir eine Menge Y von 3 m Vektoren über { 0 ,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 auf diese Weise :

  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 zu

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

Schließlich fügen wir hinzu m Dummy-Elemente:

  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

Beachten Sie erneut, dass Vektoren Werte enthalten >1 kann unter Verwendung einer Gruppe von 0-1 Vektoren wie in SCHRITT 2 gezeigt "unär" dargestellt werden.

Y. hat zwei disjunkt Y.1,Y.2 Teilmengen mit gleicher Summe genau dann, wenn X hat eine gerade-ungerade Partition.

Marzio De Biasi
quelle
what you call 0-1 vector partition is equivalent to the problem of determining if a set system has discrepancy 0. this is NP hard, since it captures e.g. the 2-2-set-splitting problem, see thm 9 in this paper by guruswami cs.cmu.edu/~venkatg/pubs/papers/ss-jl.ps; my paper has a bit more on the hardness of discrepancy paul.rutgers.edu/~anikolov/Files/charikarM.pdf
Sasho Nikolov
also I believe you mis-state the even-odd partition problem. if no two consecutive vectors can be in the same set the problem is trivial. i believe you mean that |Xi{x2j1,x2j}|=1 is required for all i{1,2} and 1jm
Sasho Nikolov
@SashoNikolov: Ja, das meine ich für jedes Paar (x2ich-1,x2ich) (und im Beweis (x2ich-1,x2ich)) genau eine ist enthalten in X1; Ich werde die Antwort bearbeiten
Marzio De Biasi
8

EDIT: Mein Original-Proof hatte einen Fehler. Ich glaube jetzt, dass es behoben ist.

Wir reduzieren das Problem von EQUAL SUM SUBSETS auf dieses Problem. EQUAL SUM SUBSETS ist das Problem von: gegeben einer Menge vonmGanzzahlen finden Sie zwei disjunkte Teilmengen, die die gleiche Summe haben. Es ist bekannt, dass EQUAL SUM SUBSETS NP-vollständig sind.

Angenommen, diese Bitfolgen waren keine Vektoren, sondern Darstellungen von n-Bit-Zahlen im Binärformat. Dann wäre das Problem NP-vollständig durch eine Reduktion von EQUAL SUM SUBSETS. Ich werde zeigen, wie diese Vektoren sich wie Binärzahlen verhalten. Was wir brauchen, ist in der Lage zu sein zu tragen; Das heißt, für jedes Paar benachbarter Koordinaten müssen wir in der Lage sein, den Vektor ..02 .. durch ..10 .. zu ersetzen.

Wie können wir das machen? Wir brauchen ein Gerät , mit dem wir das machen können. Insbesondere benötigen wir zwei Teilmengen mit den Summen ..02 .. x und ..10 .. x, wobei x eine Bitfolge ist, die neue Koordinaten verwendet (dh Koordinaten, die keine der Koordinaten sind)n Koordinaten, die die binären Darstellungen bilden), und wo es nur einen Weg gibt, zwei Teilmengen mit der gleichen Summe in den neuen Bitpositionen zu erzeugen, die x entsprechen.

Das ist ziemlich einfach. Addieren Sie für jedes Paar benachbarter Bitpositionen drei Vektoren der folgenden Form. Hier sind die letzten beiden Bits Koordinaten, die nur in diesen drei Vektoren nicht Null sind, und jedes nicht explizit unten angegebene Bit ist 0.

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

Lassen Sie mich ein Beispiel machen. Wir wollen zeigen, wie 5 + 3 = 8 funktioniert.

Hier ist 8 = 5 + 3 in binärer Form:

1000

=

0101
0011

Diese Bitfolgen ergeben die gleiche Summe in binärer Form, jedoch nicht in Vektoraddition.

Nun haben wir Überträge an den Stellen 1, 2, 4, also müssen wir der Gleichung drei Sätze von drei Vektoren hinzufügen, um diese Überträge auszuführen.

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

=

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

Diese Mengen haben nun die gleiche Summe bei der Vektoraddition. Die Summen sind:

1222 11 11 11

in beiden Fällen.

Diese Konstruktion funktioniert gut, wenn es nur einen Übertrag pro Position gibt, aber möglicherweise bis zu n trägt pro Position, und Sie müssen sicherstellen, dass Ihre Konstruktion bis zu verarbeiten ist nträgt, und dass die verschiedenen trägt sich nicht gegenseitig stören. Wenn Sie beispielsweise zwei verschiedene Sätze von drei Vektoren für dasselbe Paar benachbarter Positionen hinzugefügt haben (was ich in meinem ursprünglichen Beweis vorgeschlagen habe):

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

Sie haben das Problem, dass Sie zwei verschiedene Vektorsätze erhalten, die dieselbe Summe ergeben:

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

=

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

Wie kann man das beheben? Fügen Sie einen Satz Vektoren hinzu, mit dem Sie 1, einen Satz mit 2 und einen Satz für 4, 8 tragen können., 2Logn. Ich werde im Moment nicht die Details dieser Konstruktion herausarbeiten, aber es sollte ziemlich einfach sein. Da jede Zahl eine eindeutige Binärdarstellung hat, können Sie jede Zahl bis zu tragenn. Zum Tragen von 4 benötigen Sie beispielsweise vier Vektoren, die die gleiche Summe wie zwei Vektoren haben und für die dies die einzige lineare Beziehung zwischen den beiden Mengen ist. Zum Beispiel das Set

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

funktioniert. Sie können leicht überprüfen, ob die Beziehung

11000
00100
00010
00001

=

10001
01110

ist die einzig mögliche Beziehung zwischen diesen sechs Vektoren, da die durch diese sechs Zeilen gebildete Matrix Rang 5 hat.

Peter Shor
quelle
Zur Klarstellung sagen Sie: "Jetzt haben wir in den 1, 2, 4 Stellen trägt"; aber in dem Problem wissen wir nicht, welche Vektoren ausgewählt sind, so dass wir das Übertrags-Gadget zu jeder benachbarten Bitposition hinzufügen müssen? Und in der ersten Liste des Beispiels gibt es 7 Vektoren, ist das richtig?
Marzio De Biasi
Angenommen, Sie haben eine Lösung für das Teilmengen-Summenproblem. Das heißt: Wir haben 3 + 5 = 8. Jetzt können wir uns den Zusatz in diesem Zeugnis ansehen und herausfinden, wo sich die Überträge befinden. Dies gibt uns die Lösung für das Vektoradditionsproblem. Ein Problem hat genau dann eine Lösung, wenn es das andere tut.
Peter Shor
Aber wie funktioniert die Reduktion zum Beispiel, wenn die Instanz der Teilmenge Summe ist 2,3,5,7 und Zielsumme 8 (Was ist die entsprechende Vektorinstanz)?
Marzio De Biasi
PS Ich habe auch einen Beweis gefunden, dass das Problem NP-vollständig ist, aber es ist viel länger als deins, also versuche ich es zu verstehen ... einfacher ist besser :-)
Marzio De Biasi
Dies bedeutet, dass wir für das zweite Problem das Übertrags-Gadget zu jeder benachbarten Bitposition hinzufügen müssen. In der Tat, da könnten wir habenn-1 trägt in dieser Position, müssen wir hinzufügen n-1Kopien des Carry-Gadgets an diese Bitposition. Und ich habe gerade gemerkt, dass das nicht funktioniert - wir müssen schlauer sein. Ich weiß, wie es geht, aber ich muss die Antwort überarbeiten.
Peter Shor
3

Dies beantwortet die Frage nicht, kann aber einige hilfreiche Beobachtungen enthalten. Ich wollte es nicht als Kommentar formulieren, da ich lange, fragmentierte Kommentare als lästig empfinde

Die Neuformulierung des Problems wie in meinem Kommentar zur Frage ausgeführt:

Eingang: n Vektoren X={x1,,xn} Über {0,1}m, m ist ein Teil der Eingabe

Frage: Gibt es zwei verschiedene Teilmengen? EIN,BX so dass

xEINx=xBx

Vielleicht sollte ich beachten, dass man beachten sollte X,EIN,B als Multisets (die Vektoren dürfen nicht eindeutig sein) und die Summen sind vorbei N.

Ich schlage vor, dieses Problem 2SUBSET-BINARY-VECTOR-SUM zu nennen, da wir nach 2 Teilmengen von Binärvektoren suchen.

Einige Beobachtungen:

  • Ob Xenthält einen Vektor mehrmals die Antwort wird trivial. Lassenxich,xjX und xich=xj. DannEIN={xich},B={xj} arbeitet als Zeuge.

  • Wenn einer der Vektoren in Xenthält nur 0en ist es trivial. Lassen0Xsei dieser Vektor. Dann für jedenEINX{0} es folgt B=EIN{0} ist ein Zeuge.

  • Angenommen, es gibt einen solchen Zeugen EINB. Dies impliziert, dass sich jeder Vektor in befindetB aber nicht in EIN darf nur aus Nullen bestehen.

  • Um die beiden oben genannten Punkte zusammenzufassen: ein Zeuge EIN,B mit EINB existiert, wenn mindestens einer der Vektoren in X enthält nur Nullen

  • Angenommen, es gibt einen Zeugen EIN,B so dass EINB. Sie können die gemeinsamen Elemente in beiden Sätzen entfernen und trotzdem einen korrekten Zeugen haben.

Diese Punkte bedeuten im Wesentlichen, dass Sie nach einer Partition von suchen X in zwei Sätze (EINB=X) oder drei Sätze. Der dritte Satz repräsentiert die Vektoren, die auch nicht ausgewählt wurdenEIN oder B. LassenS(n,k) seien Sie die Stirling-Zahlen der zweiten Art - die Anzahl der Möglichkeiten, eine Menge von zu partitionieren n Objekte in knicht leere Partitionen. Dann gibt esS(n,3)+S(n,2) Mögliche Lösungen, daher ist hier keine rohe Gewalt möglich.

Wenn Sie den Vektoren erlauben, vorbei zu sein Nm(2SUBSET-VECTOR-SUM), dann können wir versuchen, UNIQUE-PARTITION auf dieses Problem zu reduzieren . Lassenm=1und übergeben Sie einfach die Instanz von UNIQUE-PARTITION (wenn sie 0 enthält, entfernen Sie sie zuerst, um triviale Lösungen zu vermeiden). Dies funktioniert jedoch nicht, da mögliche LösungenEIN,B Enthält nicht unbedingt alle Eingabeelemente:

Erwägen {1,2,3,5}. Dies ist aber nicht in EINZIGARTIGER TEILUNGEIN={1,2},B={3}in 2SUBSET-VECTOR-SUM. Vielleicht mitm>1 Wir können die zusätzlichen Vektoreinträge verwenden, um zu erzwingen EIN,B um die Eingabe zu partitionieren.

John D.
quelle