Funkcje boolowskie, w których czułość jest równa czułości bloku

Część pracy nad czułością w porównaniu do czułości bloku miała na celu zbadanie funkcji z możliwie największą luką między $s(f)$ i $bs(f)$ w celu rozstrzygnięcia przypuszczenia, że $bs(f)$ jest tylko wielomianowo większy niż $s(f)$ . Co z przeciwnym kierunkiem? Co wiadomo o funkcjach, w których $s(f) = bs(f)$ ?

Trywialnie, funkcje stałe mają $0=s(f)=bs(f)$ . Również trywialnie, każda funkcja z $s(f) = n$ ma również $s(f) = bs(f)$ . Nie jest trywialne, ale nie za trudne wykazanie, że jakakolwiek funkcja monotoniczna spełnia również tę równość. Czy są jakieś inne ładne klasy funkcji, które mają $s(f) = bs(f)$? Idealna byłaby pełna charakterystyka. Co jeśli dalsze zwiększenie wymagań w $s^0(f) = bs^0(f)$ i $s^1(f) = bs^1(f)$ ?

Motywem tego pytania jest po prostu intuicja dotycząca tego, jak wrażliwość odnosi się do wrażliwości bloku.

Definicje

Niech $f:\{0,1\}^n\rightarrow \{0,1\}$ będzie funkcją boolowską dla $n$ bitowych słów. Dla $x \in \{0,1\}^n$ i ⊆ { 0 , 1 , ... , n } , niech x oznaczają n słów bitowych otrzymany z X odchylając bitów określone przez A . W przypadku, gdy A = {$A \subseteq \{0,1,\ldots,n\}$$x^A$$n$$x$$A$$A = \{i\}$ , po prostu oznaczymy to jako$x^i$ .

Definiujemy czułość $f$ at $x$ jako $s(f,x) = \# \{ i | f(x^i) \neq f(x)\}$ . Innymi słowy, jest to liczba bitów $x$ które możemy przerzucić, aby przerzucić wyjście $f$ . Określamy wrażliwość na $f$ w postaci $s(f) = \text{max}_x s(f,x)$.

Definiujemy czułość bloku $f$ at $x$ (oznaczoną $bs(f,x)$ ) jako maksimum $k$ tak że istnieją rozłączne podzbiory $B_1, B_2, \ldots, B_k$ z $\{1,2,\ldots, n\}$ takie że $f(x^{B_i}) \neq f(x)$ . Definiujemy czułość bloku na$f$ as$bs(f) = \text{max}_x bs(f,x)$ .

Wreszcie, określenia 0 wrażliwość na $f$ co $s^0(f) = \text{max} \{ s(f,x) | f(x) = 0 \}$ . Podobnie definiujemy 1-czułość , 0-blokową czułość i 1-blokową czułość , oznaczoną $s^1(f)$ , $bs^0(f)$ i $bs^1(f)$ odpowiednio.

Recently, I proved that s(f) = bs(f) for unate functions and read-once functions over the Boolean operators AND, OR and EXOR, and my paper including the results was accepted to TCS 2014. (http://dx.doi.org/10.1007/978-3-662-44602-7_9)

You may be attacking this problem. If so, I feel sorry, but I started to attack the problem independently before the question was posted. A preliminary version of my paper was presented at a Japanese domestic meeting in Dec/2013 and the submission deadline was Oct/2013. (http://www.ieice.org/ken/paper/20131220DBID/eng/)