Boolesche Funktionen, bei denen die Empfindlichkeit der Blockempfindlichkeit entspricht

16

Einige der Arbeiten zur Empfindlichkeit im Vergleich zur Blockempfindlichkeit zielten darauf ab, Funktionen mit einer möglichst großen Lücke zwischen s(f) und bs(f) zu untersuchen, um die Vermutung aufzulösen, dass bs(f) nur polynomiell größer ist als s(f) . Was ist mit der Gegenrichtung? Was ist über Funktionen mit s(f)=bs(f) ?

Trivialerweise haben konstante Funktionen 0=s(f)=bs(f) . Ebenfalls trivialerweise hat jede Funktion mit s(f)=n auch s(f)=bs(f) . Es ist nicht trivial, aber nicht zu schwer zu zeigen, dass jede monotone Funktion auch diese Gleichheit erfüllt. Gibt es andere nette Klassen von Funktionen, die s(f)=bs(f)? Eine vollständige Charakterisierung wäre ideal. Was ist, wenn wir die Anforderungen an s0(f)=bs0(f) und s1(f)=bs1(f) ?

Die Motivation für diese Frage besteht einfach darin, sich ein Bild davon zu machen, wie die Empfindlichkeit mit der Blockempfindlichkeit zusammenhängt.

Definitionen

Sei f:{0,1}n{0,1} eine Boolesche Funktion für n Bit-Wörter. Für x{0,1}n und A{0,1,,n} bezeichne xA das n Bit-Wort, das aus x durch Spiegeln der durch A angegebenen Bits erhalten wird . Für den Fall, dass A={i} , wir bezeichnen dies einfach alsxi .

Wir definieren die Empfindlichkeit von f bei x als s(f,x)=#{i|f(xi)f(x)} . Mit anderen Worten, es ist die Anzahl der Bits in x , die wir kippen können, um die Ausgabe von f zu kippen . Wir definieren die Empfindlichkeit von f als s(f)=maxxs(f,x).

Wir definieren die Blockempfindlichkeit von f bei x (bezeichnet mit bs(f,x) ) als das Maximum k so dass disjunkte Teilmengen B1,B2,,Bk von {1,2,,n} wie z daß f(xBi)f(x) . Wir definieren die Blockempfindlichkeit vonf alsbs(f)=maxxbs(f,x) .

Schließlich definieren wir die 0-Empfindlichkeit von f als s0(f)=max{s(f,x)|f(x)=0} . Wir definieren in ähnlicher Weise 1-Empfindlichkeit , 0-Block-Empfindlichkeit und 1-Block-Empfindlichkeit , bezeichnet mit s1(f) , bs0(f) und bs1(f) jeweils.

mhum
quelle

Antworten:

16

Kürzlich habe ich bewiesen, dass s (f) = bs (f) für Unate-Funktionen und Read-Once-Funktionen über die Booleschen Operatoren AND, OR und EXOR gilt, und meine Arbeit einschließlich der Ergebnisse wurde in TCS 2014 aufgenommen. ( Http: // dx .doi.org / 10.1007 / 978-3-662-44602-7_9 )

Möglicherweise greifen Sie dieses Problem an. Wenn ja, tut es mir leid, aber ich habe begonnen, das Problem selbständig anzugreifen, bevor die Frage veröffentlicht wurde. Eine vorläufige Version meines Papiers wurde auf einem japanischen Inlandstreffen im Dezember 2013 vorgestellt und die Einreichungsfrist war Oktober 2013. ( http://www.ieice.org/ken/paper/20131220DBID/eng/ )

Hiroki Morizumi
quelle
2
Nettes Ergebnis. Ich freue mich darauf, es zu lesen.
mhum