Sensitivitas-Blok sensitivitas dugaan - Implikasi

Biarkan menjadi fungsi boolean dengan sensitivitas s ( f ) dan sensitivitas blok b s ( f ) .$f$$s(f)$$bs(f)$

Konjektur Sensitivitas-Blok sensitivitas menyatakan bahwa ada sehingga ∀ f , b s ( f ) ≤ s ( f ) c .$c>0$$\forall f,\mbox{ }bs(f)\leq s(f)^c$

Apa implikasi dari kebenaran dan kepalsuan dugaan ini?

Silakan mengutip referensi juga.

Inilah yang dikatakan Scott Aaronson tentang masalah ini:

$f$$f$$f$$f$$f$

Memeriksa literatur lain yang relevan tidak menawarkan implikasi menarik lainnya:

• Nisan dan Szegedy menjelaskan pertanyaan itu tetapi tidak memberikan motivasi sama sekali.
• Kenyon dan Kutin menyebutkan bahwa ini adalah "pertanyaan terbuka alami".
• Gotsman dan Linial memberikan masalah setara yang agak dibuat-buat (Conjecture 5.33 pada halaman 18 dari makalah berikut).
• P. Hatami, Kulkarni dan Pankratov , dalam survei komprehensif mereka tentang masalah ini, juga tidak menawarkan motivasi, tetapi mereka memiliki beberapa formulasi yang setara. Sebagai contoh, dugaan sensitivitas setara dengan dugaan bahwa kompleksitas keputusan paritas dari suatu fungsi secara polinomi terikat oleh sensitivitas. Dugaan 5.31 pada halaman 17, karena Shi, adalah salah satu reformulasi yang tidak menyebutkan sensitivitas sama sekali.
• Ambainis, Bavarian, Gao, Mao, Sun dan Zao menyatakan bahwa dugaan "berasal dari teori ukuran kompleksitas fungsi Boolean dan kompleksitas pohon keputusan", dan umumnya menawarkan jenis motivasi yang sama seperti yang dilakukan Scott Aaronson. Pracetak terbaru mereka adalah kata terakhir pada dugaan (per Desember 2014).

$\Omega( \log(s(f)) )$$f$$CREW(f)$$f$

$CREW(f) = \Omega(\log s(f))$

$CREW(f)$

$CREW(f) = \Theta(\log bs(f))$

$CREW(f) = O(\log s(f))$

$CREW(f)$