Zdecyduj, czy jądro macierzy zawiera jakiś niezerowy wektor, którego wszystkie wpisy to -1, 0 lub 1

Biorąc pod uwagę $m$ o $n$ binarnego macierzy $M$ (wartość wynosi $0$ lub $1$ ), problemem jest ustalenie, czy istnieje dwoma wektorami binarnymi $v_1 \ne v_2$ w taki sposób, $Mv_1 = Mv_2$ (wszystkie operacje wykonywane przez $\mathbb{Z}$ ). Czy ten problem jest trudny NP?

Widać to wyraźnie w NP, ponieważ możesz podać dwa wektory jako świadków.

Równoważnie: Biorąc pod uwagę $M$ , czy istnieje niezerowy wektor $v\in \{-1,0,1\}^n$ taki, że $Mv=0$ ?

Równoważnie: Biorąc pod uwagę $n$ wektorów $X=\{x_1,\dots,x_n\}$ powyżej $\{0,1\}^m$ , czy istnieją dwa różne podzbiory $A,B \subseteq X$ takie, że $\sum_{x \in A} x = \sum_{x \in B} x$ ?

cc.complexity-theory np-hardness linear-algebra Mohammad Al-Turkistany
źródło

O ile nie zrozumiem źle pytania, czy nie jest to równoznaczne z ustaleniem, czy istnieje niezerowe

v

$v$ takie, że

M v = 0

$Mv = 0$ ? I czy nie można tego rozwiązać poprzez określenie rangi

M

$M$ ?

mhum,

@ mhum nie, jest to równoważne z ustaleniem, czy istnieje niezerowa

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

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

M v = 0

$Mv = 0$ .

Sasho Nikolov,

Ach Brakowało mi tego

v_{i}

$v_i$ również musiały być binarny. Mój błąd.

mhum,

Wydaje się, że jest to problem wykonalności dla programowania w liczbach całkowitych 0/1. Czy operacje przekraczają

Z

$\mathbb{Z}$ czy przekraczają

Z_{2}

$\mathbb{Z_2}$ ?

Kaveh,

Przeformułowanie problemu: Biorąc pod uwagę

n

$n$ wektorów

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

$X = \{ x_1,\dots,x_n \}$ powyżej

{0, 1}^{m}

$\{ 0,1 \}^m$ . Czy istnieją dwa różne podzestawy

A, B \subseteq X

$A,B \subseteq {X}$ takie, że

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

$\sum_{x \in A} x = \sum_{x \in B} x$ ? Sądzę, że bardziej prawdopodobne jest, że NP-trudne, jeśli sumy nie zostaną pobrane modulo dwa, to znaczy operacje są zakończone

Z

$\mathbb{Z}$

John D.

Odpowiedzi:

Używam równoważnego sformułowania user17410:

Dane wejściowe: wektorów powyżej , jest częścią danych wejściowych Pytanie: Czy istnieją dwa różne podzbiory takie, że $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$

Dowód twardości obejmuje wiele pośrednich redukcji, które następują po tym samym „łańcuchu”, który został użyty do udowodnienia twardości standardowego problemu EQUAL SUBSET SUM:

X3C podzbiór SUM PODZIAŁU parzyste-nieparzyste PODZIAŁU EQUAL SUBSET SUM $\leq$ $\leq$ $\leq$ $\leq$

(Nadal go sprawdzam, więc może być źle :)

KROK 1

Następujący problem ( 0-1 VECTOR SUBSET SUM ) jest NP-zupełny: biorąc pod uwagę , wektory powyżej oraz wektor sumy docelowej , zdecyduj, czy istnieje taki, że Dowód : Bezpośrednia redukcja z DOKŁADNEGO POKRYCIA PRZEZ 3-ZESTAWY (X3C): biorąc pod uwagę zestaw elementów $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$

oraz zbiór

trzy elementy subsets

budujemy odpowiednie ustawienie instancji SUMA WEKTORU 0-1

wtedy i tylko wtedy, gdy element

jest zawarty w

;

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

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

C

$C$

m

$m$

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

KROK 2 Znalezienie dwóch podzbiorów równej sumie wśród wektorów 0-1 powyżej , jest równoważne znalezieniu dwóch podzbiorów wektorów o równej sumie z elementem o ograniczonej wielkości gdzie dla ustalonego . $A,B$ $m$ $\{0,1\}^n$ $A,B$ $x_1 ... x_m$ $max\{x_i\} = O((mn)^k)$ $k$

Na przykład zestaw wektorów:

x1 2 1 0 1
x2 1 2 3 1

Jest równoważny wektorom 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

$A$ $A$ $B$ $mn$

Zatem następujący problem jest NP-zupełny.

KROK 3

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

