Problema de vetores não ortogonais

8

Considere os seguintes problemas:

Problema de vetores ortogonais

Entrada: um conjunto S de vetores booleanos, cada um de comprimento .nd

Pergunta: Existem vetores distintos e tais que ?v1v2Sv1v2=0

Problema de vetores não ortogonais

Entrada: Um conjunto de vetores booleanos, cada um de comprimento e um número inteiro positivo .Sndk

Pergunta: Existem vetores distintos e tais que ?v1v2Sv1v2k

Qual é a relação entre esses dois problemas?

Em particular, aqui estão algumas perguntas mais específicas sobre as quais eu tenho me perguntado:

(1) Um desses problemas parece ser mais difícil que o outro?

(2) Não sei ao certo qual é o algoritmo atual do OVP, mas para um desses problemas, é possível obter um limite superior melhor que o tempo ?O(n2d)

(3) A fixação de faz alguma diferença para a complexidade do segundo problema?k

Por , quero dizer o produto interno de e sobre .v 1 v 2 R dv1v2v1v2Rd

Editar: a maioria das respostas oferece idéias realmente excelentes quando é pequeno. d

O que se pode dizer quando é maior? Diga ou ou pelo menos para alguns .d = n d = dd=n d=nαα>0d=nd=nαα>0

Michael Wehar
fonte
4
Em relação a (2): até onde eu sei, o algoritmo mais conhecido para resolver OVP foi estabelecido neste artigo . Possui complexidade Melhorar esse resultado paraO(n2-ε)para uma constanteεé um famoso problema aberto, e acredita-se improvável, poisfalsificaria a forte conjectura da hipótese de tempo exponencial.
O(n21O(log(dlogn))).
O(n2ε)ε
Geoffroy Couteau
O segundo problema também é solucionável em tempo. Apenas escolhakposições e verifique se dois vetores têm todos os 1s nessas posições. O(nk(dk))k
Michael Wehar
1
Uma observação sobre o tempo limite acima para OVP: o tempo limite também exige que d <= 2 ^ (sqrt (log n)), caso contrário, a construção intermediária de um polinômio probabilístico leva muito tempo.
Ryan Williams
2
Sobre d grande: os algoritmos para multiplicação de matriz retangular superam n ^ 2 d na computação de todos os produtos de ponto. Quando d <n ^ 0,3, o tempo limite se torna n ^ (2 + o (1)).
Rasmus Pagh 19/09/18
1
@ MichaelWehar: Exatamente. Eu acho que o melhor resultado se deve a François Le Gall, arxiv.org/abs/1204.1111
Rasmus Pagh

Respostas:

8

kS{0,1}dmax(a,b)S,abab

Recentemente, eu e Ryan Williams temos um trabalho (ainda não publicado) mostrando que, quando , OVP e uma versão bicromática do Max-IP (dado , encontre ) é realmente equivalente: ou seja, se um deles possui o algoritmo de tempo , o mesmo ocorre com o outro. (A redução de OVP para Max-IP é bem conhecida, a nova redução aqui é a de Max-IP para OVP).A , B max ( a , b ) A × B a b n 2 - εd=O(logn)A,Bmax(a,b)A×Babn2ε

Como a versão monocromática do Max-IP pode ser reduzida para a versão bicromática, o resultado acima também implica que, quando , o Max-IP monocromático pode ser reduzido para OVP.d=O(logn)

Eu acredito que é uma questão em aberto que se o OVP pode ser reduzido a Max-IP monocromático. Isso também está intimamente relacionado ao estabelecimento da dureza OV para o problema do par mais próximo (consulte Por exemplo, Sobre a complexidade do par mais próximo via par polar de conjuntos de pontos )

Para Max-IP monocromático, existe um algoritmo com tempo de execução algoritmo de tempo de Alman, Chan e Williams ( também apontado por Rasmus), para o qual acredito ser o estado da arte. Enquanto o melhor algoritmo para OVP é executado em quando , que é significativamente mais rápido. n 2 - 1 / O ( log c ) d = c log nn21/O~((d/logn)1/3)n21/O(logc)d=clogn

Além disso, a versão aproximada do Max-IP também é estudada por este artigo Sobre a dureza do produto interno máximo aproximado e exato (bicromático) , que fornece uma caracterização para o caso bicromático (ou seja, para quais dimensões e relação aproximada , o problema pode ser resolvido em tempo?). O algoritmo desse artigo também funciona para o caso monocromático.t n 2 - εdtn2ε

Lijie Chen
fonte
O algoritmo de tempo requer alguns limites em ? dn21/O~((d/logn)1/3)d
Michael Wehar 30/06/19
6

Se , acredito que as técnicas de Alman, Chan e Williams fornecem a solução mais conhecida para o problema de vetores não ortogonais. (Eles o definem de maneira diferente, como um problema de par mais próximo de Hamming, mas isso é equivalente a fatores poli ( ).)dk=O(logn)d

Sem limite em , uma versão bicromática do Problema de Vetores Não Ortogonais é pelo menos tão difícil quanto o Problema de Vetores Ortogonais (OVP) até um fator . Primeiro, observe que, com um fator cima, podemos reduzir para a versão bicromática do OVP, onde (união em conjuntos de "cores" diferentes) e estamos interessados ​​apenas em pares ortogonais bicromáticos . Segundo, com um fator acima, podemos reduzir ao caso especial de OVP bicromático, em que todos os vetores em têm o mesmo peso de Hamming . Por fim, invertendo todos os vetores em para obterd log n log n S = S 1S 2 ( v 1 , v 2 ) S 1 × S 2 d S 1 w S 2 S 2 S 1 S 2 S 1 S 2 wkdlognlognS=S1S2(v1,v2)S1×S2dS1wS2S2 , vemos que e têm um par ortogonal se e somente se e tiverem um par de vetores com produto escalar pelo menos . Não tenho certeza se há uma redução eficiente do problema bicromático de vetores não ortogonais para a versão monocromática que você descreve.S1S2S1S2w

Se você permitir a aproximação, há vários resultados recentes para o problema bicromático de vetores não ortogonais (geralmente chamado de problema de pesquisa interna máxima do produto). Veja, por exemplo, este artigo e suas referências.

Rasmus Pagh
fonte
0

Equivalências:

O problema de vetores não ortogonais (como definido acima) para um conjunto S de n vetores booleanos, cada um de comprimento d e um número inteiro positivo k é equivalente ao seguinte:

  • Encontre uma submatriz 2 por k de 1's em um dado n por d Matriz booleana.

  • Encontrar um K2,k subgráfico completa em um determinado gráfico bipartido, onde o primeiro conjunto de vértices tem o tamanho n e o segundo conjunto de vértices tem o tamanho d .

Algoritmo ingênuo:

A abordagem ingênua para o problema de vetores não-ortogonais é executada em O(dn2) tempo, porque leva O(dn2) tempo para calcular ingenuamente o produto escalar de cada par de vetores.

Responda às perguntas (2) e (3):

Sim, existem vários algoritmos que são mais eficientes em diferentes casos.

Primeira abordagem:

Podemos resolver o problema de vetores não ortogonais no tempo O(dn+kn2) .

Nota: Como o produto escalar de dois vetores booleanos de comprimento d deve ser delimitado por d , o problema só faz sentido quando kd .

Prova. Seja dado um conjunto S de n vetores booleanos, cada um de comprimento d e um número inteiro positivo k . Considere-se uma enumeração {si}i[n] dos elementos de S .

Criar uma hashmap m de pares (a,b)[n]×[n] para N . Inicialmente, m mapeia cada entrada para o valor 0.

Para cada i[d] , fazemos o seguinte. Enumere através de pares de vetores sa , sb modo que a<b , o i bit de sa seja 1 e o i bit de sb seja 1. Para cada um desses sa e sb se m(a,b)=k1 , então sa e sbsão não ortogonais, isto é, sasbk . Caso contrário, incremente m(uma,b) e continue.

