Dou-lhe uma lista de $n$ vetores de largura $k$ . Seu objetivo é retornar dois vetores de bits da lista que não possuem 1s em comum, ou então informar que esse par não existe.

Por exemplo, se eu fornecer $[00110, 01100, 11000]$ , a única solução é $\{00110, 11000\}$ . Alternativamente, a entrada $[111, 011, 110, 101]$ não tem solução. E qualquer lista que contenha o vetor zero de bits $000...0$ e outro elemento $e$ tem uma solução trivial $\{e, 000...0\}$ .

Aqui está um exemplo um pouco mais difícil, sem solução (cada linha é um vetor de bits, os quadrados pretos são 1s e os quadrados brancos são 0s):

■ ■ ■ ■ □ □ □ □ □ □ □ □ □
■ □ □ □ ■ ■ ■ □ □ □ □ □ □ 
■ □ □ □ □ □ □ ■ ■ ■ □ □ □
■ □ □ □ □ □ □ □ □ □ ■ ■ ■
□ ■ □ □ □ ■ □ □ □ ■ ■ □ □
□ ■ □ □ ■ □ □ □ ■ □ □ □ ■
□ ■ □ □ □ □ ■ ■ □ □ □ ■ □ <-- All row pairs share a black square
□ □ ■ □ □ □ ■ □ ■ □ ■ □ □
□ □ ■ □ □ ■ □ ■ □ □ □ □ ■
□ □ ■ □ ■ □ □ □ □ ■ □ ■ □
□ □ □ ■ ■ □ □ ■ □ □ ■ □ □
□ □ □ ■ □ □ ■ □ □ ■ □ □ ■
□ □ □ ■ □ ■ □ □ ■ □ □ ■ □

Qual a eficiência com que dois vetores de bits não sobrepostos podem ser encontrados ou demonstrados que não existem?

O algoritmo ingênuo, onde você apenas compara todos os pares possíveis, é $O(n^2 k)$ . É possível fazer melhor?

Aquecimento: bitvectors aleatórios

Como aquecimento, podemos começar com o caso em que cada vetor de bit é escolhido, de maneira uniforme, aleatoriamente. Acontece que o problema pode ser resolvido no tempo (mais precisamente, o 1.6 pode ser substituído pelo lg 3 ).$O(n^{1.6} \min(k, \lg n))$$1.6$$\lg 3$

Consideraremos a seguinte variante de dois conjuntos do problema:

Conjuntos dados de bitvectors, determinar onde existe um par não sobrepostos s ∈ S , t ∈ T .$S,T \subseteq \{0,1\}^k$$s \in S, t \in T$

A técnica básica para resolver isso é dividir e conquistar. Aqui está um algoritmo de tempo usando dividir e conquistar:$O(n^{1.6} k)$

