Dolne granice funkcji progowej

W złożoności drzewa decyzyjnego funkcji boolowskiej bardzo dobrze znaną metodą dolnej granicy jest znalezienie (przybliżonego) wielomianu reprezentującego funkcję. Paturi podał charakterystykę symetrycznych funkcji boolowskich (częściowych i całkowitych) pod względem oznaczonej ilości $\Gamma$ :

Twierdzenie ( Paturi ): Niech $f$ być dowolną niestałą funkcją symetryczną i oznaczać $f_k=f(x)$ kiedy $|x|=k$ (tj. masa młota wynosząca $x$ jest $k$ ). Przybliżony stopień $f$ , oznaczony $\widetilde{deg}(f)$ , jest $\Theta(\sqrt{n(n-\Gamma(f))})$ , gdzie $\Gamma(f)=\min\{|2k-n+1|:f_k\neq f_{k+1}\text{ and } 0\leq k\leq n-1\}$

Teraz niech będzie funkcją progową, tj. jeśli . W tym artykule (por. Sekcja 8, strona 15) napisano, że . $Thr_t(x)$ $Thr_t(x)=1$ $x\geq t$ $\widetilde{deg}(f)=\sqrt{(t+1)(N-t+1)}$

Zauważ, że dla funkcji progowej mamy, ponieważ gdy funkcja zmienia się z 0 na 1. Czy mam rację? $\Gamma(Thr_t)=|2(t-1)-n+1|$ $|x|=t-1$

Jeśli zastosuję bezpośrednio twierdzenie Paturiego do tej wartości , nie otrzymam dolnej granicy funkcji progowej podanej w innych artykułach. Czy wartość powyżej jest poprawna? czego mi brakuje? $\Gamma$ $\Gamma(Thr_t)$

Edycja: Próbowałem również obliczyć dolną granicę przeciwnika kwantowego dla progu. Najpierw przejrzyjmy twierdzenie.

Twierdzenie (nieważony przeciwnik kwantowy): Niech będzie częściową funkcją boolowską, a i będą podzbiorem (twardych) danych wejściowych. Niech będzie relacją i ustaw dla każdego . Niech oznaczają minimalną liczbę 1s odpowiednio w dowolnym wierszu i dowolnej kolumnie w relacji , a niech oznacza maksymalną liczbę jedynek odpowiednio w dowolnym wierszu i kolumnie w dowolnej relacji . Następnie . $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'}})$

Jeśli zdefiniuję jako zbiór wszystkich danych wejściowych o liczbie 1s większej lub równej , a wszystkie dane wejściowe o wartości 1 s ściśle mniejsze niż , otrzymam (po pewnej algebrze), że . $B$ $t$ $A$ $t$ $\frac{mm'}{\ell\ell'}=n^2 \ln(\frac{n}{t}) \ln(\frac{n}{n-t})$

Więc wciąż nie dostaję takich samych dolnych granic w innych artykułach. Porównajmy teraz te granice. Poniższy rysunek pokazuje dla i bez pierwiastków kwadratowych porównanie między twierdzeniem Paturiego związanym (niebieski), przeciwnikiem związanym (czerwony) i raportowanym związanym z innych prac (zielony). $n=200$

wprowadź opis zdjęcia tutaj

Moje pytania to:

1- Jak mogę zgłosić granicę w innych dokumentach?

2- Z rysunku widać, że dolna granica zgłoszona (zielona) także dolna granica Paturi i granica przeciwnika. Czy to nie osłabia „prawdziwej” dolnej granicy? Na przykład, jeśli Paturi mówi, że dla wszystkich funkcji symetrycznych mamy to ograniczenie, to jak można uzyskać pasującą górną granicę dla zliczania kwantowego ( )? Czy ta górna granica nie narusza twierdzenia Paturiego? $\sqrt{(t+1)(n-t+1)}$

— Marcos Villagra
źródło

Brakuje wartości bezwzględnej w obliczeniach dla (wydaje się, że jest to zbyt mała zmiana do edycji).

Γ (T h r_{t})

$\Gamma(Thr_t)$

— Hartmut Klauck

Myślę, że masz rację i jest to rodzaj przybliżenia wartościuzyskać stopień wymieniony w artykule. Wykresy funkcji pozwalają mi przypuszczać, że :)

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

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

— Marc Bury

tak, wydaje się to przybliżeniem (tutaj jest fabuła wolframalpha.com/input/… ). I to dolne granice . Jeśli tak, to po co to robić? Dlaczego nie zastosować wynikowej dolnej granicy z Paturi?

Γ (T h r_{t})

$\Gamma(Thr_t)$

— Marcos Villagra,

Przypuszczam, że chcą uniknąć funkcji wartości absolutnej. Uzyskują łatwiejszą formę funkcji i unikają analizy poszczególnych przypadków dla jakichkolwiek obliczeń. Interesuje mnie, w jaki sposób uzyskują to przybliżenie oryginalnej funkcji?

— Marc Bury,

To samo do stałej.

— Kristoffer Arnsfelt Hansen

Nie wiem, jak uzyskać lub zobaczyć granicę z oryginalnej granicy ale oto dowód, że granice te są asymptotycznie równe do stałego współczynnika: $\sqrt{(t+1)(n-t+1)}$ $\sqrt{n(n-\vert (2(t-1) -n+1 \vert )}$

Najpierw zobacz, że (wykluczam ponieważ funkcją progową jest zawsze ) $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.$

Określić , i . $f_1(t) = n(2t-1)$ $f_2(t) = n(2n-2t+1)$ $g(t) = (t+1)(n-t+1)$

Teraz musisz obliczyć maksymalną wartość (według określonych przedziałach) ułamków , , i . Możesz to zrobić za pomocą rachunku różniczkowego lub aproksymacji za pomocą wykresu ( wystarczająco duże): $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$

To daje ci a także pożądany wynik

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)}).$

Czy jest łatwiejszy sposób na zobaczenie / uzyskanie tego wyniku?

— Marc Bury
źródło

Tak, myślę, że masz rację. Mam wrażenie, że oryginalni autorzy wiedzieli o tej dolnej granicy z powodu niektórych wyników, takich jak kwantowanie. W wykreślaniu kwantowym mamy górną granicę , a stosując twierdzenie Paturiego i granice przeciwnika, pokazali oni to, co właśnie pokazaliście tutaj.

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

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

— Marcos Villagra,

Dziękuję za Twój wysiłek!! Myślę, że to jest odpowiedź. Jestem teraz bardziej przekonany, że może to jedyny sposób na uzyskanie tego wyniku.

— Marcos Villagra,