Decida se o kernel de uma matriz contém um vetor diferente de zero, cujas entradas são -1, 0 ou 1

Dado um por matriz binária (as entradas são ou ), o problema é determinar se existem dois vetores binários tais que (todas as operações executadas em ). Este problema é NP-difícil? $m$ $n$ $M$ $0$ $1$ $v_1 \ne v_2$ $Mv_1 = Mv_2$ $\mathbb{Z}$

Está claramente em NP, pois você pode dar dois vetores como testemunhas.

Equivalentemente: Dado , existe um vetor diferente de zero tal que ? $M$ $v\in \{-1,0,1\}^n$ $Mv=0$

Equivalentemente: dados vetores acima de , existem dois subconjuntos diferentes tais que ? $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
fonte

A menos que eu entenda mal a pergunta, isso não equivale a determinar se existe um diferente de zero, tal que ? E isso não é resolvido determinando a classificação de ?

v

$v$

M v = 0

$Mv = 0$

M

$M$

Mhum

@ hum não, é equivalente a determinar se existe um diferente de zero tal que .

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

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

M v = 0

$Mv = 0$

Sasho Nikolov

que

v_{i}

$v_i$ também tinha que ser binário. Meu erro.

Mhum

Parece o problema de viabilidade para a programação 0/1-Integer. As operações estão acima de

Z

$\mathbb{Z}$ ou acima de

Z_{2}

$\mathbb{Z_2}$ ?

Kaveh

Reformulação do problema: Dados

n

$n$ vetores

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

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

{0, 1}^{m}

$\{ 0,1 \}^m$ . Existem dois subconjuntos diferentes

A, B \subseteq X

$A,B \subseteq {X}$ modo que

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

$\sum_{x \in A} x = \sum_{x \in B} x$ ? Eu acho que é mais provável que seja NP-hard se os montantes não são tomadas modulo dois, que é operações estão sobre

Z

$\mathbb{Z}$

John D.

Respostas:

Eu uso a formulação equivalente user17410:

Entrada: vetores over , faz parte da entrada Pergunta: Existem dois subconjuntos diferentes tais que $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$

A prova de dureza envolve muitas reduções intermediárias que seguem a mesma "cadeia" usada para provar a dureza do problema padrão EQUAL SUBSET SUM:

X3C SUBSET SUM PARTITION par-ímpar PARTITION EQUAL SUBSET SUM $\leq$ $\leq$ $\leq$ $\leq$

(Ainda estou verificando para que possa estar errado :)

PASSO 1

O seguinte problema ( 0-1 VETOR SUBSET SUM ) é NP-complete: dado , vetores sobre e um vetor de soma alvo , decida se houver tal que Prova : Redução direta da TAMPA EXATA POR 3 SETS (X3C): dado um conjunto de elementos e uma coleção de três subconjuntos de elementos criamos a configuração de instância 0-1 VECTOR SUM correspondente se e somente se o elemento $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$

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$ está incluído no ; .

C_{i}

$C_i$

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

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

PASSO 2 Encontrar dois subconjuntos de somas iguais entre 0-1 vetores acima de , é equivalente a encontrar dois subconjuntos de somas iguais de vetores com elemento de tamanho delimitado onde para fixo . $A,B$ $m$ $\{0,1\}^n$ $A,B$ $x_1 ... x_m$ $max\{x_i\} = O((mn)^k)$ $k$

Por exemplo, o conjunto de vetores:

x1 2 1 0 1
x2 1 2 3 1

É equivalente aos vetores 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

Informalmente, os vetores 0-1 são agrupados (se você selecionar um vetor do grupo x2 e adicioná-lo ao subconjunto , será forçado a incluir em os outros dois e colocar o último no subconjunto ) e as somas serão feitas em unário (esta é a razão pela qual os vetores não binários correspondentes devem conter elementos que são polinomialmente limitados em relação a ). $A$ $A$ $B$ $mn$

Portanto, o seguinte problema é NP-completo.

ETAPA 3

O seguinte problema ( 0-1 PARCÇÃO DO VETOR ) é NP-completo: dado , vetores sobre decidem se pode ser particionado em dois subconjuntos modo que $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''\}$

( ) Suponha que exista tal que ; definimos e ; temos $\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$

( ) Suponha que e tenham soma igual. não podem pertencer ao mesmo conjunto (caso contrário, sua soma é e não podem ser "equilibrados" pelos elementos do outro conjunto). Suponha que ; temos: $\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$

