Considere el siguiente problema:
Entrada : un hiperplano , dado por un vector y en representación binaria estándar.a ∈ Z n b ∈ Z
Salida :
En la notación anterior para y se define como , es decir, es la distancia euclidiana natural entre un conjunto de puntos y un solo punto .
En palabras, se nos da un hiperplano y estamos buscando el punto en el entramado entero más cercano al hiperplano.
La pregunta es:
¿Cuál es la complejidad de este problema?
Tenga en cuenta que el tiempo polinomial aquí significará polinomio en el tamaño de bits de la entrada. Por lo que puedo ver, el problema es interesante incluso en dos dimensiones. Entonces no es difícil ver que es suficiente considerar solo aquellas soluciones con pero eso es superpolinomialmente muchas opciones.
Un problema estrechamente relacionado es resolver una ecuación lineal de diofantina, es decir, encontrar un tal que o determinar que no existe tal existe. Entonces, resolver una ecuación lineal de diofantina es equivalente a determinar si existe una solución de valor 0 para el problema que definí anteriormente. Una ecuación lineal de diofantina se puede resolver en tiempo polinómico; de hecho, incluso los sistemas de ecuaciones lineales de diofantina se pueden resolver en tiempo polinómico calculando la forma normal de Smith de la matriz proporciona el sistema. Existen algoritmos de tiempo polinómico que calculan la forma normal de Smith de una matriz entera, la primera dada porKannan y Bachem .
Para tener una intuición sobre las ecuaciones lineales de diofantina, podemos considerar nuevamente el caso bidimensional. Claramente, no hay una solución exacta si no divide . Si lo hace división , a continuación, puede ejecutar el algoritmo de GCD prolongado para obtener dos números y tal que y el conjunto y . Ahora puede ver cómo la versión aproximada es diferente: cuando no divide , ¿cómo encontramos números enterosb b s t a 1 s + a 2 t = g c d ( a 1 , a 2 ) x 1 = s b / g c d ( a 1 , a 2 ) x 2 = t b / g c d ( a 1 ,g c d ( a 1 , a 2 ) b x 1 , x 2tal que la distancia entre y la línea se minimiza?a 1 x 1 + a 2 x 2 = b
El problema para mí suena un poco como el problema de vector más cercano en las redes, pero no veo una reducción obvia de un problema a otro.
fuente
Respuestas:
Muy bien, después de pensarlo más, creo que tengo una reducción explícita de este problema a GCD extendido; Lo explicaré en el caso , pero creo que se extiende a arbitraria . Tenga en cuenta que esto encuentra un que minimiza la distancia al hiperplano, pero no necesariamente el más pequeño (de hecho, hay infinitos valores que alcanzan la misma distancia mínima). Creo que el último problema es También es factible, pero todavía no lo he pensado realmente. El algoritmo se basa en algunos principios simples:n x xn=2 n x x
Esto sugiere el siguiente procedimiento:
Hasta donde yo sé, exactamente el mismo procedimiento debería funcionar correctamente en dimensiones arbitrarias; la clave es que el dimensional GCD aún satisface la identidad de Bezout, por lo que para encontrar la distancia mínima a un punto de red solo tiene que encontrar el múltiplo más cercano de a .g bn g b
fuente