Problema de vectores algorítmicos

Tengo un problema algebraico relacionado con vectores en el campo GF (2). Supongamos que sean (0,1) -vectores de dimensión , . Encuentre un algoritmo de tiempo polinómico que encuentre un vector (0,1) de la misma dimensión tal que no sea la suma de ningún vector entre $v_1, v_2, \ldots, v_m$ $n$ $m=n^{O(1)}$ $u$ $u$ $(\log n)^{O(1)}$ . La adición de vectores está sobre el campo GF (2), que tiene dos elementos 0 y 1 ( , y ). $v_1,v_2, \ldots, v_m$ $0+1=0+1=1$ $0+0=1+1=0$

Es fácil ver la existencia de tal vector u mediante un simple argumento de conteo. Podemos encontrar en un tiempo polinómico? Es trivial para encontrar en tiempo exponencial. Enviaré un cheque de $ 200 por la primera solución correcta. $u$ $u$

ds.algorithms linear-algebra Bin Fu
fuente

parece vagamente relacionado con el problema de suma de subconjuntos que es NP completo. sin embargo, eso usa la suma entera completa en lugar de XOR.

vzn

Curiosamente, recientemente he estado tratando de formular y mirar un problema similar. pruebe sec13.5 de stasys jukna book sobre la complejidad de la función booleana. parece que su q puede formularse en términos de circuitos lineales en ese capítulo.

vzn

¿Qué hay de algoritmos super-poli, es decir, m ^ log (n)?

Dimitris

@Niel de Beaudrap: pero la cantidad de XOR que debe verificar es superpolítica (es decir, aproximadamente

), no poli. ¿No es eso un problema?

(\binom{m}{\log (n)})

${{m}\choose{\log(n)}}$

Dimitris

Para extender el comentario de vzn: parecería que casi cualquier vector satisface sus requisitos, por el mismo argumento de conteo. Me imagino que también le gustaría una prueba de que un vector (tal vez generado aleatoriamente) no está contenido en ningún subespacio abarcado por polylog ( n ) de los vectores: por lo tanto, su pregunta equivale a mostrar que el problema de determinar si un candidato es o no el vector u no pertenece a un subespacio generado por alguna dimensión f ( n ) ∈ polylog ( n ) de los vectores

está en NP .

v_{j}

$\mathbf v_j$

Niel de Beaudrap

Respuestas:

Parece que hay un error tipográfico; Supongo que quiere encontrar que no es la suma de los vectores entre (no ). $u \in \{0,1\}^n$ $(\log n)^{O(1)}$ $v_1,\dots, v_m$ $n$

No me queda claro si alguna constante en funciona para usted. Si puede conformarse con sumas de menos de tal vez haya algo que hacer. Pero si desea que esta cantidad sea , entonces creo que es bastante difícil (he estado trabajando en este problema durante mucho tiempo). $(\log n)^{O(1)}$ $\log m$ $(\log m)^{1+\delta}$

Aún así, puede interesarle saber que esta es una instancia del Problema de punto remoto de Alon, Panigrahy y Yekhanin ("Algoritmos de aproximación deterministas para el problema de palabras de código más cercano") para ciertos parámetros. Dejar que y ser las columnas de la matriz de comprobación de paridad de un código lineal de de dimensión (si esta matriz no tenía rango completo, el El problema sería trivial). Entonces su problema es equivalente a encontrar $m > n$ $v_1,\dots,v_m$ $\{0,1\}^m$ $d = m - n$ que es $u \in \{0,1\}^n$ $(\log n)^{O(1)}$ $\log m$ $d = cm$ $c$ $\omega(\log m)$ $\Omega(m)$ , mucho menos encontrarlo.

$(\log n)^{O(1)}$ ${0,1}^m$ $n$ $n - 1$ $u$

El problema también está relacionado con la separación de EXP de ciertas reducciones a conjuntos dispersos.

david
fuente

Gracias por señalar el error tipográfico. El último "v_n" debería ser "v_m". Espero que alguien lo arregle. Su respuesta contiene información útil. +1

Bin Fu