Bessere Untergrenzen als 3n für nicht-boolesche Funktionen?

17

Blums -Untergrenze ist die bekannteste Schaltkreisuntergrenze über die gesamte Basis für eine explizite Funktion f : { 0 , 1 } n{ 0 , 1 } , vgl. Juknas Antwort auf diese Frage für verwandte Ergebnisse.3n-Ö(n)f:{0,1}n{0,1}

Was sind die bekanntesten unteren Grenzen , wenn der Bereich von ist { 0 , 1 } m ? Erhalten wir insbesondere etwas Besseres für m = n oder für m = 2 ?f{0,1}mm=nm=2

Manu
quelle
1
studiert dieser Aufsatz das nicht? Über den von Goldreich Cook et al. Vorgeschlagenen
Einwegfunktionskandidaten

Antworten:

18

Nach der Arbeit A Lower Bound auf der Schaltkreisgröße über U 2 einer linearen Booleschen Funktion5n-Ö(n)U2 von Kulikov, Melanich und Mihajlin, wenn gibt es keine unteren Grenzen, die besser als 3 sind n - o ( n ) . Es wird auch ein Verfahren zum Erhalten von Funktionen beschrieben, für die eine untere Grenze von 4 n - o ( n ) gilt, wenn m = nm=Ö(n)3n-Ö(n)4n-Ö(n)m=n, basierend auf einem Ergebnis von Lamagne und Savage.

Kristoffer Arnsfelt Hansen
quelle
11

hier sind neue Ergebnisse zu dieser , sagte der 1 sein st in ~ 3 Jahrzehnte und einige kurzen Kommentar

vzn
quelle