1. Divida e T com base na posição do primeiro bit. Em outras palavras, a forma S 0 = { s ∈ S : s 0 = 0 } , S 1 = { s ∈ S : s 0 = 1 } , t 0 = { t ∈ T : t 0 = 0 } , T 1 = { t ∈ T : $S$$T$$S_0 = \{s \in S : s_0=0\}$$S_1 = \{s \in S : s_0 = 1\}$$T_0 = \{t \in T : t_0 = 0\}$ .$T_1 = \{t \in T : t_0 = 1\}$

2. Agora, procure recursivamente um par sem sobreposição de , de S 0 , T 1 e de T 1 , S 0 . Se qualquer chamada recursiva encontrar um par não sobreposto, produza-o; caso contrário, emita "Não existe um par sobreposto".$S_0,T_0$$S_0,T_1$$T_1,S_0$

Como todos os vetores de bits são escolhidos aleatoriamente, podemos esperar e | T b | ≈ | T | / 2 . Portanto, temos três chamadas recursivas e reduzimos o tamanho do problema em um fator de dois (ambos os conjuntos são reduzidos em tamanho por um fator de dois). Após a divisão de lg min ( | S | , | T | ) , um dos dois conjuntos é reduzido ao tamanho 1 e o problema pode ser resolvido em tempo linear. Temos uma relação de recorrência ao longo das linhas de$|S_b| \approx |S|/2$$|T_b| \approx |T|/2$$\lg \min(|S|,|T|)$ , cuja solução é T ( n ) = O ( n 1,6 k ) . Contabilizando o tempo de execução com mais precisão no caso de dois conjuntos, vemos que o tempo de execução é O ( min ( | S | , | T | ) 0,6 max ( | S | , |$T(n) = 3T(n/2) + O(nk)$$T(n) = O(n^{1.6} k)$ .$O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) k)$

Isso pode ser melhorado, observando que, se , a probabilidade de um par não sobreposto existir é exponencialmente pequena. Em particular, se x , y são dois vectores aleatórios, a probabilidade de que eles são não-sobreposição é ( 3 / 4 ) k . Se | S | = | T | = n , existem n 2 pares desse tipo; portanto, por um limite de união, a probabilidade de existir um par não sobreposto é no máximo n 2 ( $k \ge 2.5\lg n+100$$x,y$$(3/4)^k$$|S|=|T|=n$$n^2$ . Quando k ≥ 2,5 lg n + 100 , este é ≤ 1 / 2 100 . Portanto, como uma etapa de pré-processamento, se k ≥ 2,5 lg n + 100 , podemos retornar imediatamente "Não existe par não sobreposto" (a probabilidade de que isso esteja incorreto é insignificante pequeno), caso contrário, executamos o algoritmo acima.$n^2 (3/4)^k$$k \ge 2.5 \lg n+100$$\le 1/2^{100}$$k \ge 2.5 \lg n + 100$

Assim, alcançamos um tempo de execução de (ou O ( min ( | S | , | T | ) 0,6 max ( | S | , | T | ) min ( k , lg n ) ) para a variante de dois conjuntos proposta acima), para o caso especial em que os vetores de bits são escolhidos uniformemente aleatoriamente.$O(n^{1.6} \min(k, \lg n))$$O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) \min(k, \lg n))$

Obviamente, essa não é uma análise do pior caso. Os vetores de bits aleatórios são consideravelmente mais fáceis do que o pior caso - mas vamos tratá-lo como um aquecimento, para obter algumas idéias que talvez possamos aplicar ao caso geral.

Lições do aquecimento

Podemos aprender algumas lições com o aquecimento acima. Primeiro, dividir e conquistar (dividir em uma posição de bit) parece útil. Segundo, você deseja dividir em uma posição de bit com o máximo de nessa posição possível; quanto mais 0 houver, menor será a redução no tamanho do subproblema.$1$$0$

Em terceiro lugar, isto sugere que o problema fica mais difícil como a densidade de 's fica menor - se há muito poucos 1 é entre os bitvectors (eles são na sua maioria 0 's), os olhares problema muito difícil, já que cada divisão reduz o tamanho dos subproblemas um pouco. Portanto, defina a densidade Δ como a fração de bits que é 1 (ou seja, de todos os n k bits) e a densidade da posição de bit i como a fração de vetor de bits que é 1 na posição i .$1$$1$$0$$\Delta$$1$$nk$$i$$1$$i$

Manipulação de densidade muito baixa

Como próximo passo, podemos nos perguntar o que acontece se a densidade for extremamente pequena. Acontece que se a densidade em cada posição de bit for menor que , garantimos a existência de um par não sobreposto: existe um argumento de existência (não construtivo) mostrando que algum par não sobreposto deve existir. Isso não nos ajuda a encontrá-lo, mas pelo menos sabemos que ele existe.$1/\sqrt{k}$

Por que esse é o caso? Digamos que um par de vetores de bits esteja coberto pela posição do bit i se x i = y i = 1 . Observe que todo par de vetores de bits sobrepostos deve ser coberto por alguma posição de bit. Agora, se fixarmos uma posição de bit específica i , o número de pares que podem ser cobertos por essa posição de bit é no máximo ( n Δ ( i ) ) 2 < n 2 / k . Somando todos os $x,y$$i$$x_i=y_i=1$$i$$(n \Delta(i))^2 < n^2/k$$k$das posições de bits, descobrimos que o número total de pares cobertos por alguma posição de bit é . Isso significa que deve existir algum par que não esteja coberto por nenhuma posição de bit, o que implica que esse par não se sobrepõe. Portanto, se a densidade é suficientemente baixa em todas as posições de bits, certamente existe um par não sobreposto.$< n^2$

