¿Se puede decidir la membresía de un subconjunto trimestral de manera eficiente en el espacio?

Considere el siguiente problema de decisión. Deje y deje que sea adecuado enumeración de aquellos subconjuntos de que tienen como 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$

Entrada de membresía del subconjunto trimestral : tupla de enteros no negativos representados en binario Pregunta: ¿ es ? $(i,j,n)$
$i \in C_j^n$

Al elegir una enumeración "agradable" , ¿puede la Membresía de un Subconjunto de Cuartos ser decidida por una máquina de Turing determinista que utiliza no más de bits de espacio de trabajo, para todos los suficientemente grandes ? $(C_i^n)$ $(0.99)n$ $n$

Discusión

Deje . Es fácil enumerar todos los subconjuntos de, como máximo, elementos elegidos de mediante el seguimiento de índices de tamaño bits cada uno. (Consulte también la discusión en la sección 7.2.1.3 de TAOCP de Knuth.) Cuando es constante, esto es solo bits. Sin embargo, si dejamos para algún constante , entonces dichos esquemas de enumeración usan el espacio . También se puede usar un vector característico de bits junto con una verificación del número de bits establecidos. Estoy interesado en esquemas que superan bits. $\log x = \log_2 x$ $k$ $n$ $k$ $\lceil \log n \rceil$ $k$ $O(\log n)$ $k = cn$ $c \le 1/4$ $\Omega(n\log n)$ $n$ $n$

Una pregunta estrechamente relacionada es entonces:

Para positivo que satisface la desigualdad , ¿hay un código que represente subconjuntos de a lo sumo elementos elegidos de que use bits para alguna constante , y puede ser decodificado de manera eficiente? $c$ $c\log(e(1+c)/c) < 1$ $cn$ $n$ $dn$ $d < 1$

Tenga en cuenta que para suficientemente grande , y dado que cuando entonces la información teóricamente se deduce que se lograría con un código perfecto. (Esto es menos de si .) Por lo tanto, estoy buscando un código razonablemente limpio que pueda manipularse sin utilizar mucho espacio. $n$

\sum_{i = 0}^{k} (\binom{n}{i}) \leq ((\binom{n}{k})) = (\binom{n + k - 1}{k}),

$\sum_{i=0}^k\binom{n}{i} \le \left(\binom{n}{k}\right) = \binom{n+k-1}{k},$

\log (\binom{n + k - 1}{k}) \leq \log [(e (n + k - 1) / k)^{k}],

$\log\binom{n+k-1}{k} \le \log[(e(n+k-1)/k)^k],$

k = c n

$k = cn$

d \leq c \log (e (1 + c) / c)

$d \le c\log(e(1+c)/c)$

1

$1$

0 < c \leq 0.2728

$0 < c \le 0.2728$

Para obtener un código perfecto, uno podría elegir alguna enumeración de los subconjuntos, ejecutar un índice a través de la enumeración en orden creciente y luego obtener cada combinación decodificando el índice. Sin embargo, decodificar dicho código cuando parece requerir el uso de al menos bits de espacio para las enumeraciones que he visto, como a través de vectores característicos ordenados aumentando el peso de Hamming y luego lexicográficamente o mediante los códigos Gray. $k \ge \Omega(n/\log n)$ $n$

~~Puede haber una manera de hacer esto con espacio, pero creo que es más probable que sea factible. $o(n)$ $(1-\varepsilon)n$~~ Tenga en cuenta que dado que , el límite inferior teórico de la información ya es bits, por lo que realmente se trata de si se puede lograr para algunos . Un código que sea lo suficientemente bueno (pero no necesariamente perfecto) parecería ser suficiente para responder a mi pregunta afirmativamente. También podría darse el caso de que la Membresía de un subconjunto de trimestres se pueda decidir eficientemente sin construir explícitamente un código. Por otro lado, tal enumeración puede no existir: por ejemplo, cada secuencia de enumeraciones para valores de $\log \binom{n}{cn} \ge cn\log(1/c)$ $\Omega(n)$ $(1-\varepsilon)n$ $\varepsilon > 0$ $n$ podría ser intrínsecamente no uniforme, o podría ser el caso de que cualquier límite de bit deba romperse infinitamente a menudo. $(1-\varepsilon)n$

