A associação de quarto de subconjunto pode ser decidida com eficiência de espaço?

Considere o seguinte problema de decisão. Seja e deixe ser adequado enumeração dos subconjuntos de que possuem no máximo elementos.$q = \sum_{i=0}^{n/4} \binom{n}{i}$$(C_0^n, C_1^n,\dots,C_{q-1}^n)$$\{0,1,\dots,n-1\}$$n/4$

Quartas-de-Subconjunto Membership
Entrada: tupla de inteiros não negativos representada em binário Pergunta: é ? $(i,j,n)$
$i \in C_j^n$

Ao escolher uma enumeração "legal" , a Associação de subconjuntos de trimestre pode ser decidida por uma máquina de Turing determinística usando não mais do que bits de espaço de trabalho, para todos os grandes o suficiente ?$(C_i^n)$$(0.99)n$$n$

Discussão

Seja $\log x = \log_2 x$ . É fácil enumerar todos os subconjuntos de no máximo $k$ elementos escolhidos dentre $n$ , acompanhando $k$ índices de tamanho $\lceil \log n \rceil$ bits cada. (Veja também a discussão na seção 7.2.1.3 de Knuth, TAOCP). Quando $k$ é constante, são apenas $O(\log n)$ bits. No entanto, se deixarmos $k = cn$ para alguma constante $c \le 1/4$ , esses esquemas de enumeração usarão o espaço $\Omega(n\log n)$ . Pode-se também usar um vetor característico de $n$ bits juntamente com uma verificação do número de bits definidos. Estou interessado em esquemas que batem $n$ bits.

Uma questão intimamente relacionada é então:

Para positivo satisfazendo a desigualdade , existe um código que representa subconjuntos de no máximo elementos escolhidos entre que usa bits para alguma constante e pode ser decodificado de forma eficiente?c log ( E ( 1 + c ) / c ) < 1 c n n d n d < $c$$c\log(e(1+c)/c) < 1$$cn$$n$$dn$$d < 1$

Observe que para grande o suficiente , e desde quando então a informação é teoricamente segue que seria alcançado com um código perfeito. (Isso é menor que se .) Portanto, estou procurando um código razoavelmente limpo que possa ser manipulado sem usar muito espaço.k ∑ i = 0 ($n$log ( n+k-

Para obter um código perfeito, pode-se escolher uma enumeração dos subconjuntos, executar um índice através da enumeração em ordem crescente e, em seguida, obter cada combinação decodificando o índice. No entanto, decodificar esse código quando parece exigir o uso de pelo menos bits de espaço para as enumerações que eu observei, como por meio de vetores característicos ordenados pelo aumento do peso de Hamming e, em seguida, lexicograficamente , ou via códigos Gray.$k \ge \Omega(n/\log n)$$n$

Pode haver uma maneira de fazer isso com espaço, mas acho que é mais provável que seja viável. ( 1 - ε ) $o(n)$$(1-\varepsilon)n$ Observe que, como , o limite inferior da teoria da informação já é bits, então isso realmente é sobre se pode ser alcançado por alguns . Um código que seja bom o suficiente (mas não necessariamente perfeito) parece ser suficiente para responder afirmativamente à minha pergunta. Também pode ser que a associação de quartos de subconjuntos possa ser decidida eficientemente sem construir explicitamente um código. Por outro lado, essa enumeração pode não existir: por exemplo, toda sequência de enumerações para valores deΩ ( n ) ( 1 - ε ) n ε > 0 n ( 1 - ε ) $\log \binom{n}{cn} \ge cn\log(1/c)$$\Omega(n)$$(1-\varepsilon)n$$\varepsilon > 0$$n$ pode ser inerentemente não uniforme, ou pode ser o caso de qualquer bits ser violado infinitamente com frequência.$(1-\varepsilon)n$

Suponho que, na discussão, você não esteja realmente interessado no espaço de trabalho conforme reivindicado, mas no espaço total, incluindo o tamanho da entrada. (Caso contrário, o esquema de codificação trivial de bits poderá ser decodificado no espaço logarítmico.)$n$

Seja uma constante suficientemente grande e considere o seguinte esquema de codificação para . Divida em blocos , , de tamanho cada, e coloque . A codificação de consiste na sequência dos seguintes números (escritos em binário) para cada :X ⊆ { 0 , … , n - 1 } { 0 , … , n - 1 } k B u u < k n / k X u = X ∩ B u X u < $k$$X\subseteq\{0,\dots,n-1\}$$\{0,\dots,n-1\}$$k$$B_u$$u<k$$n/k$$X_u=X\cap B_u$$X$$u<k$

• o tamanho;$s_u=|X_u|$

• o número correspondente a no sistema combinatório de números para subconjuntos .s $X_u$$s_u$

Quanto ao tamanho da codificação, assuma . Os números recebem bits, que serão desprezíveis. Temos para pelo menos dos 's, nesse caso a codificação de leva cerca de bits; o restante leva no máximo bits cada. O total é no máximo bits.s u S ( k log ( n / k ) ) s u ≤ n / ( 3 k ) k / 4 u X u H ( 1 / 3 ) $|X|\le n/4$$s_u$$O(k\log(n/k))$$s_u\le n/(3k)$$k/4$$u$$X_u$Xun/k0. 98$H(1/3)\tfrac nk\approx0{.}92n/k$$X_u$$n/k$$0{.}98n$

Decodificar equivale a decidir em qual bloco entra e depois descobrir ; o último pode ser feito facilmente no espaço e é possível reutilizar o espaço ocupado pelas codificações dos blocos restantes (desde que o espaço total seja pelo menos , o que é aceitável para grande o suficiente).X u n / k + O ( log n ) 2 n / k $i$$X_u$$n/k+O(\log n)$$2n/k$$k$

Uma análise melhor mostra que esse esquema alcança o espaço essencialmente : seja . Como , a média de sobre é no máximo . A codificação de leva cerca de bits. Agora, a função de entropia é côncava; portanto, a média de sobre é no máximo , e o espaço total é . Isso é ideal até .$H(1/4)n\approx0{.}812n$$p_u=s_u/(n/k)$$|X|/n\le1/4$$p_u$$u<k$$1/4$$X_u$$H(p_u)n/k$$H(p_u)$$u<k$$H(1/4)$$H(1/4)n+O(\log n)$$O(\log n)$

Obviamente, não há nada de especial em . O mesmo argumento mostra que, para qualquer constante , existe um esquema de codificação para os subconjuntos size de que usam bits e pode ser decodificado no local. Até certo ponto, ele pode até ser usado para subconjuntos de tamanho de que , obtendo um número não constante de blocos ( ou menos), mas a sobrecarga de fica mais acentuada e ultrapassa o termo principal quando cai abaixo aproximadamente .$1/4$$0<c<1/2$$\le cn$$\{0,\dots,n-1\}$$H(c)n+O(\log n)$$\le s(n)$$s(n)\ll n$$k\ge 2/H(s(n)/n)$s ( n ) $O(k\log(n/k))$$s(n)$$\sqrt n$