Bisakah Keanggotaan Quarter-Subset ditentukan secara efisien?

Pertimbangkan masalah keputusan berikut. Biarkan dan biarkan menjadi cocok enumerasi himpunan bagian dari yang memiliki paling banyak elemen. $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$

Input Keanggotaan Quarter-Subset : tupel bilangan bulat non-negatif $(i,j,n)$ diwakili dalam biner
Pertanyaan: apakah $i \in C_j^n$ ?

Dengan memilih enumerasi "bagus" $(C_i^n)$ , dapatkah Keanggotaan Sub-Bagian ditentukan oleh mesin Turing deterministik menggunakan tidak lebih dari $(0.99)n$ bit ruang kerja, untuk semua cukup besar $n$ ?

Diskusi

Biarkan $\log x = \log_2 x$ . Sangat mudah untuk menghitung semua himpunan bagian dari elemen paling banyak $k$ dipilih dari $n$ dengan melacak indeks $k$ ukuran masing-masing $\lceil \log n \rceil$ bit. (Lihat juga diskusi di bagian TAOCP Knuth 7.2.1.3.) Ketika $k$ adalah konstan, ini hanya $O(\log n)$ bit. Namun, jika kita membiarkan $k = cn$ untuk beberapa konstanta $c \le 1/4$ , maka skema enumerasi seperti itu menggunakan ruang $\Omega(n\log n)$ . Satu juga dapat menggunakan vektor karakteristik $n$ bit bersama-sama dengan cek untuk jumlah bit yang ditetapkan. Saya tertarik pada skema yang mengalahkan $n$ bit.

Pertanyaan yang berkaitan erat adalah:

Untuk positif memuaskan ketimpangan , apakah ada kode yang mewakili himpunan bagian dari paling banyak elemen dipilih dari yang menggunakan bit untuk beberapa konstanta , dan dapat diterjemahkan secara efisien? $c$ $c\log(e(1+c)/c) < 1$ $cn$ $n$ $dn$ $d < 1$

Perhatikan bahwa untuk cukup besar , dan karena ketika maka informasi-secara teoritis mengikuti bahwa akan dicapai dengan kode yang sempurna. (Ini kurang dari jika .) Karena itu saya mencari kode yang cukup bersih yang dapat dimanipulasi tanpa menggunakan banyak ruang. $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$

Untuk mendapatkan kode yang sempurna, seseorang dapat memilih enumerasi himpunan bagian, menjalankan indeks melalui enumerasi dalam urutan yang meningkat, dan kemudian memperoleh setiap kombinasi dengan mendekode indeks. Namun, mendekode kode seperti itu ketika tampaknya memerlukan penggunaan setidaknya bit ruang untuk enumerasi yang telah saya lihat, seperti melalui vektor karakteristik yang dipesan dengan menambah berat Hamming dan kemudian secara leksikografis , atau melalui kode Gray. $k \ge \Omega(n/\log n)$ $n$

~~Mungkin ada cara untuk melakukan ini dengan ruang, tapi saya pikir lebih mungkin untuk dilakukan. $o(n)$ $(1-\varepsilon)n$~~ Perhatikan bahwa karena , informasi-teoretis batas bawah sudah bit, jadi ini benar-benar tentang apakah dapat dicapai untuk beberapa . Kode yang cukup bagus (tapi belum tentu sempurna) tampaknya sudah cukup untuk menjawab pertanyaan saya di afirmatif. Mungkin juga halnya Keanggotaan Quarter-Subset dapat diputuskan secara efisien tanpa membuat kode secara eksplisit. Di sisi lain, enumerasi semacam itu mungkin tidak ada: misalnya, setiap urutan enumerasi untuk nilai $\log \binom{n}{cn} \ge cn\log(1/c)$ $\Omega(n)$ $(1-\varepsilon)n$ $\varepsilon > 0$ $n$ mungkin secara inheren tidak seragam, atau mungkin terjadi bahwa setiap bit terikat harus sering dilanggar tanpa batas. $(1-\varepsilon)n$

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

Batas Anda sia-sia. Jika , maka , dan . Perhitungan yang sedikit lebih hati-hati (lihat misalnya mathoverflow.net/q/55585 ) menunjukkan bahwa sebenarnya , maka log-nya lagi . Tentu saja, untuk semua .

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 poin bagus, jadi pertanyaannya dapat diperluas ke Keanggotaan Setengah-Subset yang lebih umum, dan sebagian besar diskusi disederhanakan.

András Salamon

Saya berasumsi dari diskusi bahwa Anda sebenarnya tidak tertarik pada ruang kerja seperti yang diklaim, tetapi dalam ruang total termasuk ukuran input. (Kalau tidak, skema pengkodean bit sepele dapat didekodekan dalam ruang logaritmik.) $n$

Biarkan menjadi konstanta yang cukup besar, dan pertimbangkan skema penyandian berikut untuk . Pisahkan menjadi blok , , dengan ukuran $k$ $X\subseteq\{0,\dots,n-1\}$ $\{0,\dots,n-1\}$ $k$ $B_u$ $u<k$ $n/k$ masing-masing , dan masukkan . Pengkodean terdiri dari urutan angka-angka berikut (ditulis dalam biner) untuk setiap : $X_u=X\cap B_u$ $X$ $u<k$

ukuran; $s_u=|X_u|$
nomor sesuai dengan $X_u$ dalam sistem angka kombinatorial untuk himpunan s_u. $s_u$

Sedangkan untuk ukuran encoding, asumsikan . Angka mengambil bit, yang akan diabaikan. Kami memiliki untuk setidaknya dari , dalam hal mana pengkodean memakan waktu sekitar $|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$ bits; sisa - mengambil paling banyak bit. Totalnya adalah paling banyak bit. $X_u$ $n/k$ $0{.}98n$

Mengurai jumlah untuk menentukan blok mana yang masuki, dan kemudian mencari tahu $i$ $X_u$ ; yang terakhir dilakukan dengan mudah di ruang , dan kita dapat menggunakan kembali ruang yang ditempati oleh penyandian dari blok yang tersisa (selama total ruang setidaknya , yang OK untuk cukup besar). $n/k+O(\log n)$ $2n/k$ $k$

Analisis yang lebih baik menunjukkan bahwa skema ini menghasilkan ruang yang pada dasarnya : misalkan . Karena , rata-rata lebih dari paling banyak . Pengkodean membutuhkan waktu sekitar bit. Sekarang, fungsi entropi adalah cekung, maka rata-rata lebih dari paling banyak $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)$ , dan total ruang adalah . Ini optimal hingga . $H(1/4)n+O(\log n)$ $O(\log n)$

Tentu saja tidak ada yang istimewa tentang . Argumen yang sama menunjukkan bahwa untuk sembarang konstanta , ada skema penyandian untuk -ukuran subset dari yang mengambil bit, dan dapat didekodekan di tempat. Sampai batas tertentu, ia bahkan dapat digunakan untuk subset -ukuran mana lln , dengan mengambil jumlah blok yang tidak konstan ( atau lebih), tetapi kemudian overhead menjadi lebih jelas, dan menyusul istilah utama ketika turun di bawah kira-kira . $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
sumber

Bisakah Keanggotaan Quarter-Subset ditentukan secara efisien?

Diskusi

Jawaban: