RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika // Archive

Prikl. Diskr. Mat., 2013 Number 2(20), Pages 14–18 (Mi pdm407)

This article is cited in 7 papers

Theoretical Foundations of Applied Discrete Mathematics

Lower and upper bounds for the affinity order of transformations of Boolean vector spaces

S. P. Gorshkova, A. V. Dvinyaninovb

a Institute of Cryptography, Communications and Informatics, Moscow, Russia
b TVP, Moscow, Russia

Abstract: Let $\Phi_n$ be the set of all transformations of the Boolean vector space $V_n$. Affinity order of a mapping $F\in\Phi_n$ is the least order of the set $V_n$ partition with the property: for every its block there exists an affine mapping $A\colon V_n\to V_n$ being equivalent to $F$ on this block. Affinity order of $\Phi_n$ is the greatest order of $F\in\Phi_n$. Upper and lower bounds for the affinity order of $\Phi_n$ are given in the article. These results can be used for estimating complexity of some techniques in Boolean equations resolving.

Keywords: transformation of Boolean vector space, affine mapping, solution complexity of Boolean equations.

UDC: 510.52



© Steklov Math. Inst. of RAS, 2024