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

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 $v_1 \ne v_2$ , so daß $Mv_1 = Mv_2$ (alle Operationen durchgeführt über $\mathbb{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\in \{-1,0,1\}^n$ so dass $Mv=0$ ?

Äquivalent: Wenn Vektoren über , gibt es zwei verschiedene Teilmengen so dass ? $n$ $X=\{x_1,\dots,x_n\}$ $\{0,1\}^m$ $A,B \subseteq X$ $\sum_{x \in A} x = \sum_{x \in B} x$

cc.complexity-theory np-hardness linear-algebra 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

? Und ist dies nicht durch die Bestimmung des Ranges von

gelöst ?

v

$v$

M v = 0

$Mv = 0$

M

$M$

mhum

@mhum nein, es ist äquivalent zu bestimmen, ob es ein von Null verschiedenes

so dass

v \in {- 1, 0, 1}^{n}

$v \in \{-1, 0, 1\}^n$

M v = 0

$Mv = 0$

Sasho Nikolov

Ah. Ich vermisste , dass

musste auch binär sein. Mein Fehler.

v_{i}

$v_i$

mhum

Scheint das Machbarkeitsproblem für die 0/1-Integer-Programmierung zu sein. Liegen Operationen über

oder über

Z

$\mathbb{Z}$

Z_{2}

$\mathbb{Z_2}$

Kaveh

Umformulierung des Problems: Gegeben sind

Vektoren

über

. Gibt es zwei verschiedene Teilmengen

so dass

? 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

n

$n$

X = {x_{1}, \dots, x_{n}}

$X = \{ x_1,\dots,x_n \}$

{0, 1}^{m}

$\{ 0,1 \}^m$

A, B \subseteq X

$A,B \subseteq {X}$

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

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

Z

$\mathbb{Z}$

John D.

Antworten:

Ich verwende die äquivalente Formulierung user17410:

Eingabe: Vektoren über , ist Teil der Eingabe Frage: Gibt es zwei verschiedene Teilmengen so dass $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

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

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 $\leq$ SUBSET SUM PARTITION Gerade-Ungerade - PARTITION EQUAL SUBSET SUM $\leq$ $\leq$ $\leq$

(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 , Vektoren über und ein Zielsummenvektor , entscheiden Sie, ob es existiert , so daß Proof : Direktreduktion von EXACT COVER BY 3-SETS (X3C): ein Satz von gegebenen Elemente $X = \{ x_1, \dots, x_m \}$ $x_i$ $\{0,1\}^n$ $t$ $A \subseteq X$

\sum_{x \in A} x = t

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

n

$n$

und eine Sammlung

von

Y = {y_{1}, . . ., y_{n}}

$Y = \{y_1,...,y_n\}$

C

$C$

m

$m$ drei Elementen Subsets

erstellen wir die entsprechende 0-1 VECTOR SUM-Instanzeinstellung

wenn und nur wenn das Element

;

C = {C_{1}, . . ., C_{m}}

$C = \{C_1,...,C_m\}$

x_{i} [j] = 1

$x_i[j] = 1$

j

$j$

C_{i}

$C_i$

t = [1, 1, . . .1]

$t = [1,1,...1]$

SCHRITT 2 Das Finden von zwei gleichen Summenteilmengen unter 0-1 Vektoren über entspricht dem Finden von zwei gleichen Summenteilmengen von Vektoren mit einem Element der begrenzten Größe mit für festes . $A,B$ $m$ $\{0,1\}^n$ $A,B$ $x_1 ... x_m$ $max\{x_i\} = 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 und die letzten in Untergruppe 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 polynomiell begrenzt sind ). $A$ $A$ $B$ $mn$

Das folgende Problem ist also NP-vollständig.

SCHRITT 3

Das folgende Problem ( 0-1 VECTOR PARTITION ) ist NP-vollständig: Wenn , Vektoren über entscheidet dies, ob in zwei Teilmengen so, dass $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

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

Beweis : Reduktion von 0-1 VEKTORSUMME: gegebenes und der Zielsummenvektor ; sei , addieren wir zu die folgenden Vektoren: und $X = \{ x_1, \dots, x_m \}$ $t$ $S = \sum x_i$ $X$ $b' = -t + 2S$ $b'' = t + S\;$ : . $B = X \cup \{b',b''\}$

( ) Angenommen , dass es existiert , so daß ; wir setzen und ; wir haben $\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''\}$

\sum_{x \in B_{1}} = b^{'} + \sum_{x \in A} x = t - t + S = 2 S

$\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 ∖ A} x = b^{″} + S - \sum_{x \in A} x = 2 S

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

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

