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

17

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 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 s0 0(f)=bs0 0(f) e s1 1(f)=bs1 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 0,1 1}n{0 0,1 1}nx{0 0,1 1}nUMA{0 0,1 1,...,n}xUMAnxUMAUMA={Eu}xEu

Definimos a sensibilidade de emfx 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)=#{Eu|f(xEu)f(x)}xffs(f)=maxxs(f,x)

Definimos a sensibilidade do bloco de emfx (denominada ) como o máximo modo que existem subconjuntos disjuntos de tais que . Definimos a sensibilidade do bloco de como .bs(f,x)kB1 1,B2,...,Bk{1 1,2,...,n}f(xBEu)f(x)fbs(f)=maxxbs(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.fs0 0(f)=max{s(f,x)|f(x)=0 0}s1 1(f)bs0 0(f)bs1 1(f)

mhum
fonte

Respostas:

17

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/ )

Hiroki Morizumi
fonte
2
Bom resultado. Estou ansioso para lê-lo.
Mhum 29/08/14