Funções booleanas em que a sensibilidade é igual à sensibilidade do bloco

Parte do trabalho sobre sensibilidade versus sensibilidade de bloco tem como objetivo examinar funções com o maior espaço possível entre e , a fim de resolver a conjectura de que é polinomialmente maior que . E a direção oposta? O que se sabe sobre funções em que s (f) = bs (f) ?$s(f)$$bs(f)$$bs(f)$$s(f)$$s(f) = bs(f)$

Trivialmente, funções constantes têm $0=s(f)=bs(f)$ . Também trivialmente, qualquer função com $s(f) = n$ também tem $s(f) = bs(f)$ . Não é trivial, mas não é muito difícil mostrar que qualquer função monótona também satisfaz essa igualdade. Existem outras boas classes de funções que possuem $s(f) = bs(f)$ ? Uma caracterização completa seria ideal. E se fortalecermos ainda mais os requisitos para $s^0(f) = bs^0(f)$ e $s^1(f) = bs^1(f)$ ?

A motivação para esta pergunta é simplesmente obter alguma intuição sobre como a sensibilidade se relaciona com a sensibilidade do bloco.

Definições

Seja uma função booleana em palavras de bits. Para e , deixe denotar a palavra de bits obtida de invertendo os bits especificados por . No caso de , simplesmente denotaremos isso como .$f:\{0,1\}^n\rightarrow \{0,1\}$$n$$x \in \{0,1\}^n$$A \subseteq \{0,1,\ldots,n\}$$x^A$$n$$x$$A$$A = \{i\}$$x^i$

Definimos a sensibilidade de em$f$$x$ como . Em outras palavras, é o número de bits em que podemos inverter para inverter a saída de . Definimos a sensibilidade de como . $s(f,x) = \# \{ i | f(x^i) \neq f(x)\}$$x$$f$$f$$s(f) = \text{max}_x s(f,x)$

Definimos a sensibilidade do bloco de em$f$$x$ (denominada ) como o máximo modo que existem subconjuntos disjuntos de tais que . Definimos a sensibilidade do bloco de como .$bs(f,x)$$k$$B_1, B_2, \ldots, B_k$$\{1,2,\ldots, n\}$$f(x^{B_i}) \neq f(x)$$f$$bs(f) = \text{max}_x bs(f,x)$

Por fim, definimos a sensibilidade 0 de como . Nós semelhante definir um-sensibilidade , sensibilidade 0-bloco , e um bloco de sensibilidade , denotado , , e , respectivamente.$f$$s^0(f) = \text{max} \{ s(f,x) | f(x) = 0 \}$$s^1(f)$$bs^0(f)$$bs^1(f)$

Recentemente, eu provei que s (f) = bs (f) para funções unificadas e funções de leitura única sobre os operadores booleanos AND, OR e EXOR, e meu trabalho, incluindo os resultados, foi aceito no TCS 2014. ( http: // dx .doi.org / 10.1007 / 978-3-662-44602-7_9 )

Você pode estar atacando esse problema. Nesse caso, sinto muito, mas comecei a atacar o problema independentemente antes de a pergunta ser publicada. Uma versão preliminar do meu trabalho foi apresentada em uma reunião doméstica japonesa em dez / 2013 e o prazo para envio era out / 2013. ( http://www.ieice.org/ken/paper/20131220DBID/eng/ )