GATE COMPLEXITY OF REVERSIBLE CIRCUITS AS A MEASURE OF EVEN PERMUTATION COMPLEXITY
The article discusses even permutation complexities via the evaluation of the gate complexity of reversible circuits consisting of NOT, CNOT and 2-CNOT gates, which implements these permutations. It is proved that almost every even permutation on the Zn set is implemented by the reversible circuit not using additional inputs with the gate complexity equivalent up to about n2n / log2 n; all other even permutations are implemented by reversible circuit not using additional inputs with the less gate complexity. It is established that every even permutation on the Zn set is implementedby the reversible circuit using ~ 5 ∙ 2n /n additional inputs with the gate complexity;S 2n+1. It is stated that for almost every even permutations the usage of additionalinputs allows to decrease gate complexity of reversible circuits implementing them