Encontrar testemunha na soma minkowski de números inteiros

16

Seja e subconjuntos de . Estamos interessados ​​em encontrar a soma de Minkowski .AB{0,,n}A+B={a+b | aA,bB}

χX:{0,,2n}{0,1} é uma função característica de seX

χX(x)={1 if xX0 otherwise

Seja a convolução discreta de e , então se e somente se . Portanto, pode ser calculado em tempo por convolução discreta via FFT.fχAχBxA+Bf(x)>0A+BO(nlogn)

Às vezes, é importante descobrir o par real e que soma . é chamado testemunha de , se existir modo que . Uma função w: A + B \ a A é chamada função de testemunha se w (x) for uma testemunha de x .aAbBxaAxbBa+b=xw:A+BAw(x)x

É possível calcular uma função de testemunha no tempo O(nlogn) ?

Chao Xu
fonte
3
O(npolylogn) não é especialmente difícil.
Sariel Har-Peled
2
Você pode usar a pesquisa binária. por exemplo, particione A em dois conjuntos de tamanho aproximadamente igual AL,AR e calcule AL+B e AR+B ; verifique em qual desses x está; e recursar. Isso lhe dará algo como O(nlg2n) .
DW
@DW Isso só pode encontrar uma testemunha para um único x , mas queremos uma testemunha para cada elemento em A+B . (meu texto parece ser claro, então eu atualizei a questão)
Chao Xu
Mas você está interessado na solução O (n polylog n)?
Sariel Har-Peled
@ SarielHar-Peled sim, também estou interessado no algoritmo determinístico O(npolylogn) .
Chao Xu

Respostas:

11

Aqui estou explicando como obter o tempo de execução aleatório . Precisamos de uma sequência de observações:O(npolylogn)

  1. Uma testemunha de um valor é um par de números modo que . Deixe e ser definido de forma análoga. Observe que o coeficiente de em é o número de testemunhas que existem para o valor .( a , b ) A × B a + b = v P A ( x ) = i A x i P B ( x ) x v P A ( x ) P B ( x ) vv(a,b)A×Ba+b=vPA(x)=iAxiPB(x)xvPA(x)PB(x)v

  2. Suponha que tenha uma única testemunha e considere o polinômio . Claramente, o coeficiente de em é e, como tal, agora conhecemos o par e terminamos.( um , b ) Um × B Q A ( x ) = Σ i Um i * x i x v Q A ( x ) * P B ( x ) um ( um , v - um )v(a,b)A×BQA(x)=iAixixvQA(x)PB(x)a(a,va)

  3. Então, acabamos com o caso de que há uma única testemunha. Portanto, considere o caso em que possui testemunhas . Seja . Observe que . Em seguida, sejam , para , para , amostras aleatórias, de modo que cada elemento de seja escolhido em com probabilidade . A probabilidade de ter uma única testemunha em ék ( a 1 , b 1 ) , , ( a k , b k ) i ( k ) = lg vk(a1,b1),,(ak,bk)2i(k)-1i(k)=lgk Rj=(Aj,Bj)j=1,...,mm=S(logn)AAip=1/2 i ( k ) vRJα= ( k2Eu(k)-1 1k2Eu(k)Rj=(Aj,Bj)j=1,,mm=O(logn)AAip=1/2i(k)vRjα=(k1)p2(1p2)k1, uma vez que a testemunha são pares de números separados (já que a soma de cada par é ). É fácil verificar se é uma constante em independente do valor de . Como tal, deve ser, com alta probabilidade, que tenha uma única testemunha em uma das amostras . Assim, calculando os dois polinômios associados a essa amostra, conforme descrito acima, em tempo (por amostra), usando a FFT, podemos decidir isso em tempo constante.α ( 0 , 1 ) k v R 1 , , R m O ( n log n )vα(0,1)kvR1,,RmO(nlogn)

  4. Estamos quase terminando. Calcule as amostras aleatórias acima para as resoluções . Para cada uma dessas resoluções, calcule as amostras aleatórias e os polinômios associados. Além disso, calcula-se o polinómio associado para e . Esse pré-processamento ingenuamente leva , mas suspeito que, sendo um pouco mais cuidadoso, um fator deve ser removível.A B O ( N log 3 n ) log ni=1,,lgnABO(nlog3n)logn

  5. O algoritmo: para cada valor , calcule quantas testemunhas, digamos, k, ela tem em tempo constante, consultando o polinômio . Em seguida, vá para a estrutura de dados relevante para . Em seguida, encontra a amostra aleatória que a possui como testemunha única e extrai o par que é essa testemunha em tempo constante.Q A ( x ) P B ( x ) i ( k )vQA(x)PB(x)i(k)

  6. Curiosamente, o tempo de pré-processamento é , mas o tempo esperado para encontrar a testemunha leva apenas tempo, pois é possível interromper a pesquisa assim que encontrar uma testemunha. Isso sugere que esse algoritmo deve ser improvável. Em particular, para , os polinômios gerados são muito escassos e deve-se conseguir fazer FFT muito mais rápido.O ( n ) i ( k ) lg nO(nlog3n)O(n)i(k)lgn

Sariel Har-Peled
fonte
12

Ok, estou adiando, já que realmente Sariel deve receber crédito por uma resposta, mas estou cansado de esperar, então aqui está o meu corte em um algoritmo aleatório quase linear.

  • Ao escolher amostras de pontos, , é possível obter um número logarítmico de subproblemas, de modo que cada soma do problema original tenha probabilidade constante de ser representada exclusivamente em um dos os subproblemas (aquele em que a amostragem reduz o número esperado de representações para próximo de 1). i = 0 , 1 , n(1ϵ)ii=0,1,
  • Repetindo o processo de amostragem um número logarítmico de vezes, é possível obter todas as somas para ter representações exclusivas com alta probabilidade.
  • Se você tiver uma partição de e em dois subconjuntos, multiplicando os números por quatro, adicionando 2 aos números em um dos subconjuntos em e adicionando 1 aos números em um dos subconjuntos em , você poderá leia a partir dos valores mod-4 das somas alcançáveis ​​de quais dos dois subconjuntos seus somas vêm.B A BABAB
  • Repetindo o processo de partição um número logarítmico de vezes, usando cada posição de bit das representações binárias dos valores ou índices nos subproblemas para selecionar as partições em cada etapa, é possível identificar exclusivamente as somas de cada soma representada exclusivamente.

Isso aumenta o tempo de execução por três fatores logarítmicos; provavelmente isso pode ser reduzido.

David Eppstein
fonte
3
Ha ha;). Eu estava no meio da escrita e depois fui almoçar ...
Sariel Har-Peled
5

Esta resposta fornece um algoritmo determinístico .O(n polylogn)

Parece que o algoritmo de Sariel e David pode ser des randomizado através de uma abordagem semelhante a este artigo . [2] Durante o processo, descobri que há um problema mais geral que implica esse resultado.

O problema da reconstrução k

Não estão escondidos conjuntos , temos dois oráculos S i z e e S u m que tomar um conjunto de consulta Q .S1,,Sn{1,,m}SizeSumQ

  1. retorna ( | S 1Q | , | S 2Q | , , | S nQ | ) , o tamanho de cada interseção.Size(Q)(|S1Q|,|S2Q|,,|SnQ|)
  2. retorna ( s S 1Q s , s S 2Q s , , s S nQ s ) , a soma dos elementos em cada interseção.Sum(Q)(sS1Qs,sS2Qs,,sSnQs)

knS1,,SnSiSii|Si|=min(k,|Si|)i

Seja o tempo de execução dos oráculos e assuma , então é possível encontrar os conjuntos no tempo determinístico . [1]f = Ω ( m + n ) O ( f k log n p o l y L o g ( m ) )ff=Ω(m+n)O(fklogn polylog(m))

Agora podemos reduzir o problema da testemunha de localização para o problema de reconstrução. Aqui que .S 1 , , S 2 n{ 1 , , 2 n } S i = { a | a + b = i , a A , b B }1S1,,S2n{1,,2n}Si={a|a+b=i,aA,bB}

Defina os polinômios ,χQ(x)=iQxiIQ(x)=iQixi

O coeficiente para em ée em é . Portanto, os oráculos levam tempo por chamada.xiχQχB(x)|SiQ|IQχB(x)sSiQsO(nlogn)

Isso nos fornece um algoritmo determinístico de tempo .O(n polylog(n))

[1] Yonatan Aumann, Moshe Lewenstein, Noa Lewenstein, Dekel Tsur: Encontrando testemunhas descascando . Transações ACM nos algoritmos 7 (2): 24 (2011)

[2] Noga Alon, Moni Naor: Derandomization, testemunha da multiplicação da matriz booleana e construção de funções perfeitas de hash . Algoritmica 16 (4-5) (1996)

Chao Xu
fonte