No entanto, não consigo identificar um algoritmo rápido para encontrar um par sem sobreposição, nesse regime, mesmo que um esteja garantido. Não vejo imediatamente nenhuma técnica que produza um tempo de execução que tenha uma dependência sub-quadrática de . Portanto, este é um bom caso especial para se concentrar, se você quiser gastar algum tempo pensando sobre esse problema.$n$

Em direção a um algoritmo de caso geral

No caso geral, uma heurística natural parece ser: escolher a posição de bit com o maior número de 1 's (isto é, com a mais alta densidade), e divisão sobre ele. Em outras palavras:$i$$1$

1. Encontre uma posição de bit que maximize Δ ( i ) .$i$$\Delta(i)$

2. Divida e T com base na posição do bit i . Em outras palavras, forma S 0 = { s ∈ S : s i = 0 } , S 1 = { s ∈ S : s i = 1 } , T 0 = { t ∈ T : t i = 0 } , T 1 = { t ∈ T $S$$T$$i$$S_0 = \{s \in S : s_i=0\}$$S_1 = \{s \in S : s_i = 1\}$$T_0 = \{t \in T : t_i = 0\}$ .$T_1 = \{t \in T : t_i = 1\}$

3. Agora, procure recursivamente um par sem sobreposição de , de S 0 , T 1 e de T 1 , S 0 . Se qualquer chamada recursiva encontrar um par não sobreposto, produza-o; caso contrário, emita "Não existe um par sobreposto".$S_0,T_0$$S_0,T_1$$T_1,S_0$

O desafio é analisar seu desempenho no pior dos casos.

Vamos supor que, como uma etapa de pré-processamento, primeiro calculemos a densidade de cada posição de bit. Além disso, se para cadai, assuma que a etapa de pré-processamento produz "Um par sobreposto existe" (percebo que isso não exibe um exemplo de par sobreposto, mas vamos deixar isso de lado como um desafio à parte). Tudo isso pode ser feito no tempoO(nk). As informações de densidade podem ser mantidas com eficiência, como fazemos chamadas recursivas; não será o principal contribuinte para o tempo de execução.$\Delta(i) < 1/\sqrt{k}$$i$$O(nk)$

Qual será o tempo de execução deste procedimento? Não tenho certeza, mas aqui estão algumas observações que podem ajudar. Cada nível de recursão reduz o tamanho do problema em cerca de bitvectors (por exemplo, denbitvectors paran-n/$n/\sqrt{k}$$n$ bitvectors). Portanto, a recursão só pode ser$n-n/\sqrt{k}$ níveis profundos. No entanto, não sei imediatamente como contar o número de folhas na árvore de recursão (há muito menos que3$\sqrt{k}$ sai), então não tenho certeza a que tempo de execução isso deve levar.$3^{\sqrt{k}}$

Solução mais rápida quando , usando a multiplicação de matrizes$n \approx k$

Suponha que . Nosso objetivo é melhorar o tempo de execução de O ( n 2 k ) = O ( n 3 ) .$n = k$$O(n^2k) = O(n^3)$

Podemos pensar nos vetores de bits e nas posições de bits como nós em um gráfico. Há uma aresta entre um nó de vetor de bits e um nó de posição de bit quando o vetor de bits tem um 1 nessa posição. O gráfico resultante é bipartido (com os nós que representam o vetor de bits de um lado e os nós que representam a posição de bits do outro) e possui nós de n .$n + k = 2n$

Dada a matriz de adjacência de um gráfico, podemos dizer se existe um caminho de dois saltos entre dois vértices ao quadrado M e verificando se a matriz resultante tem uma "aresta" entre esses dois vértices (ou seja, a entrada da aresta na matriz quadrada é diferente de zero). Para nossos propósitos, uma entrada zero na matriz de adjacência ao quadrado corresponde a um par de vetores de bits não sobrepostos (ou seja, uma solução). A falta de zeros significa que não há solução.$M$ $M$

O quadrado de uma matriz nxn pode ser feito no tempo , onde ω é conhecido por estar sob 2.373 e conjecturado como sendo 2 .$O(n^\omega)$$\omega$$2.373$$2$

Portanto, o algoritmo é:

• Converta os vetores de bits e posições de bits em um gráfico bipartido com nós e no máximo n k arestas. Isso leva tempo O ( n k ) .$n+k$$nk$$O(nk)$
• Calcule a matriz de adjacência do gráfico. Isso leva tempo e espaço.$O((n+k)^2)$
• Esquadre a matriz de adjacência. Isso leva tempo .$O((n+k)^\omega)$
• Pesquise a seção vetor de bits da matriz adjacente para zero entradas. Isso leva tempo .$O(n^2)$

A etapa mais cara é esquadrar a matriz de adjacência. Se , o algoritmo geral leva tempo O ( ( n + k ) ω ) = O ( n ω ) , o que é melhor que o tempo ingênuo de O ( n 3 ) .$n=k$$O((n+k)^\omega) = O(n^\omega)$$O(n^3)$

Essa solução também é mais rápida quando cresce não muito mais devagar e nem muito mais rápido que n . Enquanto k ∈ ohms ( n ω - 2 ) e k ∈ S ( n $k$$n$$k \in \Omega(n^{\omega-2})$, então(n+k)ωé melhor quen2k. Paraw≈2.373que se traduz emn0.731≤k≤n1.373(assintoticamente). Sewlimitar a 2, os limites serão ampliados paranϵ≤k≤n2-ϵ.$k \in O(n^\frac{2}{\omega-1})$$(n+k)^\omega$$n^2 k$$w \approx 2.373$$n^{0.731} \leq k \leq n^{1.373}$$w$$n^\epsilon \leq k \leq n^{2-\epsilon}$

Isso é equivalente a encontrar um vetor de bit que é um subconjunto do complemento de outro vetor; ou seja, seus 1s ocorrem apenas onde 0s ocorrem no outro.

Se k (ou o número de 1s ) for pequeno, você poderá obter tempo simplesmente gerando todos os subconjuntos do complemento de cada vetor de bit e colocando-os em um trie (usando o retorno). Se um vetor de bits for encontrado na árvore (podemos verificar cada um antes da inserção do complemento do subconjunto), teremos um par não sobreposto.$O(n2^k)$

Se o número de 1 ou 0 estiver limitado a um número ainda menor que k, o expoente poderá ser substituído por esse. A indexação de subconjunto pode ser em cada vetor ou em seu complemento, desde que a investigação use o oposto.

Há também um esquema para encontrar superconjuntos em uma tentativa que armazena apenas cada vetor apenas uma vez, mas faz pulos de bits durante análises pelo que acredito ser uma complexidade agregada semelhante; ou seja, possui inserção, mas o ( 2 k ) pesquisas.$o(k)$$o(2^k)$

Representam os vectores de bits como um matriz M . Tome i e j entre 1 e n .$n\times k$$M$$i$$j$$n$

, o produto escalar do i th e j th vector, é diferente de zero se, e apenas se, vectores i e j partes de um comum 1. Assim, para encontrar uma solução, calcular H H t e retorne a posição de uma entrada zero, se essa entrada existir.$(MM^T)_{ij}$$i$$j$$i$$j$$MM^T$

Complexidade

Usando multiplicação ingênua, isso requer operações aritméticas de . Se n = k , são necessárias operações O ( n 2,37 ) usando o algoritmo Coppersmith-Winograd totalmente impraticável, ou O ( n 2,8 ) usando o algoritmo Strassen. Se k = O ( n 0,302 ) , o problema pode ser resolvido usando as operações n 2 + o ( 1 ) .$O(n^2k)$$n=k$$O(n^{2.37})$$O(n^{2.8})$$k=O(n^{0.302})$$n^{2 + o(1)}$