Se terminarmos a enumeração, nenhum par de vetores será não ortogonal.

Leva O(nd) tempo para percorrer todos os bits de cada vector. Em seguida, leva mais tempo para enumerar pares de vetores. Porque existem no máximo (n2) pares de vetores e cada par pode aparecer no máximok1vezes antes de se mostrar não ortogonal, enumerar os pares leva no máximoO(kn2). Portanto, o tempo de execução total éO(dn+kn2).

Nota: Quando k=2 , podemos melhorar essa abordagem para o tempo O(nd) . Isso ocorre porque quando k=2 , podemos reduzir a localização de um par de vetores não ortogonais entre n vetores booleanos de comprimento d para encontrar um par de vetores não ortogonais entre d vetores booleanos de comprimento n .

Segunda abordagem:

Podemos resolver o problema de vetores não ortogonais em O(k(dk)n)de tempo.

Prova. Seja dado um conjunto S de n vetores booleanos, cada um de comprimento d e um número inteiro positivo k .

Enumere através dos conjuntos P[d] modo que P tenha o tamanho k . Para cada vector vS , verificar se v tem todos os 1 de nas posições em P . Existem dois vetores que têm todos os 1s nas posições em P , então encontramos dois vetores não ortogonais.

No total, existem (dk) possíveis escolhas paraP. E, para cada escolha, nós fazemos a varredura atravésknpedaços dos vetores. Portanto, no total, o tempo de execução éO(k(dk)n).

Terceira abordagem:

Quando dn , podemos resolver o problema de vetores não-ortogonais em O(dω2n2) tempo em que ω é o expoente da multiplicação da matriz inteira. Quando d>n , podemos resolver o problema de vetores não-ortogonais no tempo O(dnω1) .

Nota: Conforme apontado por @Rasmus Pagh, podemos melhorar esse algoritmo para O(n2+o(1)) tempo em que dn0.3 . Veja aqui para mais informações: https://arxiv.org/abs/1204.1111

Prova. Seja dado um conjunto S de n vetores booleanos, cada um de comprimento d e um número inteiro positivo k .

Considere matrizes A e B . A primeira matriz A tem dimensões n por d em que cada linha de A é um vector a partir de S . A segunda matriz B tem dimensões d por n , onde cada coluna de B é um vector a partir de S .

Podemos calcular o produto escalar de cada par de vetores em S calculando AB usando algoritmos para multiplicação rápida da matriz inteira.

Quando dn , uma abordagem é converter a multiplicação de matriz retangular em (nd)2multiplicações do quadradodpordmatrizes. Usando a multiplicação rápida da matriz quadrada, podemos calcular todas as multiplicações emO((nd)2dω)=O(dω2n2)tempo.

Quando d>n , uma abordagem é converter a multiplicação de matriz retangular em dn multiplicações denquadradospornmatrizes. Usando a multiplicação rápida da matriz quadrada, podemos calcular todas as multiplicações emO((dn)nω)=O(dnω1)hora.

Michael Wehar
fonte
Vamos comparar essas três abordagens em vários casos diferentes. Caso 1: Quando é fixo ed = O ( log 2 ( n ) ) , a segunda abordagem é mais eficiente. kd=O(log2(n))
Michael Wehar 30/06/19
Caso 2: Quando e d = S ( n α ) para qualquer α ( 0,3 , 1 ) , a primeira abordagem é, por vezes, mais eficiente. k=O(log2(n))d=O(nα)α(0.3,1)
Michael Wehar 30/06/19
Caso 3: Quando , o terceiro caso às vezes é mais eficiente. dn0.3
Michael Wehar 30/06/19
Caso 4: Quando e k são maiores que n , a terceira abordagem às vezes é mais eficiente. dkn
Michael Wehar 30/06/19
Nota: A primeira abordagem é bastante semelhante ao algoritmo para encontrar um ciclo de quatro em um gráfico em tempo quadrático. Veja aqui: sciencedirect.com/science/article/pii/S0304020808730196
Michael Wehar