Resolvendo uma equação diofantina linear aproximadamente

15

Considere o seguinte problema:

Entrada : um hiperplano H = { yR n : a T y = b }H={yRn:aTy=b} , dado por um vetor aZ naZn e b ZbZ na representação binária padrão.

Saída : xZ n = arg min d ( x , H )xZn=argmind(x,H)

Na notação acima, d ( x , S )d(x,S) para e é definido como , ou seja, é a distância euclidiana natural entre um conjunto de pontos e um único ponto.xRnSRnd ( x , S ) = min ySx - y2d(x,S)=minySxy2

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 )(x1,x2)0x1|a1|/gcd(a1,a2)

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 porxZ n a T x = b xxZnaTx=bxUMAAKannan e Bachem .

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 ,gcd(a1,a2)bbsta1s+a2t=gcd(a1,a2)x1=sb/gcd(a1,a2)a2)x2=tb/gcd(a1,a2)gcd(a1,a2)gcd(a1,a2)bbx1,x2x1,x2tal que a distância entre e a linha é minimizada?(x1,x2)(x1,x2)a1x1+a2x2=ba1x1+a2x2=b

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.

Sasho Nikolov
fonte
não, não: a aproximação diofantina é um problema diferente da solução de uma equação diofantina. em um problema de aproximação diofantina, você recebe n números reais e deseja multiplicá-los todos por um único número Q, de modo que todos eles estejam dentro de ϵ de algum número inteiro. a questão é encontrar a troca ideal entre o tamanho de Q e ϵ . Não vejo uma relação entre o meu problema e este. nQϵQϵ
Sasho Nikolov
Qual é o seu formato de entrada? Parece que se quaisquer dois valores de coordenadas de um são incomensuráveis então o mínimo em questão é zero (se intersectam com o plano 2-dimensional apropriado para obter uma equação da forma s x + t y = W com s e t incomensuráveis, ou seja α sasx+ty=wstt irracional e, em seguida, use os resultados padrão em{nα}αst( mod1 ) para mostrar que a linha passa arbitrariamente perto dos pontos da rede. {nα}(mod1)
Steven Stadnicki
Em particular, isto significa que o seu 'min' deve ser um 'inf' (sine você está tomando mais de um número infinito de pontos), e o problema de saber se i n f d ( x , H ) = 0  é distinta da questão se existe algum x com d ( x , H ) = 0 . Isso significa que os coeficientes de a devem ser números racionais para que o problema tenha uma solução não trivial, e então o problema parece assumir uma forma muito euclidiana, intimamente acoplada aos algoritmos multidimensionais de GCD. Estou esquecendo de algo? inf d(x,H)=0xd(x,H)=0a
Steven Stadnicki
@StevenStadnicki right. você pode assumir aZ n e b Z (acrescentarei isso à pergunta, devo ter esquecido). a entrada é dada na representação binária padrão. a questão é interessante mesmo quando n = 2 . basta considerar todas as soluções possíveis ( x 1 , x 2 ) com x 1| a 1 | / g c d ( a 1 , a 2 )aZnbZn=2(x1,x2)x1|a1|/gcd(a1,a2), Mas a busca bruteforce será superpolynomial na representação binária de um 1 , um 2 . a1,a2
Sasho Nikolov 01/02/2012

Respostas:

5

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=2n xx

  • Se g = G C D ( a 1 , a 2 ) , então o conjunto de valores assumidos por ax = a 1 x 1 + a 2 x 2 é precisamente { 0 , ± g , ± 2 g , ± 3 g , ... } ; Além disso, os valores de x 1 e x 2 com um 1 x 1g=GCD(a1,a2)ax=a1x1+a2x2{0,±g,±2g,±3g,}x1x2+ a 2 x 2 = g pode ser encontrado eficientemente (esse é exatamente o algoritmo euclidiano estendido).a1x1+a2x2=g
  • A distância mínima do hiperplano até um ponto na rede é a distância mínima de um ponto na rede até o hiperplano (óbvio, mas uma inversão útil do problema).
  • A distância de um dado ponto x ao hiperplano ay = b é proporcional a | umx - b | (especificamente, é 1 / | a | vezes esse valor - mas, como a multiplicação de todas as distâncias por esse valor não afeta o local mínimo, podemos ignorar o fator de normalização).xay=b|axb|1/|a|

Isso sugere o seguinte procedimento:

  • Calcular g = G C D ( um 1 , um 2 ) , juntamente com X 0 1 , x 0 2 de tal modo que um 1 x 0 1 + um 2 x 0 2 = g .g=GCD(a1,a2)x01,x02a1x01+a2x02=g
  • Calcular r = bge calculed=min(b-rg,(r+1)g-b); dé a distância mínima (escalada) da rede ao hiperplano. Deixesserrour+1(=bg, a menos quebseja um múltiplo deg) dependendo de qual deles atingir a distância mínima.
  • Calcular x 1 = s x 0 1 e X 2 = s x 0 2 ; então ax = s g é o múltiplo mais próximo de g a b e, portanto, | umx - b | atinge o mínimo dessa distância em todos os pontos da rede.

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 .

Steven Stadnicki
fonte