Cómo encontrar el vector de densidad de un subespacio dado de $\mathbb{F}_2^n$

Question

Un subespacio $C$ $\mathbb{F}_2^n$ para $n \geq 1$. El espacio de $C$ está dado por su base.

Existe un polinomio tiempo algoritmo para encontrar el (distinto de cero) vector en $C$ de los más bajos de hamming de peso?

Motivación: Encontrar la distancia de un determinado lineal de código.

Answer 1

Para los efectos de este problema, nos limitamos a códigos lineales presentan en términos de su generador (o, equivalentemente, la comprobación de paridad) de la matriz. A continuación, Alexander Vardy (1997) mostraron que el cómputo de la distancia mínima de un lineal de código exactamente es NP-duro. [La decisión de la versión de este problema es: dado un lineal de código $C$ y un atado $k$, ¿existe un código distinto de cero $c$ $C$ peso $k$ o menos? Esta versión es NP-completo.]

Se han realizado varias mejoras a este resultado básico -- ahora se sabe que también es bastante difícil (un.) aproximado de la distancia, (b.) decodificar una palabra recibida bajo la promesa de que no hay una única palabra clave cerca de ella, etc. Por desgracia, yo no tengo el tiempo ahora al detalle todos los acontecimientos, pero este parece ser un buen lugar para empezar: http://cseweb.ucsd.edu/~daniele/Research/CodeComp.html . Voy a tratar de ampliar esta respuesta más tarde.

Referencia:

A. Vardy, la Inflexibilidad de La Computación de la Distancia Mínima de un Código - IEEE transactions on Teoría de la Información, 1997.