Kann eine Quarter-Subset-Mitgliedschaft platzsparend entschieden werden?

Betrachten Sie das folgende Entscheidungsproblem. Sei $q = \sum_{i=0}^{n/4} \binom{n}{i}$ und sei $(C_0^n, C_1^n,\dots,C_{q-1}^n)$ geeignet Aufzählung der Teilmengen von $\{0,1,\dots,n-1\}$ mit höchstens $n/4$ Elementen.

Quarter-Subset Membership
Input: Tupel von nichtnegativen ganzen Zahlen $(i,j,n)$ binär dargestellt
Frage: ist $i \in C_j^n$ ?

Kann durch Auswahl einer "netten" Aufzählung $(C_i^n)$ die Quarter-Subset-Mitgliedschaft von einer deterministischen Turing-Maschine unter Verwendung von nicht mehr als $(0.99)n$ Bits Arbeitsbereich für alle ausreichend großen $n$ ?

Diskussion

Sei $\log x = \log_2 x$ . Es ist einfach, alle Teilmengen von höchstens $k$ aus n ausgewählten Elementen aufzulisten,$n$ indem $k$ Indizes der Größe $\lceil \log n \rceil$ Bits verfolgt werden. (Siehe auch die Diskussion in Knuths TAOCP-Abschnitt 7.2.1.3.) Wenn $k$ konstant ist, sind dies nur $O(\log n)$ Bits. Wenn wir jedoch $k = cn$ für eine Konstante $c \le 1/4$ , verwenden solche Aufzählungsschemata den $\Omega(n\log n)$ -Raum. Man kann auch einen $n$ Bit-Kennlinienvektor zusammen mit einer Überprüfung der Anzahl der gesetzten Bits verwenden. Ich interessiere mich für Schemata, die $n$ Bits schlagen .

Eine eng verwandte Frage lautet dann:

Für ein positives , das die Ungleichung erfüllt , gibt es einen Code, der Teilmengen von höchstens Elementen darstellt, die aus , die Bits für eine Konstante und sein können effizient dekodiert?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$

