Batas bawah pada fungsi Ambang

Dalam kompleksitas pohon keputusan fungsi boolean, metode batas bawah yang sangat diketahui adalah untuk menemukan (perkiraan) polinomial yang mewakili fungsi. Paturi memberikan karakterisasi untuk fungsi simetris boolean (parsial dan total) dalam hal kuantitas yang dilambangkan : $\Gamma$

Teorema ( Paturi ): Misalkan menjadi fungsi simetris non-konstan, dan melambangkan saat (yaitu berat palu adalah ). Tingkat perkiraan , dilambangkan , adalah $f$ $f_k=f(x)$ $|x|=k$ $x$ $k$ $f$ $\widetilde{deg}(f)$ , di mana $\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\}$

Sekarang misalkan menjadi fungsi ambang, yaitu jika . Dalam makalah ini (lih. Bagian 8, halaman 15) mengatakan bahwa $Thr_t(x)$ $Thr_t(x)=1$ $x\geq t$ . $\widetilde{deg}(f)=\sqrt{(t+1)(N-t+1)}$

Perhatikan bahwa untuk fungsi threshold kita memiliki , karena ketika fungsinya berubah dari 0 ke 1. Apakah saya benar? $\Gamma(Thr_t)=|2(t-1)-n+1|$ $|x|=t-1$

Jika saya menerapkan langsung teorema Paturi ke nilai , saya tidak mendapatkan batas bawah pada fungsi ambang batas yang dilaporkan dalam makalah lain. Apakah nilai atas benar? Apa yang saya lewatkan? $\Gamma$ $\Gamma(Thr_t)$

Sunting: Saya juga mencoba menghitung batas bawah musuh kuantum untuk ambang batas. Pertama, mari kita tinjau teorema.

Teorema (Musuh Kuantum Tertimbang): Biarkan menjadi fungsi boolean parsial, dan biarkan dan menjadi subset dari input (keras). Biarkan menjadi relasi, dan atur untuk setiap $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\}$ . Mari menunjukkan jumlah minimal 1s dalam setiap baris dan setiap kolom dalam kaitannya masing-masing, dan biarkan menunjukkan jumlah maksimal yang di setiap baris dan kolom di salah satu hubungan masing-masing. Kemudian $1\leq i \leq n$ $m,m'$ $R$ $\ell,\ell'$ $R_i$ . $Q_2(f)=\Omega(\sqrt{\frac{m m'}{\ell \ell'}})$

Jika saya mendefinisikan sebagai himpunan semua input dengan jumlah 1s lebih besar dari atau sama dengan , dan semua input dengan 1s benar-benar kurang dari , saya mendapatkan (setelah beberapa aljabar) bahwa $B$ $t$ $A$ $t$ . $\frac{mm'}{\ell\ell'}=n^2 \ln(\frac{n}{t}) \ln(\frac{n}{n-t})$

Jadi saya masih belum mendapatkan batas bawah yang sama seperti yang dilaporkan di koran lain. Sekarang, mari kita bandingkan batasan-batasan ini. Gambar di bawah ini menunjukkan untuk dan tanpa akar kuadrat, perbandingan antara teorema terikat Paturi (biru), batas musuh (merah), dan ikatan yang dilaporkan dari makalah lain (hijau). $n=200$

masukkan deskripsi gambar di sini

Pertanyaan saya adalah:

1 - Bagaimana saya mendapatkan ikatan dilaporkan di koran lain?

2- Anda dapat melihat dari gambar, bahwa batas bawah yang dilaporkan (hijau) juga batas bawah batas Paturi dan batas musuh. Bukankah itu melemahkan batas bawah "nyata"? Misalnya, jika Paturi mengatakan bahwa untuk semua fungsi simetris kita memiliki batas ini, lalu bagaimana Anda bisa mendapatkan batas atas yang cocok untuk penghitungan kuantum ( )? Bukankah itu batas atas melanggar teorema Paturi? $\sqrt{(t+1)(n-t+1)}$

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

Γ (T h r_{t})

$\Gamma(Thr_t)$

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

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

Γ (T h r_{t})

$\Gamma(Thr_t)$

Saya kira mereka ingin menghindari fungsi nilai absolue. Mereka mendapatkan bentuk fungsi yang lebih mudah dan menghindari analisis kasus per kasus untuk perhitungan apa pun. Saya tertarik bagaimana mereka mendapatkan perkiraan ini dari fungsi aslinya?

Marc Bury

Itu sama sampai konstan.

Kristoffer Arnsfelt Hansen

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

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

$f_1(t) = n(2t-1)$ $f_2(t) = n(2n-2t+1)$ $g(t) = (t+1)(n-t+1)$

$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$

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

Apakah ada cara yang lebih mudah untuk melihat / mendapatkan hasil ini?

Marc Bury
sumber

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

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

terima kasih atas usaha anda !! Saya pikir ini jawabannya. Saya lebih yakin sekarang bahwa mungkin ini satu-satunya cara untuk mendapatkan hasil ini.

Marcos Villagra

Batas bawah pada fungsi Ambang

Jawaban: