ТЕОРЕТИЧЕСКИЕ ОСНОВЫ
ИНФОРМАТИКИ
УДК 004.312, 519.7
ВЕНТИЛЬНАЯ СЛОЖНОСТЬ ОБРАТИМЫХ СХЕМ
КАК МЕРА СЛОЖНОСТИ ЧЕТНЫХ ПОДСТАНОВОК
Д.В. Закаблуков
МГТУ им. Н.Э. Баумана, Москва, Российская Федерация
e-mail:
dmitriy.zakablukov@gmail.comРассмотрен вопрос сложности четных подстановок через оценку вентильной
сложности задающих их обратимых схем, состоящих из вентилей NOT, CNOT
и 2-CNOT. Доказано, что все четные подстановки на множестве
Z
n
2
задают-
ся обратимой схемой, не использующей дополнительные входы, с вентильной
сложностью, эквивалентной с точность до порядка
n
2
n
/
log
2
n
; оставшиеся
четные подстановки задаются обратимой схемой, не использующей дополни-
тельные входы, с меньшей вентильной сложностью. Установлено, что любая
четная подстановка на множестве
Z
n
2
реализуется обратимой схемой с вен-
тильной сложностью
.
2
n
+1
при использовании
∼
5
∙
2
n
/n
дополнительных
входов. Для всех четных подстановок применение дополнительных входов по-
зволяет снизить вентильную сложность реализующих их обратимых схем.
Ключевые слова
:
обратимые схемы, вентильная сложность, сложность четных
подстановок.
GATE COMPLEXITY OF REVERSIBLE CIRCUITS AS A MEASURE
OF EVEN PERMUTATION COMPLEXITY
D.V. Zakablukov
Bauman Moscow State Technical University, Moscow, Russian Federation
e-mail:
dmitriy.zakablukov@gmail.comThe 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
Z
n
2
set is implemented by the reversible circuit not using additional inputs with
the gate complexity equivalent up to about
n
2
n
/
log
2
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
Z
n
2
set is implemented
by the reversible circuit using
∼
5
∙
2
n
/n
additional inputs with the gate complexity
.
2
n
+1
. It is stated that for almost every even permutations the usage of additional
inputs allows to decrease gate complexity of reversible circuits implementing them.
Keywords
:
reversible circuits, gate complexity, even permutation complexity.
Введение.
В дискретной математике для оценки сложности того
или иного преобразования вводится мера сложности этого преобразо-
вания. В качестве меры сложности булевой функции зачастую рассма-
тривают вентильную сложность минимальной схемы, задающей эту
функцию. Впервые это было предложено К. Шенноном в работе [1],
с которой берет свое начало теория схемной сложности. В настоящее
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 1 67