Man beachte , dass für ausreichend großen , und da wenn dann informationstheoretisch Daraus folgt, dass mit einem perfekten Code erreicht werden würde. (Dies ist weniger als wenn .) Ich suche daher nach einem einigermaßen sauberen Code, der ohne großen Speicherplatz kann.k ≤ i = 0 ($n$log ( n+k-

Um einen perfekten Code zu erhalten, könnte man eine Aufzählung der Teilmengen auswählen, einen Index in aufsteigender Reihenfolge durch die Aufzählung führen und dann jede Kombination durch Dekodieren des Index erhalten. Das Dekodieren eines solchen Codes, wenn anscheinend mindestens Bit Platz für die von mir betrachteten Aufzählungen erfordert , beispielsweise über charakteristische Vektoren, die durch Erhöhen des Hamming-Gewichts und dann lexikographisch geordnet sind oder über Gray-Codes.$k \ge \Omega(n/\log n)$$n$

Es könnte einen Weg geben, dies mit Raum zu tun , aber ich denke, dass eher machbar ist. $o(n)$$(1-\varepsilon)n$ Beachten Sie, dass seit die informationstheoretische Untergrenze bereits Bits beträgt. Es geht also wirklich darum, ob kann für einige . Ein Code, der nett genug (aber nicht unbedingt perfekt) ist, scheint zu genügen, um meine Frage zu bejahen. Es kann auch vorkommen, dass die Quarter-Subset-Mitgliedschaft effizient entschieden werden kann, ohne explizit einen Code zu erstellen. Andererseits existiert eine solche Aufzählung möglicherweise nicht: zum Beispiel jede Folge von Aufzählungen für Werte vonΩ(n)(1-ε)nε>0n(1-ε)$\log \binom{n}{cn} \ge cn\log(1/c)$$\Omega(n)$$(1-\varepsilon)n$$\varepsilon > 0$$n$ kann von Natur aus ungleichmäßig sein, oder es kann der Fall sein, dass eine Bit-Bindung unendlich oft verletzt werden muss.$(1-\varepsilon)n$

Ich gehe aus der Diskussion davon aus, dass Sie nicht wirklich an dem beanspruchten Arbeitsbereich interessiert sind , sondern am Gesamtraum einschließlich der Größe der Eingabe. (Andernfalls kann das triviale Bit-Codierungsschema im logarithmischen Raum decodiert werden.)$n$

Sei eine ausreichend große Konstante und betrachte das folgende Codierungsschema für . Teilen Sie in Blöcke , mit der Größe und setzen Sie . Die Codierung von besteht aus der Folge der folgenden Zahlen (binär geschrieben) für jedes :X ⊆ { 0 , … , n - 1 $k$$X\subseteq\{0,\dots,n-1\}$k B u u < k n / k X u$\{0,\dots,n-1\}$$k$$B_u$$u<k$$n/k$ X u < $X_u=X\cap B_u$$X$$u<k$

• die Größe;;$s_u=|X_u|$

• die Nummer, die im kombinatorischen Zahlensystem für Teilmengen mit Größe entspricht.s $X_u$$s_u$

Für die Größe der Codierung wird . Die Zahlen nehmen Bits, was vernachlässigbar ist. Wir haben für mindestens der , in welchem ​​Fall die Codierung von ungefähr Bits ; Die verbleibenden höchstens Bits. Die Summe beträgt höchstens Bits.s u$|X|\le n/4$$s_u$s u ≤ n / ( 3 k ) k / 4 $O(k\log(n/k))$$s_u\le n/(3k)$$k/4$$u$ H ( 1 / 3 ) $X_u$X$H(1/3)\tfrac nk\approx0{.}92n/k$$X_u$0 . 98 $n/k$$0{.}98n$

Das Dekodieren läuft darauf hinaus, zu entscheiden, in welchen Block gehe, und dann herauszufinden ; Letzteres kann leicht im Raum , und man kann den Raum, der durch Codierungen der verbleibenden Blöcke belegt wird, wiederverwenden (solange der Gesamtraum mindestens beträgt, was für Ordnung ist groß genug).X u n / k + O ( $i$$X_u$2 n / k $n/k+O(\log n)$$2n/k$$k$

Eine bessere Analyse zeigt, dass dieses Schema im Wesentlichen Raum : sei . Da , beträgt der Durchschnitt von über höchstens . Die Codierung von dauert ungefähr Bits. Nun ist die Entropiefunktion konkav, daher ist der Durchschnitt von über höchstens und der Gesamtraum ist . Dies ist bis zum optimal .p u = s u / ( n / k ) | X | / N ≤ 1 / 4 $H(1/4)n\approx0{.}812n$$p_u=s_u/(n/k)$$|X|/n\le1/4$ u < k 1 / 4 X u H ( p u ) n / k H / 4 ) H ( 1 / 4 ) $p_u$$u<k$$1/4$$X_u$$H(p_u)n/k$u < k H ( $H(p_u)$$u<k$$H(1/4)$$H(1/4)n+O(\log n)$$O(\log n)$

An ist natürlich nichts Besonderes . Das gleiche Argument zeigt, dass es für jede Konstante ein Codierungsschema für große Teilmengen von , das annimmt Bits und kann direkt dekodiert werden. Bis zu einem gewissen Grad kann es sogar für Teilmengen mit -Größe verwendet werden, wobei , indem eine nicht konstante Anzahl von Blöcken ( oder so), aber dann wird der Overhead von stärker und überholt den Hauptterm, wenn unter ungefähr fällt .0 < c < 1 / 2 ≤ C n { 0 , ... , N - 1 } H ( c $1/4$$0<c<1/2$$\le cn$$\{0,\dots,n-1\}$≤ s ( n ) s ( n ) « n k ≥ 2 / H $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$