- t + 2 S + \sum_{x \in B_{1} ∖ {b^{'}}} x = t + S + \sum_{x \in B_{2} ∖ {b^{″}}} x

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

Wir müssen also und ist eine gültige Lösung für die 0-1-VEKTORSUMME. $\sum_{x \in B_1 \setminus\{b'\}} x = t$ $B_1 \setminus\{b'\}$

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

SCHRITT 3

Das Problem ist noch NP-vollständig , wenn die Vektoren aus nummeriert sind und die beiden Teilmengen müssen gleich groß sein, und wir fordern, dass genau eines von für (also durch die Bedingung gleicher Größe) muss das andere Element des Paares in $x_1,...,x_2n$ $X_1,X_2$ $X_1$ $x_{2i-1},x_{2i}$ $1 \leq i \leq n$ ) enthalten sein (0-1 VECTOR EVEN-ODD PARTITION). $X_2$

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

Aufgrund des -Elements können die Vektoren und 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). $2i$ $x'_{2i-1}$ $x'_{2i}$

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 Vektoren über bilden wir eine Menge von Vektoren über $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}$ 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}

$x_{2m}$ 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

| X_{i} \cap {x_{2 j - 1}, x_{2 j}} | = 1

$|X_i \cap \{x_{2j-1}, x_{2j}\}| = 1$ is required for all

i \in {1, 2}

$i \in \{1, 2\}$ and

1 \leq j \leq m

$1 \leq j \leq m$

Sasho Nikolov

@SashoNikolov: Ja, das meine ich für jedes Paar

(x_{2 i - 1}, x_{2 i})

$(x_{2i-1},x_{2i})$ (und im Beweis

(x_{2 i - 1}^{'}, x_{2 i}^{'})

$(x'_{2i-1}, x'_{2i})$ ) genau eine ist enthalten in

X_{1}

$X_1$ ; Ich werde die Antwort bearbeiten

Marzio De Biasi

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 von $m$ Ganzzahlen 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 $n$ trä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. $\ldots$ , 2 $^{\lfloor \log n \rfloor}$ . 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 tragen $n$ . 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

$2,3,5,7$ und Zielsumme

8

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

n - 1

$n-1$ trägt in dieser Position, müssen wir hinzufügen

n - 1

$n-1$ Kopien 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

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 = \{ x_1, \dots, x_n \}$ Über $\{0,1\}^m$ , $m$ ist ein Teil der Eingabe

Frage: Gibt es zwei verschiedene Teilmengen? $A,B \subseteq X$ so dass

\sum_{x \in EIN} x = \sum_{x \in B} x

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

Vielleicht sollte ich beachten, dass man beachten sollte $X,A,B$ als Multisets (die Vektoren dürfen nicht eindeutig sein) und die Summen sind vorbei $\mathbb{N}$ .

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

Einige Beobachtungen:

Ob $X$ enthält einen Vektor mehrmals die Antwort wird trivial. Lassen $x_i,x_j \in X$ und $x_i = x_j$ . Dann $A = \{x_i\}, B = \{x_j\}$ arbeitet als Zeuge.
Wenn einer der Vektoren in $X$ enthält nur 0en ist es trivial. Lassen $0 \in X$ sei dieser Vektor. Dann für jeden $A \subseteq X \setminus \{ 0 \}$ es folgt $B = A \cup \{ 0 \}$ ist ein Zeuge.
Angenommen, es gibt einen solchen Zeugen $A \subset B$ . Dies impliziert, dass sich jeder Vektor in befindet $B$ aber nicht in $A$ darf nur aus Nullen bestehen.
Um die beiden oben genannten Punkte zusammenzufassen: ein Zeuge $A,B$ mit $A \subset B$ existiert, wenn mindestens einer der Vektoren in $X$ enthält nur Nullen
Angenommen, es gibt einen Zeugen $A,B$ so dass $A \cap B \neq \emptyset$ . 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 ( $A \cup B = X$ ) oder drei Sätze. Der dritte Satz repräsentiert die Vektoren, die auch nicht ausgewählt wurden $A$ oder $B$ . Lassen $S(n,k)$ seien Sie die Stirling-Zahlen der zweiten Art - die Anzahl der Möglichkeiten, eine Menge von zu partitionieren $n$ Objekte in $k$ nicht leere Partitionen. Dann gibt es $S(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 $\mathbb{N}^m$ (2SUBSET-VECTOR-SUM), dann können wir versuchen, UNIQUE-PARTITION auf dieses Problem zu reduzieren . Lassen $m=1$ und ü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ösungen $A,B$ Enthält nicht unbedingt alle Eingabeelemente:

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

John D.
quelle