Untergrenzen der Schwellenwertfunktion

In der Entscheidungsbaumkomplexität einer Booleschen Funktion besteht eine sehr bekannte Methode der unteren Grenze darin, ein (ungefähres) Polynom zu finden, das die Funktion darstellt. Paturi gab eine Charakterisierung für symmetrische boolesche (Teil- und Gesamt-) Funktionen in Form einer mit bezeichneten Größe an $\Gamma$ :

Satz ( Paturi ): Sei $f$ eine beliebige nicht konstante symmetrische Funktion und bezeichne $f_k=f(x)$ wenn $|x|=k$ (dh das Hamming-Gewicht von $x$ ist $k$ ). Der ungefähre Grad von $f$ , bezeichnet mit $\widetilde{deg}(f)$ , ist $\Theta(\sqrt{n(n-\Gamma(f))})$ $\Gamma(f)=\min\{|2k-n+1|:f_k\neq f_{k+1}\text{ and } 0\leq k\leq n-1\}$

Nun sei die Schwellenwertfunktion, dh wenn . In diesem Papier (siehe Abschnitt 8, Seite 15) , so dass . $Thr_t(x)$ $Thr_t(x)=1$ $x\geq t$ $\widetilde{deg}(f)=\sqrt{(t+1)(N-t+1)}$

Beachten Sie, dass für die Schwellenwertfunktion, denn wenn ist, ändert sich die Funktion von 0 auf 1. Habe ich recht? $\Gamma(Thr_t)=|2(t-1)-n+1|$ $|x|=t-1$

Wenn ich den Satz von Paturi direkt auf diesen Wert von , erhalte ich nicht die Untergrenze für die in anderen Veröffentlichungen angegebene Schwellenwertfunktion. Ist der Wert von oben korrekt? Was vermisse ich? $\Gamma$ $\Gamma(Thr_t)$

Bearbeiten: Ich habe auch versucht, die untere Grenze des Quantengegners für den Schwellenwert zu berechnen. Lassen Sie uns zunächst den Satz überprüfen.

Satz (ungewichteter Quantengegner): Sei eine partielle boolesche Funktion und sei und eine Teilmenge von (harten) Eingaben. Sei eine Beziehung und setze für jede . Sei die minimale Anzahl von Einsen in einer Zeile bzw. einer Spalte in Beziehung , und sei die maximale Anzahl von Einsen in einer Zeile und Spalte in einer der Beziehungen . Dann ist . $f$ $A\subseteq f^{-1}(0)$ $B\subseteq f^{-1}(1)$ $R\subseteq A\times B$ $R_i=\{(x,y)\in R : x_i\neq y_i\}$ $1\leq i \leq n$ $m,m'$ $R$ $\ell,\ell'$ $R_i$ $Q_2(f)=\Omega(\sqrt{\frac{m m'}{\ell \ell'}})$

Wenn ich als die Menge aller Eingaben mit einer Anzahl von 1s größer oder gleich und alle Eingaben mit 1s streng kleiner als , erhalte ich (nach einiger Algebra) das . $B$ $t$ $A$ $t$ $\frac{mm'}{\ell\ell'}=n^2 \ln(\frac{n}{t}) \ln(\frac{n}{n-t})$

Trotzdem bekomme ich nicht die gleichen Untergrenzen, die in anderen Zeitungen angegeben wurden. Vergleichen wir nun diese Grenzen. Die folgende Abbildung zeigt für und ohne Quadratwurzeln einen Vergleich zwischen dem Satz von Paturi (blau), der Bindung des Gegners (rot) und der von anderen Arbeiten angegebenen Bindung (grün). $n=200$

Geben Sie hier die Bildbeschreibung ein

Meine Fragen sind:

1- Wie kann ich die Bindung in anderen Zeitungen melden lassen?

2- Sie können der Abbildung entnehmen, dass die gemeldete Untergrenze (grün) auch die Untergrenze von Paturi und die Grenze des Gegners beträgt. Schwächt das nicht die "echte" Untergrenze? Wenn Paturi beispielsweise sagt, dass wir für alle symmetrischen Funktionen diese Grenze haben, wie können Sie dann eine passende Obergrenze für die Quantenzählung erhalten ( )? Verstößt diese Obergrenze nicht gegen Paturis Theorem? $\sqrt{(t+1)(n-t+1)}$

cc.complexity-theory quantum-computing lower-bounds boolean-functions query-complexity Marcos Villagra
quelle

Sie vermissen den absoluten Wert in der Berechnung für (dies scheint eine zu kleine Änderung für eine Bearbeitung zu sein).

Γ (T h r_{t})

$\Gamma(Thr_t)$

Hartmut Klauck

