Решение о том, что данная схема

Какова сложность решения, вычисляет ли схема с n входными битами и n выходными битами перестановку { 0 , 1 } n ? другими словами, является ли каждая строка битов в { 0 , 1 } n выходом схемы для некоторого входа? Это похоже на проблему, которая была изучена, но я не могу найти никаких ссылок.$\mathsf{NC}^0$$n$$n$$\{0,1\}^n$$\{0,1\}^n$

твердость

После вашего комментария по этому вопросу мы назовем схему, в которой каждый выходной бит зависит не более чем от k входных битов, «NC ⁰ _k- цепь». Используя этот термин, ваша задача является coNP-полной в случае NC ⁰ ₅ -контур . То есть следующая проблема является coNP-полной.

Экземпляр : логическая схема C с n входными битами и n выходными битами, где каждый выходной бит зависит максимум от пяти входных битов.
Вопрос : вычисляется ли отображение из {0,1} ⁿ в себя биективным Си ?

Как прокомментировал Каве, он явно присутствует в coNP, даже без ограничения количества входных битов, от которых зависит каждый выходной бит. Чтобы доказать твердость coNP, мы уменьшим 3SAT до дополнения к текущей проблеме. Основная идея сокращения та же, что и в работе [Dur94] Дюрана, о которой я упоминал в комментарии к вопросу, но в нашем случае все сокращение намного проще.

Учитывая формулу 3CNF φ с n переменными и m предложениями, мы строим булеву схему C с ( n + m ) входными битами и ( n + m ) выходными битами следующим образом. Мы обозначаем входные биты как x ₁ ,…, x _n , y ₁ ,…, y _m , а выходные биты - как x ′ ₁ ,…, x ′ _n , z ₁ ,…, z _m . Мы считаем, что входные биты х₁ ,…, x _n задают присвоение истинности n переменным в φ .

• x ′ _i = x _i для 1≤ i ≤ n . Таким образом, первые n битов ввода всегда копируются в первые n битов вывода.
• Для 1≤ i ≤ m , если i- е условие φ выполнено, то z _i = y _i ⊕ y _{i +1} , где нижний индекс интерпретируется по модулю m . В противном случае z _i = y _i .

Обратите внимание, что каждый выходной бит зависит не более чем от пяти входных битов. Я опускаю доказательство правильности сокращения, но ключевая идея (которую я позаимствовал из [Dur94]) заключается в том, что если φ выполнимо, а входные биты x ₁ ,…, x _n установлены в удовлетворительное присвоение φ , то м выходных биты г ₁ , ..., Z _м ограничены иметь четность, и , следовательно, схема не может быть перестановкой. С другой стороны, если входные биты x ₁ ,…, x _n установлены на неудовлетворительное назначение φ , то выходные биты z₁ ,…, z _m можно установить на что угодно; из-за этого, если φ неудовлетворительно, то схема является перестановкой.

уступчивость

С трактируемой стороны ваша проблема в P в случае NC ⁰ ₂ цепей. Это показано следующим образом. В общем, каждый выходной бит в булевой схеме для перестановки сбалансирован ; т. е. ровно половина входных строк устанавливает бит вывода на 1. Однако каждая сбалансированная булева функция от {0,1} ² до {0,1} является аффинной ; т.е. копия одного входного бита, XOR двух входных битов или их отрицание. Следовательно, мы можем сначала проверить, сбалансирован ли каждый выходной бит, а затем проверить биективность с помощью исключения Гаусса.

Я не знаю сложности в случае цепей NC ⁰ ₃ или цепей NC ⁰ ₄ .

Ссылки

[Dur94] Бруно Дюран. Обращение двумерных клеточных автоматов: некоторые результаты сложности. Теоретическая информатика , 134 (2): 387–401, ноябрь 1994. DOI: 10.1016 / 0304-3975 (94) 90244-5 .