Encontrar testemunha na soma minkowski de números inteiros

Seja e subconjuntos de . Estamos interessados ​​em encontrar a soma de Minkowski .$A$$B$$\{0,\ldots,n\}$$A+B=\{a+b~|~a\in A,b\in B\}$

$\chi_X:\{0,\ldots,2n\}\to \{0,1\}$ é uma função característica de se$X$

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$$\chi_A$$\chi_B$$x\in A+B$$f(x)> 0$$A+B$$O(n\log n)$

À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 .$a\in A$$b\in B$$x$$a\in A$$x$$b\in B$$a+b=x$$w:A+B\to A$$w(x)$$x$

É possível calcular uma função de testemunha no tempo $O(n\log n)$ ?

Aqui estou explicando como obter o tempo de execução aleatório . Precisamos de uma sequência de observações:$O(n *\mathrm{polylog} n)$

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 ) $v$$(a,b) \in A \times B$$a+b=v$$P_A(x) = \sum_{i \in A} x^i$$P_B(x)$$x^v$$P_A(x) * P_B(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) \in A \times B$$Q_A(x) = \sum_{i \in A} i*x^i$$x^v$$Q_A(x)*P_B(x)$$a$$(a,v-a)$

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 $v$$k$$(a_1, b_1),\ldots, (a_k,b_k)$2i(k)-1≤$i(k) = \lceil{\lg \sqrt{k}}\rceil$ Rj=(Aj,Bj)j=1,...,mm=S(logn)AAip=1/2 i ( k ) vRJα= ($2^{i(k)-1} \leq \sqrt{k} \leq 2^{i(k)}$$R_j = (A_j, B_j)$$j=1,\ldots, m$$m=O(\log n)$$A$$A_i$$p = 1/2^{i(k)}$$v$$R_j$$\alpha = \binom{k}{1}p^2 (1-p^2)^{k-1}$, 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$$\alpha$$(0,1)$$k$$v$$R_1, \ldots, R_{m}$$O(n \log n)$

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 $i=1,\ldots, \lceil\lg n\rceil$$A$$B$$O(n \log^3 n)$$\log n$

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 $v$$Q_A(x)*P_B(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 $O(n \log^3 n)$$O(n)$$i(k) \ll \lg n$

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-\epsilon)^i$$i=0,1,\dots$
• 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 $A$$B$$A$$B$
• 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.

Esta resposta fornece um algoritmo determinístico .$O(n~\mathrm{polylog} n)$

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 .$S_1,\ldots,S_n \subset \{1,\ldots,m\}$$Size$$Sum$$Q$

1. retorna ( | S 1 ∩ Q | , | S 2 ∩ Q | , … , | S n ∩ Q | ) , o tamanho de cada interseção.$Size(Q)$$(|S_1\cap Q|,|S_2\cap Q|,\ldots,|S_n\cap Q|)$
2. retorna ( ∑ s ∈ S 1 ∩ Q s , ∑ s ∈ S 2 ∩ Q s , … , ∑ s ∈ S n ∩ Q s ) , a soma dos elementos em cada interseção.$Sum(Q)$$(\sum_{s\in S_1\cap Q} s,\sum_{s\in S_2\cap Q} s,\ldots,\sum_{s\in S_n\cap Q} s)$

$k$$n$$S_1',\ldots,S_n'$$S_i'\subset S_i$$|S_i'|=\min(k,|S_i|)$$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 ) $f$$f=\Omega(m+n)$$O(f k \log n~\mathrm{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 $1$$S_1,\ldots,S_{2n}\subset \{1,\ldots,2n\}$$S_i = \{a|a+b = i, a\in A, b\in B\}$

Defina os polinômios ,$\chi_Q(x) = \sum_{i \in Q} x^i$$I_Q(x) = \sum_{i \in Q} i x^i$

O coeficiente para em ée em é . Portanto, os oráculos levam tempo por chamada.$x^i$$\chi_Q\chi_B(x)$$|S_i\cap Q|$$I_Q\chi_B(x)$$\sum_{s\in S_i\cap Q} s$$O(n\log n)$

Isso nos fornece um algoritmo determinístico de tempo .$O(n~\mathrm{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)