6 / 16
Обозначим через
k
чиcло подряд идущих вентилей в схеме. При
k
=
o
(
n
)
и
k
=
o
(
s
)
, можно утверждать на основании условия эквива-
лентности обратимых схем, что
C
(
n, s
)
6
r
s
+1
−
1
(
k
!)
b
s/k
c
(
r
−
1)
6
r
s
+1
−
1
(
k
!)
(
s/k
)
−
1
(
r
−
1)
.
(2)
Число всех четных подстановок на множестве
Z
n
2
равно
|
A
(
Z
n
2
)
|
=
= (2
n
)!
/
2
. По формуле Стирлинга
x
!
&
(
x/e
)
x
. Оценим величину
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
.
Согласно формуле (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
.
Выберем значение
s
так, чтобы выполнялось условие
log
2
(
C
(
n, s
)
/
|
A
(
Z
n
2
)
|
)
6
−
log
2
n
. Пусть
k
=
n/
log
2
n
, тогда
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
−
−
2
n
log
2
n
+
n
−
n
log
2
log
2
n
log
2
n
−
n
2
n
=
−
log
2
n
;
s
=
n
2
n
+
o
(
n
2
n
)
2 log
2
n
+
o
(log
2
n
)
.
Очевидно, что при таком значении
s
величина
log
2
(
C
(
n, s
)
/
|
A
(
Z
n
2
)
|
)
→
→ −∞
при
n
→ ∞
, т.е. доля четных подстановок, которые задаются
обратимой схемой, состоящей из вентилей множества
Ω
2
n
и не исполь-
зующей дополнительные входы, с вентильной сложностью менее
s
,
стремится к нулю.
Следует отметить, что при указанном выборе значений
s
и
k
вы-
полняются условия
k
=
o
(
n
)
,
k
=
o
(
s
)
, таким образом, применение
формулы (2) корректно. Тогда
s
∼
n
2
n
−
1
/
log
2
n
, откуда следует истин-
ность утверждения теоремы.
I
Асимптотическая верхняя оценка вентильной сложности.
В ра-
боте [7] был предложен алгоритм синтеза обратимых схем, состоящих
72 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1