Como iterar sobre vetores em ordem de probabilidade no espaço pequeno

12

Considere um vetor dimensional v em que v i{ 0 , 1 } . Para cada i sabemos p i = P ( v i = 1 ) e vamos assumir o v i são independentes. Usando essas probabilidades, existe uma maneira eficiente de iterar sobre vetores binários n dimensionais, na ordem do mais provável para o menos provável (com opções arbitrárias de vínculos) usando o espaço sublinear no tamanho da saída? nvvi{0,1}ipi=P(vi=1)vin

Tomemos, por exemplo, . O vetor mais provável é ( 1 , 0 , 1 ) e o menos provável é { 0 , 1 , 0 } . p={0.8,0.3,0.6}(1,0,1){0,1,0}

Para muito pequeno , poderíamos rotular cada um dos 2 n vetores com sua probabilidade e simplesmente classificar, mas isso obviamente ainda não usaria espaço sublinear.n2n

Uma variante aproximada dessa pergunta foi feita anteriormente em /cs/24123/how-to-iterate-over-vectors-in-order-of-probability .

Lembik
fonte
Existe algum motivo para você não fazer a pergunta de acompanhamento também? A questão principal aqui é fazer isso no espaço sublinear?
Suresh Venkat
@SureshVenkat Sim, o problema é inteiramente sobre o espaço sublinear (no tamanho da saída). Perguntei aqui, pois acho que a pergunta pode ser muito difícil.
Lembik
Resolver isso no espaço e tempo parece exigir técnicas semelhantes ao SUBSET-SUM (saber rapidamente quais somas de subconjuntos quase cancelam somas diferentes). Portanto, é improvável que tenha uma solução rápida. poly(n)
Geoffrey Irving
@GeoffreyIrving Você acha que essa intuição pode ser mais formal?
Lembik

Respostas:

9

A seguir, é apresentado um algoritmo que usa aproximadamente tempo e 2 n / 2 de espaço.2n2n/2

Primeiro, vejamos o problema de classificar as somas de todos os subconjuntos de itens.n

Considere este subproblema: você tem duas listas classificadas de comprimento e gostaria de criar uma lista classificada das somas aos pares dos números nas listas. Você gostaria de fazer isso em aproximadamente O ( m 2 ) tempo (o tamanho da saída), mas em espaço sublinear. Podemos alcançar O ( m ) espaço. Mantemos uma fila de prioridade e extraímos as somas da fila de prioridade em ordem crescente.mO(m2)O(m)

Deixe as listas de ser e b 1 ... b m , classificados em ordem crescente. Tomamos as m somas a i + ba1amb1bmm , i = 1 ... m , e colocá-los em uma fila de prioridade.ai+b1i=1m

Agora, quando extraímos a menor soma restante da fila de prioridade, se j < m , então colocamos a soma a i + b j + 1 na fila de prioridade. O espaço é dominado pela fila de prioridade, que contém sempre a maioria m somas. E o tempo é O ( m 2 log m ) , já que usamos O ( log mai+bjj<mai+bj+1mO(m2logm) para cada operação na fila de prioridade. Isso mostra que podemos fazer o subproblema em O ( m 2O(logm) tempo e O ( m ) espaço.O(m2logm)O(m)

Agora, para classificar as somas de todos os subconjuntos de números, usamos apenas esta sub-rotina em que a listan é o conjunto de somas de subconjuntos da primeira metade dos itens, ea lista b i é o conjunto de somas de subconjuntos da segunda metade dos itens. Podemos encontrar essas listas recursivamente com o mesmo algoritmo.aibi

Vamos agora considerar o problema original. Seja o conjunto de coordenadas 0 e S 1 o conjunto de coordenadas 1 . Então Π i S 0 p ( v i = 0 ) Π i S 1S00S11

iS0p(vi=0)iS1p(vi=1)=1inp(vi=0)iS1p(vi=1)p(vi=0)=1inp(vi=0)exp(iS1logp(vi=1)p(vi=0)).

Classificar esses números é o mesmo que classificar os números , de modo que têm reduzido o problema para classificar os somas de subconjuntos de n itens.iS1logp(vi=1)logp(vi=0)n

Peter Shor
fonte
Existe uma redução plausível que tornaria uma solução poli-tempo / espaço implausível?
Lembik
Você provavelmente não terá uma solução que leva menos de 2n tempo, já que esse é o tamanho da saída (e minha solução leva tempo). Eu não tenho um bom limite inferior para o espaço, no entanto. n2n
Peter Shor
Obrigado. Eu não quis dizer tempo poli, é claro, mas algo linear no tamanho da saída e no espaço poli.
Lembik
4

Podemos fazer isso no espaço O(n)

  1. x{0,1}nO(n)r(x)xxp(x)>p(x)x{0,1}nxp(x)>p(x)r(x)x
  2. kxr(x)=kO(n)x{0,1}nxr(x)xr(x)=k
  3. k02n1kxr(x)=k

(Também devemos cuidar de possíveis laços, mas isso não é difícil.)

Yury
fonte
Obrigado. Isso é bastante um algoritmo lento no entanto :)
Lembik
0

Editar: esta resposta está incorreta. Veja os comentários para obter detalhes. ~ gandaliter

O(2n)O(n)

  1. (i,pi)|0.5pi|

  2. vvi1pi>0.50vviv .

  3. Chame essa função recursiva na lista classificada e um vetor vazio.

010.5

O(2n)O(n)nO(2n)O(n)O(2n)etapas de tempo. Portanto, esse algoritmo é a complexidade do pior caso ideal.

gandaliter
fonte
Θ(2n)
Obrigado. Eu claramente não li com atenção o suficiente! Eu editei minha resposta.
gandaliter
3
v1=12n1v1=1pi=0.5
Você está certo, isso não funciona. Desculpe!
gandaliter