cc.complexity-theory coding-theory space-bounded space-complexity András Salamon
fuente

Tus límites son derrochadores. Si , entonces y . Un cálculo un poco más cuidadoso (véase, por ejemplo, mathoverflow.net/q/55585 ) muestra que en realidad , por lo tanto, su registro es nuevamente . Por supuesto, para todos los .

0 < c < 1 / 2

$0<c<1/2$

\log (\binom{n}{c n}) = H (c) n - \frac{1}{2} \log n + O (1)

$\log\binom n{cn}=H(c)n-\frac12\log n+O(1)$

\log (\sum_{i \leq c n} (\binom{n}{i})) \leq \log (n (\binom{n}{c n})) \leq H (c) n + \frac{1}{2} \log n + O (1)

$\log\left(\sum_{i\le cn}\binom ni\right)\le\log\left(n\binom n{cn}\right)\le H(c)n+\frac12\log n+O(1)$

\sum_{i \leq c n} (\binom{n}{i}) = O ((\binom{n}{c n}))

$\sum_{i\le cn}\binom ni=O\left(\binom n{cn}\right)$

H (c) n - \frac{1}{2} \log n + O (1)

$H(c)n-\frac12\log n+O(1)$

H (c) < 1

$H(c)<1$

c < 1 / 2

$c<1/2$

Emil Jeřábek

@ EmilJeřábek buen punto, por lo que la pregunta puede extenderse a la Membresía de medio subconjunto más general, y gran parte de la discusión simplificada.

András Salamon

Asumo por la discusión que no está realmente interesado en el espacio de trabajo como se afirma, sino en el espacio total, incluido el tamaño de la entrada. (De lo contrario, el esquema de codificación trivial de bits puede decodificarse en espacio logarítmico). $n$

Sea una constante suficientemente grande y considere el siguiente esquema de codificación para . Divida en bloques , , de tamaño cada uno, y ponga . La codificación de consiste en la secuencia de los siguientes números (escritos en binario) para cada : $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$

el tamaño; $s_u=|X_u|$
el número correspondiente a en el sistema de números combinatorios para los subconjuntos de tamaño . $X_u$ $s_u$

En cuanto al tamaño de la codificación, suponga . Los números toman bits, que serán insignificantes. Tenemos para al menos de las 's, en cuyo caso la codificación de toma aproximadamente bits; los restantes toman como máximo bits cada uno. El total es como máximo bits. $|X|\le n/4$ $s_u$ $O(k\log(n/k))$ $s_u\le n/(3k)$ $k/4$ $u$ $X_u$ $H(1/3)\tfrac nk\approx0{.}92n/k$ $X_u$ $n/k$ $0{.}98n$

La decodificación de cantidades a decidir qué bloque entra en, y luego averiguar ; esto último se puede hacer fácilmente en el espacio , y se puede reutilizar el espacio ocupado por las codificaciones de los bloques restantes (siempre que el espacio total sea al menos , lo cual está bien para lo suficientemente grande). $i$ $X_u$ $n/k+O(\log n)$ $2n/k$ $k$

Un mejor análisis muestra que este esquema logra el espacio esencialmente : let . Como , el promedio de sobre es como máximo . La codificación de toma aproximadamente bits. Ahora, la función de entropía es cóncava, por lo tanto, el promedio de sobre es como máximo , y el espacio total es . Esto es óptimo hasta el . $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)$

Por supuesto, no hay nada especial sobre . El mismo argumento muestra que para cualquier constante , hay un esquema de codificación para -size subconjuntos de que toma bits, y se pueden decodificar en el lugar. Hasta cierto punto, incluso puede usarse para subconjuntos de tamaño donde , tomando un número no constante de bloques ( o menos), pero luego la sobrecarga de vuelve más pronunciada y supera el término principal cuando cae por debajo de 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)$ $O(k\log(n/k))$ $s(n)$ $\sqrt n$

Emil Jeřábek
fuente

¿Se puede decidir la membresía de un subconjunto trimestral de manera eficiente en el espacio?

Discusión

Respuestas: