Si se relaja la pregunta para preguntar la distancia de reducción de filas de matrices arbitrarias sobre $\mathbb{F}_2$ entonces se puede demostrar que el problema es $NP$ -Completo. Es decir, considere
RRD (Distancia de reducción de filas):
Entrada: $m\times n$ matrices $M$ , $N$ en $\mathbb{F}_2$ y un número entero $k$
Salida: Si $M$ pueden ser reductores de filas a $N$ en $\le k$ pasos
La afirmación es que este problema RRD es $NP$ -completa. Está dentro de $NP$ por lo que la dureza es todo lo que queda. Para ello, considere el siguiente problema relacionado.
MHW (Peso Hamming mínimo):
Entrada: $P\in\mathbb{F}_2^{m\times > n}$ , $b\in\mathbb{F}_2^n$ , entero $k$
Salida: Es $b$ expresable como una combinación lineal de $\le k$ filas de $P$ .
Primero mostraré que MHW se reduce a RRD, luego mostraré que RRD es $NP$ -duro. Esto demostrará que RRD es NP-difícil.
Sea $(P,b,k)$ sea una instancia de MHW. Crear $M$ y $N$ como $(m+1)\times n$ matrices, donde $M$ es sólo $P$ con la fila cero añadida, y $N$ es sólo $P$ con la fila $b$ añadido el. Ahora mostraré que $b$ es expresable como una combinación lineal de como máximo $k$ filas de $P$ si $M$ es reducible en filas a $N$ como máximo $k$ pasos.
El sentido directo de esta afirmación es sencillo. Pasemos ahora a la dirección inversa. Las operaciones de reducción de filas sobre $\mathbb{F}_2$ son simplemente "añade esta fila a aquella", o "intercambia esta y aquella fila". De ello se deduce que en $\le k$ las reducciones de filas tienen como máximo $k$ filas "origen" de donde proceden las adiciones. Así, la última fila de $N$ es igual a la última fila de $M$ (que es cero) más como máximo $k$ otras filas de $M$ . Esto es exactamente lo que se quería, ya que la última fila de $M$ es sólo $b$ .
Esto completa la prueba de que MHW se reduce a RRD.
Ahora vamos a demostrar que MHW es NP-difícil. Lo haremos con:
SET-COVER
Entrada: Establece $S_1,\ldots,S_m\subseteq[n]$ , entero $k$ ,
Ouptut: Decidir si $[n]$ es la unión de $\le k$ de los conjuntos $S_i$
Se sabe que Set-Cover es NP-completo. Aquí necesitamos una versión ligeramente más fuerte de este hecho, donde todos los conjuntos son de tamaño constante, y esto sigue siendo NP-completo. (Para ver esto, primero se demuestra que 3SAT sigue siendo NP-completo cuando cada variable aparece en un máximo de 3 cláusulas. A continuación, se realiza la reducción "estándar" de 3SAT a Set-Cover, y se observa que todos los conjuntos son de tamaño constante).
Consideremos ahora un caso de cobertura de conjuntos. Tenga en cuenta que si a través de todos los subconjuntos de cada $S_i$ la respuesta a la pregunta de portada no cambia. Obsérvese que podemos hacer esto ya que cada subconjunto es de tamaño constante, por lo que no hay demasiados subconjuntos que añadir. Así obtenemos
Hered-Set-Cover
Entrada: Sea $\mathcal{S}\subseteq > 2^{[n]}$ sea una familia de conjuntos, cada uno de tamaño $O(1)$ que es subconjunto cerrado. Sea $k$ sea un número entero.
Ouptut: Decidir si $[n]$ es la unión de $\le k$ de los conjuntos de $\mathcal{S}$ .
y Hered-Set-Cover es NP-completo, como se ha argumentado anteriormente. Ahora reduciremos Hered-Set-Cover a MHW. Tomemos una instancia de Hered-Set-Cover, con la familia de conjuntos $\mathcal{S}$ y enteros $k$ . Supongamos que hay $m$ conjuntos. A continuación, escribe $P$ ser el $m\times n$ matrx donde las filas son los vectores indicadores de los conjuntos en $\mathcal{S}$ . El vector objetivo $b$ es el vector de todos unos, y $k$ es como en el problema original. Por tanto, si $b$ es un $\le k$ combinación lineal de las filas, entonces esto da inmediatamente el conjunto-cubierta de $\le k$ conjuntos. Si existe un conjunto-cubierta de $\le k$ siempre podemos pasar a subconjuntos de forma que cada elemento del conjunto de base se cubra exactamente una vez, y así cuando sumemos los vectores relevantes en $\mathcal{F}_2$ nunca nos encontramos con el problema de que 2=0.
Así que en realidad estamos haciendo un "conjunto-cubierta con impar cubriendo en cada vértice" en la instancia MHW. La cuestión es que permitir los subconjuntos en la familia hace que el número exacto de coberturas sea irrelevante, y así podemos asumir que las cosas se cubren exactamente una vez.
Parece que podría haber una reducción más directa del problema Exact-Cover (donde en set-cover requerimos que cada elemento sea cubierto exactamente una vez). De hecho, acabo de desentrañar las reducciones necesarias para utilizar Exact-Cover. Pero Exact-Cover no parece exactamente correcto, porque si $b$ es un $\le k$ combinación lineal esto no se traduce inmediatamente en una cobertura exacta.
Este enfoque no parece resolver el problema cuando $M$ y $N$ son de rango completo en el problema RRD, ya que la reducción de MHW a RRD necesita que no sean de rango completo, y el problema MHW es resoluble en tiempo polinómico cuando $P$ es de rango completo.
