Considere os seguintes problemas:
Problema de vetores ortogonais
Entrada: um conjunto de vetores booleanos, cada um de comprimento .
Pergunta: Existem vetores distintos e tais que ?
Problema de vetores não ortogonais
Entrada: Um conjunto de vetores booleanos, cada um de comprimento e um número inteiro positivo .
Pergunta: Existem vetores distintos e tais que ?
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 ?
(3) A fixação de faz alguma diferença para a complexidade do segundo problema?
Por , quero dizer o produto interno de e sobre .v 1 v 2 R d
Editar: a maioria das respostas oferece idéias realmente excelentes quando é pequeno.
O que se pode dizer quando é maior? Diga ou ou pelo menos para alguns .d = n d = √ d=nαα>0
fonte
Respostas:
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,B max( a ,b)∈A×Buma⋅b n2 - ε
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 nn2−1/O˜((d/logn)1/3) n2−1/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 - εd t n2 - ε
fonte
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 1 ∪ S 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 wk dregistron registron S= S1∪ S2 ( v1, v2) ∈ S1× S2 d S1 W S2 S′2 , 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.S1 S2 S1 S′2 W
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.
fonte
Equivalências:
Algoritmo ingênuo:
Responda às perguntas (2) e (3):
Primeira abordagem:
Segunda abordagem:
Terceira abordagem:
fonte