Por isso temos de ter e é uma solução válida para o 0-1 VETOR SUM. $\sum_{x \in B_1 \setminus\{b'\}} x = t$ $B_1 \setminus\{b'\}$

Nós permitimos apenas 0-1 vetores no conjunto ; portanto, os vetores devem ser "representados em unário", como mostrado na ETAPA 2. $B$ $b', b''$

ETAPA 3

O problema ainda é NP-completo se os vetores são numerados de e os dois subconjuntos devem ter tamanho igual e exigimos que contenha exatamente um de para (portanto, pela restrição de tamanho igual, o outro elemento do par deve ser incluído em ) ( 0-1 PARTIÇÃO MESMO DE VETOR DO VETOR ). $x_1,...,x_2n$ $X_1,X_2$ $X_1$ $x_{2i-1},x_{2i}$ $1 \leq i \leq n$ $X_2$

Prova:: A redução é de 0-1 PARTIÇÃO DE VETOR e é semelhante à redução de PARTIÇÃO para PARTIÇÃO MESMO. Se são vectores sobre substitua cada vector com dois vectores de mais de : $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

Devido ao elemento , os vetores e não podem estar contidos no mesmo subconjunto; e uma solução válida para a PARTIÇÃO MESMO VECTOR 0-1 VETOR corresponde a uma solução válida da PARTIÇÃO VETORIAL 0-1 original (basta escolher os elementos 2m + 1..2m + n de cada vetor da solução descartando vetores que contenham todos zeros nessas posições). $2i$ $x'_{2i-1}$ $x'_{2i}$

PASSO 4

Soma de subconjunto igual a 0-1 de VETOR (o problema na questão) é NP-completa: redução de PARTIÇÃO MÉDIA DE VETOR DE 0-1 semelhante à redução de PARTIÇÃO MÉDIA DE VETOR A PARTIDO DE SOMA IGUAL, como provado em Gerhard J. Woeginger , Zhongliang Yu, No problema de soma de subconjuntos iguais : dado um conjunto ordenado de vetores acima de , construímos um defina de vetores sobre . $A = \{x_1,...,x_{2m}\}$ $2m$ $\{0,1\}^n$ $Y$ $3m$ $\{0,1\}^{2m+n}$

Para cada vetor , construímos um vetor sobre desta maneira: $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}

Para cada vetor , construímos um vetor sobre desta maneira: $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}

elemento para $x_{2m}$

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

Finalmente, adicionamos elementos fictícios: $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

Observe novamente que vetores contendo valores podem ser representados em "unário" usando um grupo de 0-1 vetores, como mostrado no PASSO 2. $> 1$

$Y$ tem dois subconjuntos disjuntos com soma igual se e somente se tiver uma partição ímpar. $Y_1,Y_2$ $X$

Marzio De Biasi
fonte

o que você chama de partição vetorial 0-1 equivale ao problema de determinar se um sistema definido tem discrepância 0. isso é NP difícil, pois captura, por exemplo, o problema de divisão de 2-2 conjuntos, veja thm 9 neste artigo por guruswami cs.cmu.edu/~venkatg/pubs/papers/ss-jl.ps ; o meu papel tem um pouco mais sobre a dureza de discrepância paul.rutgers.edu/~anikolov/Files/charikarM.pdf

Sasho Nikolov

Também acredito que você deturpa o problema da partição ímpar. se não houver dois vetores consecutivos no mesmo conjunto, o problema é trivial. eu acredito que você quer dizer que é necessário para todos os e

| 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

@ShohoNikolov: sim, quero dizer que para cada par (e na prova ) exatamente um é incluído em ; Vou editar a resposta

(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

EDIT: Minha prova original teve um bug. Agora acredito que está consertado.

Reduzimos o problema de EQUAL SUM SUBSETS para esse problema. EQUAL SUM SUBSETS é o problema de: dado um conjunto de números inteiros, encontre dois subconjuntos separados que tenham a mesma soma. Sabe-se que IGUAL SUM SUBSETS é completo em NP. $m$

Suponha que essas cadeias de bits não fossem vetores, mas representações de números de bits em binário. Em seguida, o problema seria NP-completo com uma redução de EQUAL SUM SUBSETS. Vou mostrar como fazer com que esses vetores se comportem como se fossem números binários. O que precisamos é ser capaz de fazer carrega; isto é, para cada par de coordenadas adjacentes, precisamos ser capazes de substituir o vetor ..02 .. por ..10 ... $n$

Como podemos fazer isso? Precisamos de um gadget que nos permita fazer isso. Em particular, precisamos de dois subconjuntos cujas somas são 0,02 .. x e ..10 .. x, em que x é uma string de bits usando novas coordenadas (isto é, coordenadas que não são nenhuma das coordenadas que compõem o binário). representações) e onde existe apenas uma maneira de criar dois subconjuntos com a mesma soma nas novas posições de bits correspondentes a x. $n$

Isso é bastante fácil de fazer. Para cada par de posições de bits adjacentes, adicione três vetores da seguinte forma. Aqui, os dois últimos bits são coordenadas que são diferentes de zero apenas nesses três vetores, e todo bit não explicitamente indicado abaixo é 0.

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

Deixe-me fazer um exemplo. Queremos mostrar como 5 + 3 = 8 funciona.

Aqui está 8 = 5 + 3 em binário:

1000

0101
0011

Essas cadeias de bits fornecem a mesma soma em binário, mas não na adição de vetor.

Agora, temos carregamentos nos lugares 1, 2, 4, portanto, precisamos adicionar três conjuntos de três vetores à equação para executar esses carregamentos.

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

Esses conjuntos agora têm a mesma soma na adição de vetores. As somas são:

1222 11 11 11

em ambos os casos.

Essa construção funciona bem se houver apenas um transporte por posição, mas pode haver potencialmente carregamentos por posição, e você precisa garantir que sua construção possa suportar até carregamentos e que os diferentes carregamentos não interfiram um com o outro. Por exemplo, se você adicionou dois conjuntos diferentes de três vetores para o mesmo par de posições adjacentes (que é o que propus na minha prova original): $n$ $n$

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

você tem o problema de obter dois conjuntos diferentes de vetores, dando a mesma soma:

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

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

Como consertar isto? Adicione um conjunto de vetores que permite transportar 1, um conjunto que permite transportar 2 e um conjunto para 4, 8, , 2 . Não vou detalhar os detalhes dessa construção agora, mas deve ser bem direto. Como cada número tem uma representação binária exclusiva, isso permitirá que você carregue qualquer número até . Para transportar 4, por exemplo, você precisa encontrar quatro vetores com a mesma soma que dois vetores e para os quais essa é a única relação linear entre os dois conjuntos. Por exemplo, o conjunto $\ldots$ $^{\lfloor \log n \rfloor}$ $n$

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

trabalho. Você pode verificar facilmente se a relação

11000
00100
00010
00001

10001
01110

é a única relação possível entre esses seis vetores, porque a matriz formada por essas seis linhas tem classificação 5.

Peter Shor
fonte

Um esclarecimento, você diz: "Agora, nós carregamos nos 1, 2, 4 lugares"; mas no problema não sabemos quais vetores são selecionados, portanto, devemos adicionar o gadget de transporte a cada posição de bit adjacente? E na primeira lista do exemplo há 7 vetores, está correto?

Marzio De Biasi

Suponha que tenha uma solução para o problema da soma do subconjunto. Ou seja: temos 3 + 5 = 8. Agora, podemos olhar para o complemento nesta testemunha e descobrir onde estão os carregamentos. Isso nos dá a solução para o problema de adição de vetores. Um problema tem uma solução se e somente se o outro tiver.

Peter Shor

Mas como a redução funciona, por exemplo, se a instância da soma do subconjunto for

e a soma alvo

(qual é a instância do vetor correspondente)?

2, 3, 5, 7

$2,3,5,7$

8

$8$

Marzio De Biasi

PS: Eu também encontrei uma prova de que o problema é NP-completo, mas é muito mais longo que o seu, por isso estou tentando entendê-lo ... mais simples é melhor :-)

Marzio De Biasi

Isso significa que, para o segundo problema, precisamos adicionar o gadget de transporte a todas as posições de bits adjacentes. De fato, como podemos ter

carrega nessa posição, temos que adicionar

cópias do gadget para transportar nessa posição de bit. E acabei de perceber que isso não funciona - temos que ser mais espertos. Eu sei como fazê-lo, mas vou ter que revisar a resposta.

n - 1

$n-1$

n - 1

$n-1$

Peter Shor

Isso não responde à pergunta, mas pode conter algumas observações úteis. Eu não queria colocá-lo como um comentário, porque acho comentários longos e fragmentados incomodantes de ler

A reformulação do problema, como indicado no meu comentário à pergunta:

$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

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

$X,A,B$ $\mathbb{N}$

Proponho chamar esse problema de 2SUBSET-BINARY-VECTOR-SUM devido ao fato de estarmos procurando por 2 subconjuntos de vetores binários.

Algumas observações:

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

$X$ $A \cup B = X$ $A$ $B$ $S(n,k)$ $n$ $k$ $S(n,3)+S(n,2)$ soluções possíveis, então a força bruta não é viável aqui.

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

$\{1,2,3,5\}$ $A=\{1,2\} , B = \{3\}$ $m>1$ $A,B$

John D.
fonte