Ich denke, Sie haben Recht und es ist eine Art Annäherung an den absoluten Wertum den in der Zeitung genannten Abschluss zu erhalten. Die Darstellungen der Funktionen lassen mich das annehmen :)

Γ (T h r_{t}) = | 2 (t - 1) - n + 1 |

$\Gamma(Thr_t)=|2(t-1)-n+1|$

Marc Bury

Ja, es scheint eine Annäherung zu sein (hier ist die Handlung wolframalpha.com/input/… ). Und es Grenzen . Wenn ja, warum dann? Warum nicht einfach die resultierende Untergrenze von Paturi anwenden?

Γ (T h r_{t})

$\Gamma(Thr_t)$

Marcos Villagra

Ich nehme an, sie wollen die Absolutwertfunktion vermeiden. Sie erhalten eine einfachere Form der Funktion und vermeiden bei jeder Berechnung eine Einzelfallanalyse. Ich bin daran interessiert, wie sie diese Annäherung aus der ursprünglichen Funktion herausholen.

Marc Bury

Es ist das gleiche bis zu einer Konstanten.

Kristoffer Arnsfelt Hansen

Ich weiß nicht, wie Sie die Grenze von von der ursprünglichen Grenze aber hier ist der Beweis, dass diese Grenzen bis zu einem konstanten Faktor asymptotisch gleich sind: $\sqrt{(t+1)(n-t+1)}$ $\sqrt{n(n-\vert (2(t-1) -n+1 \vert )}$

Sehen Sie zuerst, dass (ich schließe weil die Schwellenwertfunktion immer ) $t = 0$ $1$

n (n - | (2 (t - 1) - n + 1 |) = {\begin{cases} n (2 t - 1) & 1 \leq t \leq n / 2 + 1 / 2 \\ n (2 n - 2 t + 1) & n / 2 + 1 / 2 \leq t \leq n - 1 \end{cases}

$n(n-\vert (2(t-1) -n+1 \vert) = \left\lbrace \begin{array}{ll} n(2t-1) & 1 \leq t \leq n/2+1/2\\ n(2n-2t+1) & n/2+1/2 \leq t \leq n-1 \end{array} \right.$

Definiere , und . $f_1(t) = n(2t-1)$ $f_2(t) = n(2n-2t+1)$ $g(t) = (t+1)(n-t+1)$

Nun müssen Sie den Maximalwert (nach innerhalb der definierten Intervalle) der Brüche , , und berechnen . Sie können dies mit Hilfe der Differentialrechnung oder der Approximation mit Hilfe des Graphen tun (wobei groß genug ist): $t$ $f_1(t)/g(t)$ $f_2(t)/g(t)$ $g(t)/f_1(t)$ $g(t)/f_2(t)$ $n$

$f_1(t)/g(t) \leq f_1(n/2+1/2)/g(n/2+1/2) \leq \dfrac{n^2}{n^2/4} = 4$

$f_2(t)/g(t) \leq f_2(n/2+1/2)/g(n/2+1/2) \leq \dfrac{n^2}{n^2/4} = 4$

$g(t)/f_1(t) \leq g(1)/f_1(1) = \dfrac{2n}{n} = 2$

$g(t)/f_2(t) \leq g(n-1)/f_2(n-1) = \dfrac{n/2}{n/3} \leq 3/2$

Dies ergibt und auch das gewünschte Ergebnis

n (n - | 2 (t - 1) - n - 1 |) = Θ ((t + 1) (n - t + 1))

$n(n-\vert 2(t-1)-n-1\vert) = \Theta((t+1)(n-t+1))$

\sqrt{n (n - | 2 (t - 1) - n - 1 |)} = Θ (\sqrt{(t + 1) (n - t + 1)}) .

$\sqrt{n(n-\vert 2(t-1)-n-1 \vert)} = \Theta(\sqrt{(t+1)(n-t+1)}).$

Gibt es eine einfachere Möglichkeit, dieses Ergebnis zu sehen / zu erhalten?

Marc Bury
quelle

Ja, ich denke du hast recht. Mein Eindruck ist, dass die ursprünglichen Autoren aufgrund einiger Ergebnisse wie Quantencouting von dieser Untergrenze wussten. Beim Quantencouting haben wir eine Obergrenze von , und durch Anwendung des Paturi-Theorems und der gegnerischen Grenzen haben sie gezeigt, was Sie gerade hier gezeigt haben.

\sqrt{(t + 1) (n - t + 1)}

$\sqrt{(t+1)(n-t+1)}$

Marcos Villagra

Danke für Ihr Bemühen!! Ich denke das ist die Antwort. Ich bin jetzt mehr davon überzeugt, dass dies vielleicht nur der Weg ist, um dieses Ergebnis zu erzielen.

Marcos Villagra

Untergrenzen der Schwellenwertfunktion

Antworten: