Вопросы с тегом «circuit-families»

40
Обведите нижние границы над произвольными наборами вентилей

В 1980-х годах Разборов, как известно, показал, что существуют явные монотонные булевы функции (такие как функция CLIQUE), которые требуют экспоненциально большого количества вентилей AND и OR для вычисления. Однако базис {AND, OR} над булевой областью {0,1} является лишь одним примером интересного...

39
Чем интересны ворота mod_m?

Райан Уильямс только что опубликовал свою нижнюю границу для ACC , класса задач, которые имеют контуры постоянной глубины с неограниченным разветвлением и вентилями AND, OR, NOT и MOD_m для всех возможных m. Что особенного в воротах MOD_m? Они позволяют имитировать арифметику над любым кольцом Z_m....

27
Решать, есть ли NC

Я хотел бы спросить о частном случае вопроса « Решение, вычисляет ли данная схема NC 0 перестановку » QiCheng, который остался без ответа. Булева схема называется цепью NC 0 k , если синтаксически каждый выходной вентиль зависит не более чем от k входных вентилей. (Мы говорим, что выходной вентиль...

14
Малые цепи для задачи оценки цепи

Пусть будет функцией, которая отображает схему s- гейта C на n битов и n- битную строку x на C ( x ) . Предположим, что схемы кодируются как ациклическая последовательность назначений k : = g ( i , j ), где i , j , k - метки проводов.C i r c u i t E v a lс , нСярсUяTЕvaLs,N\mathsf{CircuitEval}_{s,...

13
Схемы с оракулами против машин Тьюринга с оракулами

Проще говоря: как соотносятся машины Тьюринга с оракулами и семействами однородных цепей с оракулами? Как последние определяются для получения той же вычислительной модели для данной машины оракула Тьюринга? Это может быть элементарный вопрос, но не очевидно, где искать, и я из тех людей, которым...

13
Сложность схемы функции большинства

Пусть - мажоритарная функция, т.е. f ( x ) = 1 тогда и только тогда, когда ∑ n i = 1 x i > n / 2 . Мне было интересно, есть ли простое доказательство следующего факта (под «простым» я подразумеваю не полагаться на вероятностный метод, как это сделал Valiant 84, или на сортировку сетей;...

11
Существует ли конечный унитарный набор затворов, который может точно реализовать все КТП порядка

Я рассматриваю идеи о точных квантовых алгоритмах. В частности, я рассматриваю вероятные ограничения , который состоит из языков, которые можно точно определить с помощью многочастотных семейств квантовых цепей в произвольном множестве конечных элементов.EQPEQP\mathsf{EQP} Квантовое преобразование...