Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
On the Complexity of Computing Two Nonlinearity Measures
verfasst von : Magnus Gausdal Find
Erschienen in: Computer Science - Theory and Applications
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We study the computational complexity of two Boolean nonlinearity measures: the
nonlinearity
and the
multiplicative complexity
. We show that if one-way functions exist, no algorithm can compute the multiplicative complexity in time 2
O
(
n
)
given the truth table of length 2
n
, in fact under the same assumption it is impossible to approximate the multiplicative complexity within a factor of (2 −
ε
)
n
/2
. When given a circuit, the problem of determining the multiplicative complexity is in the second level of the polynomial hierarchy. For nonlinearity, we show that it is #
P
hard to compute given a function represented by a circuit.