Considere los siguientes problemas:
Problema de vectores ortogonales
Entrada: Un conjunto S
S de nn vectores booleanos de longitud dd .Pregunta: ¿Existen vectores distintos v 1
v1 y v 2 ∈ S dev2∈S modo que v 1 ⋅ v 2 = 0v1⋅v2=0 ?Problema de vectores no ortogonales
Entrada: un conjunto S
S de nn vectores booleanos de longitud dd y un entero positivo kk .Pregunta: ¿Existen vectores distintos v 1
v1 y v 2 ∈ Sv2∈S tal que v 1 ⋅ v 2 ≥ kv1⋅v2≥k ?
¿Cuál es la relación entre estos dos problemas?
En particular, aquí hay algunas preguntas más específicas sobre las que me he estado preguntando:
(1) ¿Alguno de estos problemas parece ser más difícil que el otro?
(2) No estoy seguro de cuál es el algoritmo actual de última generación para OVP, pero para cualquiera de estos problemas, ¿puede obtener un límite superior mejor que el tiempo O ( n 2 ⋅ d )
(3) ¿Fijar k
Por v 1 ⋅ v 2
Editar: la mayoría de las respuestas ofrecen ideas realmente geniales cuando d
d es pequeño.¿Qué se puede decir cuando d
d es más grande? Say d = nd=n o d = √nd=n−−√ o al menosd=nαd=nα para algunosα>0α>0 .
Respuestas:
Cuando se da como parte de la entrada, el segundo problema es equivalente al problema monocromático de Max-IP (dado , find ).k S ⊆ { 0 , 1 } d max ( a , b ) ∈ S , a ≠ b a ⋅ bk S⊆ { 0 , 1 }re max( a , b ) ∈ S, a ≠ ba ⋅ b
Recientemente, yo y Ryan Williams tenemos un trabajo (aún no publicado) que muestra que cuando , OVP y una versión bicromática de Max-IP (dado , encuentran ), en realidad es equivalente: es decir, si uno de ellos tiene un algoritmo de tiempo , también lo tiene el otro. (La reducción de OVP a Max-IP es bien conocida, la nueva reducción aquí es la de Max-IP a OVP).d = O ( log n )re= O ( logn ) A , B max ( a , b ) ∈ A × B a ⋅ b n 2 - εA , B max( a , b ) ∈ A × Ba ⋅ b norte2 - ε
Dado que la versión monocromática de Max-IP se puede reducir a la versión bicromática, el resultado anterior también implica que cuando , la Max-IP monocromática se puede reducir a OVP.d = O ( log n )re= O ( logn )
Creo que es una pregunta abierta si OVP puede reducirse a Max-IP monocromática. Esto también está estrechamente relacionado con el establecimiento de la dureza OV para el problema de par más cercano (ver, por ejemplo, sobre la complejidad del par más cercano a través del par polar de conjuntos de puntos )
Para Max-IP monocromática, existe un algoritmo con tiempo de ejecución algoritmo de tiempo de Alman, Chan y Williams ( también señalado por Rasmus), por lo que creo que es el estado del arte. Mientras que el mejor algoritmo para OVP se ejecuta en tiempo cuando , que es significativamente más rápido.n 2 - 1 / ~ O ( ( d / log n ) 1 / 3 ) n 2 - 1 / O ( log c ) d = c log nnorte2 - 1 / O˜( ( d/ logn )1 / 3) norte2 - 1 / O ( registroc ) re=clogn
Además, la versión aproximada de Max-IP también se estudia en este documento sobre la dureza del producto interno máximo aproximado y exacto (bicromático) , que da una caracterización para el caso bicromático (es decir, para qué dimensiones y relación aproximada , El problema se puede resolver en tiempo?). El algoritmo en ese documento también funciona para el caso monocromático.d t n 2 - εd t n2−ε
fuente
Si creo que las técnicas de Alman, Chan y Williams dan la solución más conocida al problema de los vectores no ortogonales. (Lo expresan de manera diferente, como un problema de par más cercano de Hamming, pero esto es equivalente a los factores poli ( )).k = O ( log n ) dk=O(logn) d
Sin límite en , una versión bicromática del problema de vectores no ortogonales es al menos tan difícil como el problema de vectores ortogonales (OVP) hasta un factor . Primero, tenga en cuenta que con un factor sobrecarga podemos reducir a la versión bicromática de OVP donde (unión disjunta en conjuntos de "color" diferente) y solo estamos interesados en pares ortogonales bicromáticos . En segundo lugar, con un factor sobrecarga podemos reducir al caso especial de OVP bicromático donde todos los vectores en tienen el mismo peso de Hamming . Finalmente, invirtiendo todos los vectores en para obtenerk d 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 dlogn logn S=S1∪S2 (v1,v2)∈S1×S2 d S1 w S2 S′2 vemos que y tienen un par ortogonal si y solo si y tienen un par de vectores con producto punto al menos . Sin embargo, no estoy seguro de si hay una reducción eficiente del problema de vectores bicromáticos no ortogonales a la versión monocromática que usted describe.S1 S2 S1 S′2 w
Si permite la aproximación, hay una serie de resultados recientes para el problema de vectores bicromáticos no ortogonales (a menudo llamado el problema de búsqueda máxima de productos internos). Ver, por ejemplo, este documento y sus referencias.
fuente
Equivalencias:
Algoritmo ingenuo:
Respuesta a las preguntas (2) y (3):
Primer enfoque:
Segundo enfoque:
Tercer enfoque:
fuente