$X = \{ x_1, \dots, x_m \}$ $t$ $S = \sum x_i$ $X$ $b' = -t + 2S$ $b'' = t + S\;$ $B = X \cup \{b',b''\}$

( ) Załóżmy, że istnieje taki, że ; ustawiamy i ; mamy $\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$

( ) Załóżmy, że i mają równą sumę. nie mogą należeć do tego samego zestawu (w przeciwnym razie ich suma wynosi i nie może być „zrównoważona” przez elementy w innym zestawie). Załóżmy, że ; mamy: $\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$

Dlatego musimy mieć a jest prawidłowym rozwiązaniem dla SUMY WEKTOROWEJ 0-1. $\sum_{x \in B_1 \setminus\{b'\}} x = t$ $B_1 \setminus\{b'\}$

Dopuszczamy tylko wektory 0-1 w zbiorze , więc wektory muszą być „reprezentowane w jedności”, jak pokazano w KROKU 2. $B$ $b', b''$

KROK 3

Problem jest nadal NP-zupełny, jeśli wektory są ponumerowane od a dwa podzbiory muszą mieć taki sam rozmiar i wymagamy, aby zawierał dokładnie jeden z dla (więc, przez ograniczenie równości wielkości, drugi element pary musi być zawarty w ) ( 0-1 WEKTOR NAWET ODDY ). $x_1,...,x_2n$ $X_1,X_2$ $X_1$ $x_{2i-1},x_{2i}$ $1 \leq i \leq n$ $X_2$

Dowód:: Zmniejszenie wynosi od 0 do 1 WEKTORA i jest podobne do zmniejszenia z PARTYCJI do EVEN-ODD PARTITION. Jeśli to wektorów powyżej zamień każdy wektor na dwa wektory powyżej : $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

Z powodu elementu wektory i nie mogą być zawarte w tym samym podzbiorze; prawidłowe rozwiązanie partycji 0-1 VECTOR EVEN-ODD odpowiada prawidłowemu rozwiązaniu oryginalnej partycji 0-1 VECTOR (wystarczy wybrać elementy 2m + 1..2m + n każdego wektora rozwiązania odrzucając wektory, które zawierają wszystkie zera w tych pozycjach). $2i$ $x'_{2i-1}$ $x'_{2i}$

KROK 4

PODSUMOWANIE 0-1 WEKTORÓW RÓWNEGO PODSTAWY (problem w pytaniu) jest NP-całkowite: redukcja z 0-1 WEKTORA NAWET ODRZUTU podobna do redukcji z EVEN-ODD PODZIAŁU na PODSTAWA RÓWNEJ PODSTAWY , jak udowodnił Gerhard J. Woeginger , Zhongliang Yu, W sprawie problemu równej sumy częściowej : biorąc pod uwagę uporządkowany zestaw z wektorów powyżej , budujemy ustaw z wektorów na . $A = \{x_1,...,x_{2m}\}$ $2m$ $\{0,1\}^n$ $Y$ $3m$ $\{0,1\}^{2m+n}$

Dla każdego wektora budujemy wektor nad w ten sposób: $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}

Dla każdego wektora budujemy wektor na w ten sposób: $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}

element na $x_{2m}$

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

Na koniec dodajemy elementów pozornych: $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

Zauważ jeszcze raz, że wektory zawierające wartości mogą być reprezentowane w „jedności” przy użyciu grupy wektorów 0-1, jak pokazano w KROKU 2. $> 1$

$Y$ ma dwa rozłączne podzbiory mają jednakową sumę wtedy i tylko wtedy, gdy ma nieparzystą partycję. $Y_1,Y_2$ $X$

Marzio De Biasi
źródło

to, co nazywacie partycją wektorową 0-1, jest równoznaczne z problemem ustalenia, czy system zestawu ma rozbieżność 0. jest to NP trudne, ponieważ wychwytuje np. problem podziału 2-2 zestawów, patrz thm 9 w tym artykule guruswami cs.cmu.edu/~venkatg/pubs/papers/ss-jl.ps ; mój artykuł ma trochę więcej na temat twardości rozbieżności paul.rutgers.edu/~anikolov/Files/charikarM.pdf

Sasho Nikolov

również uważam, że źle określiłeś problem dotyczący nieparzystej partycji. jeśli nie ma dwóch kolejnych wektorów w tym samym zestawie, problem jest trywialny. uważam, że masz na myśli, że jest wymagane dla wszystkich i

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

$|X_i \cap \{x_{2j-1}, x_{2j}\}| = 1$

i \in {1, 2}

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

1 \leq j \leq m

$1 \leq j \leq m$

Sasho Nikolov

@SashoNikolov: tak, mam na myśli, że dla każdej pary (i na dowód ) dokładnie jedna to zawarty w ; Zmienię odpowiedź

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

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

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

$(x'_{2i-1}, x'_{2i})$

