Considere o seguinte problema:
Entrada : um hiperplano H = { y ∈ R n : a T y = b }
Saída : x ∈ Z n = arg min d ( x , H )
Na notação acima, d ( x , S )
Em palavras, recebemos um hiperplano e procuramos o ponto na rede inteira mais próximo do hiperplano.
A questão é:
Qual é a complexidade desse problema?
Observe que o tempo polinomial aqui significa polinômio no tamanho de bits da entrada. Tanto quanto posso ver, o problema é interessante, mesmo em duas dimensões. Portanto, não é difícil ver que basta considerar apenas essas soluções com mas isso é superpolinomialmente muitas opções.( x 1 , x 2 ) 0 ≤ x 1 ≤ | a 1 | / g c d ( a 1 , a 2 )
Um problema intimamente relacionado é resolver uma equação diofantina linear, ou seja, encontrar um tal que ou determinar que existe. Portanto, resolver uma equação diofantina linear é equivalente a determinar se existe uma solução de valor 0 para o problema definido acima. Uma equação diofantina linear pode ser resolvida em tempo polinomial; de fato, mesmo sistemas de equações diofantinas lineares podem ser resolvidos em tempo polinomial, computando a forma normal de Smith da matriz fornece o sistema. Existem algoritmos de tempo polinomial que calculam a forma normal de Smith de uma matriz inteira, o primeiro dado porx ∈ Z n a T x = b x
Para obter intuição sobre equações diofantinas lineares, podemos considerar o caso bidimensional novamente. Claramente, não há solução exata se não divide . Se dividir , você poderá executar o algoritmo GCD estendido para obter dois números e modo que e defina e . Agora você pode ver como a versão aproximada é diferente: quando não divide , como encontramos os inteirosg c d ( a 1 , a 2 ) b 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 ,
O problema para mim parece um pouco com o problema de vetor mais próximo nas redes, mas não vejo uma redução óbvia de um problema para o outro.
fonte
Respostas:
Tudo bem, pensando mais sobre isso, acredito que tenho uma redução explícita desse problema para o GCD estendido; Explicarei no caso n = 2 , mas acredito que se estenda a n arbitrário . Observe que isso encontra um x que minimiza a distância do hiperplano, mas não necessariamente o menor x (existem de fato infinitos valores que atingem a mesma distância mínima) - acredito que o último problema também é viável, mas não deu ainda é um pensamento real. O algoritmo é baseado em alguns princípios simples:n=2 n x x
Isso sugere o seguinte procedimento:
Até onde eu sei, o mesmo procedimento deve funcionar corretamente em dimensões arbitrárias; a chave é que o GCD n- dimensional ainda satisfaz a identidade de Bezout e, para encontrar a distância mínima até um ponto de rede, você só precisa encontrar o múltiplo mais próximo de g para b .
fonte