5 / 14
L
(
n
) = max
h
∈
A
(
Z
n
2
)
L
(
h
)
. Let us consider
L
∗
(
h
)
and
L
∗
(
n
)
in the same way
for reversible circuits using additional inputs.
Theorem 1.
L
(
n
)
&
n
2
n
−
1
/
log
2
n.
J
Now we will show that for almost all permutations
h
∈
A
(
Z
n
2
)
there is an equation
L
(
n
)
&
n
2
n
−
1
/
log
2
n
. Let us estimate the number of
reversible circuits composed of gates from
Ω
2
n
set and defining various even
permutations on
Z
n
2
set with
s
gate complexity. Let us denote this value by
C
∗
(
n, s
)
.
If
r
=
|
Ω
2
n
|
, then
C
∗
(
n, s
)
6
r
s
. We denote by
C
(
n, s
)
the total number
of all nonequivalent reversible circuits composed of gates from
Ω
2
n
set and
with the gate complexity not greater than
s
:
C
(
n, s
) =
s
X
i
=0
C
∗
(
n, i
)
6
6
r
s
+1
−
1
r
−
1
.
We denote by
k
the number of sequential gates in the circuit. Given
k
=
o
(
n
)
and
k
=
o
(
s
)
, it is possible to state, based on the criterion of
equivalence of the reversible circuits, that
C
(
n, s
)
6
r
s
+1
−
1
(
k
!)
s/k
(
r
−
1)
6
r
s
+1
−
1
(
k
!)
(
s/k
)
−
1
(
r
−
1)
.
(2)
The number of all even permutations on
Z
n
2
set is equal to
|
A
(
Z
n
2
)
|
=
= (2
n
)!
/
2
. Using the Stirling formula
x
!
&
(
x/e
)
x
, we estimate the value of
log
2
(
C
(
n, s
)
/
|
A
(
Z
n
2
)
|
)
:
log
2
C
(
n, s
)
|
A
(
Z
n
2
)
|
6
log
2
2
r
s
+1
(
k
!)
(
s/k
)
−
1
(
r
−
1)(2
n
)!
6
log
2
2
r
s
+1
e
2
n
+
s
−
k
k
s
−
k
(
r
−
1)2
n
2
n
;
log
2
C
(
n, s
)
|
A
(
Z
n
2
)
|
&
1 + (
s
+ 1) log
2
r
+ (2
n
+
s
−
k
) log
2
e
−
−
(
s
−
k
) log
2
k
−
log
2
(
r
−
1)
−
n
2
n
.
According to formula (1),
r
6
n
3
: log
2
C
(
n, s
)
|
A
(
Z
n
2
)
|
&
3
s
log
2
n
+
+2 (2
n
+
s
−
k
)
−
(
s
−
k
) log
2
k
−
n
2
n
.
Choose the value of
s
, so that
log
2
(
C
(
n, s
)
/
|
A
(
Z
n
2
)
|
)
6
−
log
2
n
. If
k
=
n/
log
2
n
, then:
3
s
log
2
n
+ 2 2
n
+
s
−
n
log
2
n
−
−
s
−
n
log
2
n
(log
2
n
−
log
2
log
2
n
)
−
n
2
n
=
−
log
2
n
;
s
(2 log
2
n
+ 2 + log
2
log
2
n
) + 2
n
+1
−
ISSN 0236-3933. HERALD of the BMSTU. Series “Instrument Engineering”. 2015. No. 1 71