X_{1}

$X_1$

Marzio De Biasi,

EDYCJA: Mój oryginalny dowód miał błąd. Teraz wierzę, że to naprawiono.

Zmniejszamy problem EQUAL SUM SUBSETS do tego problemu. EQUAL SUM podzbiorów jest problem: biorąc pod uwagę zestaw liczb całkowitych, znaleźć dwa rozłączne podzbiory, które mają taką samą sumę. Wiadomo, że EQUAL SUM SUBSETS to NP-complete. $m$

Załóżmy, że te ciągi bitów nie były wektorami, lecz reprezentacjami liczb bitowych w systemie binarnym. Wtedy problem byłby NP-zupełny poprzez redukcję z PODSETÓW EQUAL SUM. Pokażę, jak sprawić, by te wektory zachowywały się jak liczby binarne. To, czego potrzebujemy, to móc wykonywać przewozy; to znaczy, dla każdej pary sąsiednich współrzędnych, musimy być w stanie zastąpić wektor ..02 .. przez ..10 ... $n$

Jak możemy to zrobić? Potrzebujemy gadżetu, który pozwoli nam to zrobić. W szczególności potrzebujemy dwóch podzbiorów, których sumy wynoszą 0,02 .. x i ..10 .. x, gdzie x jest łańcuchem bitowym używającym nowych współrzędnych (tj. Współrzędnych, które nie są żadnymi z współrzędnych tworzących układ binarny) reprezentacje) i gdzie istnieje tylko jeden sposób na utworzenie dwóch podzbiorów o tej samej sumie w nowych pozycjach bitów odpowiadających x. $n$

Jest to dość łatwe do zrobienia. Dla każdej pary sąsiednich pozycji bitów dodaj trzy wektory o następującej formie. Ostatnie dwa bity to współrzędne, które są niezerowe tylko w tych trzech wektorach, a każdy bit, który nie został wyraźnie podany poniżej, wynosi 0.

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

Pozwól mi zrobić przykład. Chcemy pokazać, jak działa 5 + 3 = 8.

Oto 8 = 5 + 3 w systemie binarnym:

1000

0101
0011

Te ciągi bitów dają tę samą sumę w postaci binarnej, ale nie w dodatku wektorowym.

Teraz mamy przeniesienia w 1, 2, 4 miejscach, więc musimy dodać trzy równania trzech wektorów do równania, aby wykonać te przeniesienia.

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

Te zestawy mają teraz tę samą sumę w dodawaniu wektora. Sumy są następujące:

1222 11 11 11

w obu przypadkach.

Ta konstrukcja działa świetnie, jeśli istnieje tylko jedna opcja przenoszenia na pozycję, ale potencjalnie może istnieć do przeniesień na pozycję, i musisz upewnić się, że twoja konstrukcja może obsłużyć do przeniesień i że różne przeniesienia nie przeszkadzają ze sobą. Na przykład, jeśli dodałeś dwa różne zestawy trzech wektorów dla tej samej pary sąsiednich pozycji (co zaproponowałem w moim oryginalnym dowodzie): $n$ $n$

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

masz problem polegający na tym, że otrzymujesz dwa różne zestawy wektorów, które dają tę samą sumę:

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

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

Jak to naprawić? Dodaj jeden zestaw wektorów, który pozwala przenosić 1, jeden zestaw, który pozwala przenosić 2, i jeden zestaw dla 4, 8, , 2 . Nie zamierzam teraz opracowywać szczegółów tej konstrukcji, ale powinna być dość prosta. Ponieważ każda liczba ma unikalną reprezentację binarną, pozwoli to przenieść dowolną liczbę do . Na przykład do przenoszenia 4 potrzebujesz czterech wektorów, które mają taką samą sumę jak dwa wektory i dla których jest to jedyna relacja liniowa między tymi dwoma zbiorami. Na przykład zestaw $\ldots$ $^{\lfloor \log n \rfloor}$ $n$

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

Prace. Możesz łatwo sprawdzić, czy relacja

11000
00100
00010
00001

10001
01110

jest jedyną możliwą relacją między tymi sześcioma wektorami, ponieważ macierz utworzona przez te sześć rzędów ma rangę 5.

Peter Shor
źródło

Wyjaśnienie, mówisz: „Teraz mamy 1, 2, 4 miejsca”; ale w problemie nie wiemy, które wektory są wybrane, więc musimy dodać gadżet przenoszenia do każdej sąsiedniej pozycji bitu? I na pierwszej liście przykładu jest 7 wektorów, czy to prawda?

Marzio De Biasi,

Załóżmy, że mamy rozwiązanie problemu sumy podzbiorów. To znaczy: mamy 3 + 5 = 8. Teraz możemy spojrzeć na dodatek w tym świadku i dowiedzieć się, gdzie są nosiciele. To daje nam rozwiązanie problemu dodawania wektora. Jeden problem ma rozwiązanie wtedy i tylko wtedy, gdy drugi ma.

