Hipoteza wrażliwości blokowej - implikacje

Niech będzie funkcją logiczną o czułości s ( f ) i czułości bloku b s ( f ) .$f$$s(f)$$bs(f)$

Hipoteza domniemania czułości według bloku czułości stwierdza, że ​​istnieje takie, że ∀ f , b s ( f ) ≤ s ( f ) c .$c>0$$\forall f,\mbox{ }bs(f)\leq s(f)^c$

Jakie są implikacje prawdy i fałszu tej przypuszczenia?

Podaj także referencje.

Oto, co Scott Aaronson ma do powiedzenia na ten temat:

Interesujące jest to, że wrażliwość bloków jest wielomianowo powiązana z ogromną liczbą innych interesujących miar złożoności: złożoność drzewa decyzyjnego , złożoność certyfikatu f , złożoność losowych zapytań f , kwantowa złożoność zapytań z F , stopień f jako prawdziwy wielomianu, to nazwę. Jeśli więc, jak się przypuszcza, czułość i czułość bloku są wielomianowo powiązane, to czułość - prawdopodobnie najbardziej podstawowa ze wszystkich miar złożoności funkcji logicznej - przestaje być wartością odstającą i dołącza do dużej i szczęśliwej trzody.$f$$f$$f$$f$$f$

Sprawdzenie innej odpowiedniej literatury nie daje żadnych innych istotnych konsekwencji:

• Nisan i Szegedy opisują to pytanie, ale nie dają żadnej motywacji.
• Kenyon i Kutin wspominają, że jest to „naturalne pytanie otwarte”.
• Gotsman i Linial podają nieco wymyślony równoważny problem (Przypuszczenie 5.33 na stronie 18 poniższej pracy).
• P. Hatami, Kulkarni i Pankratov w obszernej ankiecie dotyczącej problemu również nie dają motywacji, ale mają kilka równoważnych sformułowań. Na przykład domysł czułości jest równoważny domysłowi, że złożoność decyzji parzystości funkcji jest wielomianowo ograniczona przez czułość. Hipoteza 5.31 na stronie 17, ze względu na Shi, jest jedną przeformułowaniem, która wcale nie wspomina o wrażliwości.
• Ambainis, Bavarian, Gao, Mao, Sun i Zao twierdzą, że przypuszczenie „wywodzi się z teorii miar złożoności funkcji boolowskich i złożoności drzewa decyzyjnego” i ogólnie oferuje ten sam rodzaj motywacji, co Scott Aaronson. Ich najnowszy przedruk jest ostatnim słowem na przypuszczeniu (stan na grudzień 2014 r.).

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