(0,1) problema del vector XOR

8

esta es una reescritura de otra pregunta reciente mía [1] que no se dijo bien (tenía una simplificación semi obvia, mea culpa) pero creo que todavía hay una pregunta no trivial en el fondo. He visto problemas similares en la literatura pero no este en particular.

lo escribirá en términos de vectores de bits porque eso es lo más fácil para mí.

Que haya un conjunto de vectores de bits de tamaño , . Considere la operación XOR bit a bit. dado un vector objetivo . encuentre un subconjunto de vectores de modo que el XOR bit a bit del conjunto sea igual al vector objetivo. ¿Qué es un algoritmo eficiente (o idealmente óptimo) para encontrar un subconjunto? $n$ $v_1, v_2, v_3, ... , v_n$ $v_0$

El algoritmo de fuerza bruta enumera el conjunto de potencias de tamaño enumera el primer subconjunto encontrado. (¿ligeramente?) más eficiente miraría las posiciones 1 en el objetivo y excluiría los subconjuntos que no tienen al menos 1 vector con un 1 en una posición 1 del objetivo. $2^n$

el subconjunto puede o no existir. Puede o no ser único.

preguntas estrechamente relacionadas: (1) encontrar el subconjunto más pequeño, (2) salida T / F dependiendo de si existe dicho subconjunto.

sospecho que uno de estos problemas es NP completo.

buscando referencias, información, etc., sería interesante saber si hay entradas "duras" frente a "fáciles", etc.

como escribí en la otra pregunta, esto parece estar estrechamente relacionado con el problema de la suma de subconjuntos (ver, por ejemplo, garey & johnson ref) que se sabe que es NP completo, pero parece tener una complejidad "ligeramente" menor porque es más simple calcular un vector XOR a nivel de bits que una suma binaria (la suma puede tener más dígitos binarios).

el problema también parece estar estrechamente relacionado con la pregunta reciente de bin fu [2]

[1] /cstheory/10341/building-0-1-vectors-out-of-xors

[2] Problema de vector algorítmico

cc.complexity-theory reference-request circuit-complexity lower-bounds vzn
fuente

2

Este problema es exactamente la pregunta 'es el vector

en el lapso de los vectores

módulo 2? '; si

es linealmente independiente mod 2, entonces todos

son y el problema puede resolverse mediante una inversión de matriz; e incluso si el

no es independiente, debería resolverse fácilmente mediante eliminación gaussiana. El problema del 'subconjunto de satisfacción más pequeño' puede ser NP-completo: esencialmente se pregunta '¿cuál es el vector distinto de cero de menor peso en el intervalo de estos vectores módulo 2?' - Pero aún no soy lo suficientemente consciente como para tener una respuesta precisa a eso.

v_{0}

$v_0$

v_{1} . . v_{n}

$v_1..v_n$

v_{i}

$v_i$

v_{0}

$v_0$

v_{i}

$v_i$

Steven Stadnicki

17

Sea . El problema es determinar si el siguiente sistema tiene una solución: $v_0, v_1, \ldots, v_n \in \mathbb{Z}_2^m$

(\begin{matrix} v_{1} & \dots & v_{n} \end{matrix}) (\begin{matrix} x_{1} \\ ⋮ \\ x_{n} \end{matrix}) = v_{0} (mod 2)

$\begin{pmatrix} v_1 & \cdots & v_n \end{pmatrix} \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} = v_0 \, (\text{mod } 2)$

Este problema es conocido por ser -Complete por [Damm90, BDHM92], por lo tanto dentro de . $\oplus L$ $\text{NC}^2 \subseteq \text{P}$

[Damm90] Carsten Damm: Problemas completo para . Inf. Proceso. Letón. 36 (5): 247-250 (1990) [BDHM92] Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, Christoph Meinel: Estructura e importancia de la clase Logspace-MOD. Teoría de sistemas matemáticos 25 (3): 223-237 (1992) $\oplus L$

Michael Blondin
fuente

12

Como continuación de mi comentario: encontrar el subconjunto satisfactorio más pequeño debería ser NP-completo; la reducción se debe al problema del código de peso mínimo (dada una base para un código sobre GF (2), ¿cuál es el vector de peso mínimo en el código?) y esto fue aparentemente NP-completo en 1997 por A. Vardy: " La intratabilidad de calcular la distancia mínima de un código ", http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=641542

Steven Stadnicki
fuente

Si recuerdo bien, Vardy utiliza una reducción del problema de suma de subconjuntos mínimos sobre campos finitos de la característica 2, que se sabe que es NP-completo y es de hecho equivalente a lo que pregunta OP.

Mahdi Cheraghchi

1

¿Hay algún resultado aproximado para este problema?

Bin Fu

@bin acaba de encontrar esta referencia que considera variantes de aproximación Una reducción determinista para el problema de distancia mínima de brecha Cheng / Wan y cita otras referencias que pueden ser útiles

vzn

(0,1) problema del vector XOR

Respuestas: