Let Ф п be the set of all transformations of the Boolean vector space Vn. Affinity order of a mapping Fg Ф п is the least order of the set Vn partition with the property: for every its block there exists an affine mapping A : Vn ^ Vn being equivalent to F on this block. Affinity order of Ф п is the greatest order of F G Ф п. Upper and lower bounds for the affinity order of Ф п are given in the article. These results can be used for estimating complexity of some techniques in Boolean equations resolving.
Download file
Counter downloads: 71
- Title Lower and upper bounds for the affinity order of transformations of boolean vector spaces
- Headline Lower and upper bounds for the affinity order of transformations of boolean vector spaces
- Publesher
Tomsk State University
- Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 2(20)
- Date:
- DOI
Keywords
solution complexity of Boolean equations, affine mapping, transformation of Boolean vector space, сложность решения систем булевых уравнений, аффинное отображение, преобразование пространства булевых векторовAuthors
References

Lower and upper bounds for the affinity order of transformations of boolean vector spaces | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2013. № 2(20).
Download full-text version
Download fileCounter downloads: 192