Peter Shor,

Ale jak działa redukcja, na przykład, jeśli wystąpienie sumy podzbioru wynosi a docelowa suma (jaka jest odpowiednia instancja wektora)?

2, 3, 5, 7

$2,3,5,7$

8

$8$

Marzio De Biasi,

PS Znalazłem również dowód na to, że problem jest NP-zupełny, ale jest znacznie dłuższy niż twój, więc staram się go zrozumieć ... prościej, lepiej :-)

Marzio De Biasi

Oznacza to, że w przypadku drugiego problemu musimy dodać gadżet przenoszenia do każdej sąsiedniej pozycji bitu. W rzeczywistości, ponieważ możemy mieć przeniesienia w tej pozycji, musimy dodać kopii gadżetu przenoszenia do tej pozycji bitowej. I właśnie zdałem sobie sprawę, że to nie działa - musimy być mądrzejsi. Wiem, jak to zrobić, ale będę musiał zmienić odpowiedź.

n - 1

$n-1$

n - 1

$n-1$

Peter Shor,

To nie odpowiada na pytanie, ale może zawierać przydatne spostrzeżenia. Nie chciałem tego traktować jako komentarza, ponieważ długie, fragmentaryczne komentarze sprawiają mi kłopot

Przeformułowanie problemu, jak stwierdzono w moim komentarzu do pytania:

Dane wejściowe: wektorów powyżej , jest częścią danych wejściowych $n$ $X = \{ x_1, \dots, x_n \}$ $\{0,1\}^m$ $m$

Pytanie: Czy istnieją dwa różne podzbiory takie, że $A,B \subseteq X$

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

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

Może powinienem zauważyć, że należy traktować jako multisety (wektory nie mogą być unikalne), a sumy przekraczają . $X,A,B$ $\mathbb{N}$

Proponuję nazwać ten problem 2SUBSET-BINARY-VECTOR-SUM, ponieważ szukamy 2 podzbiorów wektorów binarnych.

Niektóre spostrzeżenia:

Jeśli zawiera jeden wektor wiele razy, odpowiedź staje się banalna. Niech a . Wtedy działa jako świadek. $X$ $x_i,x_j \in X$ $x_i = x_j$ $A = \{x_i\}, B = \{x_j\}$
Jeśli jeden z wektorów w zawiera tylko 0, jest to banalne. Niech będzie tym wektorem. Następnie dla każdego następuje jest świadkiem. $X$ $0 \in X$ $A \subseteq X \setminus \{ 0 \}$ $B = A \cup \{ 0 \}$
Załóżmy, że istnieje świadkiem taki sposób, że . Oznacza to, że każdy wektor w ale nie w musi składać się wyłącznie z zer. $A \subset B$ $B$ $A$
Aby zaliczyć powyższe dwa punkty: istnieje świadek z , jeśli przynajmniej jeden z wektorów w zawiera tylko zera $A,B$ $A \subset B$ $X$
Załóżmy, że istnieje świadek taki, że . Możesz usunąć wspólne elementy z obu zestawów i nadal mieć poprawnego świadka. $A,B$ $A \cap B \neq \emptyset$

Punkty te zasadniczo oznaczają, że szukasz podziału na dwa zestawy ( ) lub trzy zestawy. Trzeci zestaw przedstawia wektory, które nie zostały Choosen zarówno dla lub . Niech będzie liczbą Stirlinga drugiego rodzaju - liczbą sposobów podziału zestawu obiektów na niepustych partycji. Są też możliwe rozwiązania , więc brutalna siła nie jest tutaj możliwa. $X$ $A \cup B = X$ $A$ $B$ $S(n,k)$ $n$ $k$ $S(n,3)+S(n,2)$

Jeśli pozwolisz, aby wektory się skończyły (2SUBSET-VECTOR-SUM), możemy spróbować zmniejszyć UNIQUE-PARTITION do tego problemu. Niech i po prostu przekaż instancję UNIQUE-PARTITION (jeśli zawiera 0, usuń ją najpierw, aby uniknąć trywialnych rozwiązań). Nie działa to jednak, ponieważ możliwe rozwiązania niekoniecznie zawierają wszystkie elementy wejściowe: $\mathbb{N}^m$ $m=1$ $A,B$

Zastanów się . To nie jest w UNIQUE-PARTITION, ale w 2SUBSET-VECTOR-SUM. Może za pomocą możemy użyć dodatkowych wpisów wektorowych, aby zmusić do podzielenia wejścia. $\{1,2,3,5\}$ $A=\{1,2\} , B = \{3\}$ $m>1$ $A,B$

John D.
źródło