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

27

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

Булева схема называется цепью NC 0 k , если синтаксически каждый выходной вентиль зависит не более чем от k входных вентилей. (Мы говорим, что выходной вентиль g синтаксически зависит от входного вентиля g ′, когда в схеме имеется направленный путь от g ′ до g, рассматриваемый как направленный ациклический граф.)

В вышеупомянутом вопросе QiCheng спросил о сложности следующей проблемы, где k - это константа:

Экземпляр : цепь NC 0 k с n- битным входом и n- битным выходом.
Вопрос : Рассчитывает ли данная схема перестановку на {0, 1} n ? Другими словами, является ли функция, вычисляемая схемой, биекцией от {0, 1} n до {0, 1} n ?

Как Каве прокомментировал этот вопрос, легко увидеть, что проблема в coNP. В ответ я показал, что задача является coNP-полной для k = 5 и что она находится в P для k = 2.

Вопрос . Какова сложность для k = 3?

Пояснение 29 мая 2013 года : «Перестановка {0, 1} n » означает биективное отображение из {0, 1} n в себя. Другими словами, проблема заключается в том, является ли каждая n- битная строка выходом данной схемы для некоторой n- битной входной строки.

Цуёси Ито
источник
1
Личное примечание: Когда я отправил ответ на вопрос QiCheng, я сделал это только потому, что проблема выглядела интересной, без какого-либо конкретного применения. Через несколько месяцев я оказался в ситуации, когда мне пришлось кому-то объяснять, что совсем не просто решать, вычисляет ли данная программа перестановку или нет. Благодаря вопросу QiCheng, у меня был прекрасный пример (какое совпадение!). После этого мне стало интересно узнать о случаях k = 3 и k = 4. Я подозреваю, что случай k = 3 уже coNP-завершен, но я не смог доказать в любом случае.
Цуёси Ито
эта проблема, по-видимому, является частным случаем проблемы Pigeonhole Circuit, определенной Пападимитриу ( sciencedirect.com/science/article/pii/S0022000005800637 ), которая является полной для PPP в отношении сокращения времени между задачами поиска.
Маркос Вильягра
@Marcos Villagra: Спасибо за комментарий, но я боюсь, что, говоря «особый случай», вы значительно меняете определение проблемы Pigeonhole Circuit. Важным свойством проблемы Pigeonhole Circuit является то, что это проблема полного поиска, тогда как текущая проблема (рассматриваемая как проблема поиска для двух входов, которые выдают одинаковый результат) не является проблемой полного поиска.
Цуеши Ито

Ответы:

3

Эта проблема с является сложной для coNP (и, следовательно, coNP-полной).k=3

Чтобы доказать это, я уменьшу от 3-SAT до дополнения к этой задаче (для данной цепи эта схема выполняет небиективную функцию).NC30

Сначала предварительное определение, которое будет полезно:

Мы помечаем помеченный граф как ориентированный граф, некоторые ребра которого помечены литералами со свойством, что каждая вершина имеет либо одно немеченое входящее ребро, одно помеченное входящее ребро, либо два немеченых входящих ребра.

Снижение

Предположим, у нас есть 3-SAT формула состоящая из m предложений, каждое из которых содержит три литерала. Первым шагом является построение помеченного графа G из ϕ . Этот помеченный граф содержит одну копию следующего гаджета (извините за ужасную диаграмму) для каждого предложения в ϕ . Три ребра, помеченные как L1, L2 и L3, вместо этого помечены литералами в предложении.ϕmGϕϕ

   |
   |               |
   |               |
   |               O<-----\
   |               ^      |
   |               |      |
   |               |      |
   |        /----->O      |
   |        |      ^      |
   |        |      |      |
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |L1    |L2    |L3
   |        |      |      |
   |        O      O      O
   |        ^      ^      ^
   |        |      |      |
   |        |      |      |
   |        \------O------/
   |               ^
   |               |
   |               |
   |               O
   |               ^
   |               |
   |

Все гаджеты (по одному на каждое предложение) расположены в один большой цикл, причем нижняя часть одного гаджета связана с верхней частью следующего.

Обратите внимание, что это расположение гаджетов фактически формирует помеченный граф (каждая вершина имеет степень 1 или 2, причем только ребра приводят к маркировке вершин степени 1).

Из формулы и помеченного графа G (который был построен из ϕ ) мы затем построим схему N C 0 3 (это завершит редукцию). Количество входов и выходов для этой схемы п + V , где п есть число переменных в ф и V является числом вершин в G . Один вход и один выход присваивается каждой переменной в ф и к каждой вершине в G . Если x некоторая переменная в ϕϕGϕNC30n+vnϕvGϕGxϕтогда мы будем ссылаться на входные и выходные биты, связанные с как x i n и x o u t . Кроме того, если l - литерал с l = x, то мы определяем l i n = x i n, а если l - литерал с l = ¬ x, то мы определяем l i n = ¬ x i n . Наконец, если v некоторая вершина в Gxxinxoutll=xlin=xinll=¬xlin=¬xinvGтогда мы будем ссылаться на входные и выходные биты, связанные с как v i n и v o u t .vvinvout

Существует четыре типа выходных битов:

1) Для каждой переменной в ϕ , x o u t = x i n . Обратите внимание, что этот вывод зависит только от одного входного бита.xϕxout=xin

2) Для каждой вершины в помеченном графе с ровно одним входящим ребром ( u , v ) таким, что ребро немечено, v o u t = v i nu i n . Обратите внимание, что этот вывод зависит только от двух входных битов.v(u,v)vout=vinuin

3) Для каждой вершины в помеченном графе с ровно одним входящим ребром ( u , v ) таким, что ребро помечено как l , v o u t = v i n( u i nl i n ) . Обратите внимание, что этот вывод зависит только от трех входных битов, поскольку l i n зависит только от x i n для любой переменной x , используемой в литерале l .v(u,v)lvout=vin(uinlin)linxinxl

4) Для каждой вершины в меченого графа с ровно два входящих ребер ( U , V ) и ( ш , v ) , v о у т = v я п( у я пш I н ) . Обратите внимание, что этот вывод зависит только от трех входных битов.v(u,v)(w,v)vout=vin(uinwin)

Поскольку во всех случаях выходной сигнал зависит только от трех входов, схема, которую мы строим, находится в по желанию.NC30

Доказательство правильности, случай 1: выполнимоϕ

Предположим, что существует удовлетворительное присваивание для . Затем создайте следующие два набора значений для входных данных.ϕ

1) Входные данные, связанные с переменными , получают значения удовлетворяющего назначения. Всем входам, связанным с вершинами G , присваивается значение 0.ϕG

2) Входные данные, связанные с переменными , получают значения удовлетворяющего назначения. Рассмотрим вершины в одном пункте гаджета в G . Если значение метки равно 0 (при удовлетворительном назначении), входу, связанному с вершиной в целевой конечной точке ребра, помеченного этой меткой, присваивается значение 0. Если и L1, и L2 имеют значение 0, то вторая Вершине вершины в гаджете (как показано выше) также присваивается значение 0. Всем остальным вершинам присваивается значение 1.ϕG

Мы хотим показать, что эти два набора входов дают идентичные выходы и, следовательно, что схема не кодирует перестановку.NC30

Рассмотрим четыре типа выходных битов:

1) Для каждой переменной в ϕ , x o u t = x i n . Поскольку x i n одинакова для обоих наборов входов, выходы этой формы всегда будут одинаковыми для двух наборов входов.xϕxout=xinxin

2) Для каждой вершины в помеченном графе с ровно одним входящим ребром ( u , v ) таким, что ребро немечено, v o u t = v i nu i n . Исследуя гаджет, копии которого составляют G , мы видим, что все такие ребра состоят только из пар вершин, чьи входные значения всегда равны 1 с при втором наборе входных данных. Таким образом, v o u t = v i nu i n = 0 0 =v(u,v)vout=vinuinG в рамках первого набора входных данных и v о у т = v я пу я п = 1 1 = 0 в рамках второго набора входных данных. Таким образом, выходные данные этой формы всегда будут одинаковыми (и фактически равны нулю) для двух наборов входных данных.vout=vinuin=00=0vout=vinuin=11=0

3) Для каждой вершины в помеченном графе с ровно одним входящим ребром ( u , v ) таким, что ребро помечено как l , v o u t = v i n( u i nl ) . Если в назначении l ложно, то v i n равно 0 для обоих наборов входов; тогда v o u t = v i n( u i nv(u,v)lvout=vin(uinl)lvin при обоих наборах входов. Если l является истинным для назначения, v i n равно 0 для первого набора входов и 1 для второго; также обратите внимание, что в гаджете только помеченные ребра ( u , v ) имеют вершины u, которые всегда имеют u i n = 1vout=vin(uinl)=vin(uin0)=vin=0lvin(u,v)uuin=1под вторым набором входов. В результате мы видим, что при обоих наборах входов всякий раз, когда l истинно; тогда v o u t = v i n( u i nl ) = v i n( u i n1 ) = v i nu i n = v i nvuin=vinl. Таким образом, выходные данные этой формы всегда будут одинаковыми (и фактически равны нулю) для двух наборов входных данных.vout=vin(uinl)=vin(uin1)=vinuin=vinvin=0

4) Для каждой вершины в меченого графа с ровно два входящих ребер ( U , V ) и ( ш , v ) , v о у т = v я п( у я пш I н ) . В каждом гаджете есть две такие вершины. Верхняя вершина и вторая - из верхней вершины. Мы рассмотрим эти два случая отдельно.v(u,v)(w,v)vout=vin(uinwin)

4a) Когда - вершина второго верхнего в гаджете, u и w - две конечные точки ребер, обозначенные L1 и L2. В рамках первого набора входных данных, v о у т = v я п( у я пж я п ) = 0 ( 0 0 ) = 0 . При втором наборе входов u i n равно 0, если L1 имеет значение 0 при удовлетворительном назначении (aka u i n =vuwvout=vin(uinwin)=0(00)=0uin ); аналогично, w i n равно 0, если L2 имеет значение 0 при удовлетворительном назначении (aka w i n = L 2 ); и, наконец, v i n определено равным 0, если и L1, и L2 имеют значение 0 (иначе v i n = L 1 L 2 ). Таким образом, при втором наборе входных данных v o u t = v i n( u i nw i n ) = (uin=L1winwin=L2vinvin=L1L2 . Таким образом, выходные данные этой формы всегда будут одинаковыми (и фактически равны нулю) для двух наборов входных данных.vout=vin(uinwin)=(L1L2)(L1L2)=0

4b) Когда - это верхняя вершина в гаджете, u - это вторая вершина, а w - конечная точка ребра, помеченного как L3. В рамках первого набора входных данных, v о у т = v я п( у я пж я п ) = 0 ( 0 0 ) = 0 . При втором наборе входов u i n равно 0, если оба значения L1 и L2 имеют значение 0 (иначе u i n = Lvuwvout=vin(uinwin)=0(00)=0uin ); w i n равно 0, если L3 имеет значение 0 (иначе w i n = L 3 ); и наконец v i n = 1 . Таким образомрамках второго набора входных данных, v о у т = v я п( у я пж я п ) = 1 ( ( L 1 L 2 ) L 3 )uin=L1L2winwin=L3vin=1 где равенство ( L 1 L 2 L 3 ) = 1 выполняется по определению в удовлетворительном назначении для каждого предложения. Таким образом, выходные данные этой формы всегда будут одинаковыми (и фактически равны нулю) для двух наборов входных данных.vout=vin(uinwin)=1((L1L2)L3)=1(L1L2L3)=11=0(L1L2L3)=1

Ясно, что мы видим, что выходы одинаковы для двух разных наборов входов и, следовательно, что схема выполняет небиективную функцию.NC30

ϕ

ϕNC30

xinxϕx

SvGvin

Мы докажем следующие леммы ниже:

SS

SS

SGSS

(L1L2L3)(u,v)Lvout=vin(uinL)L=0vout=vin(uinL)=vin(uin0)=vin0=vinvinvSS

SNC30

Осталось доказать леммы.

GSSvout=vinXXvSXvin=voutXvS

SS

Михаил Рудой
источник
-1

Не тот ответ, который искал автор, посмотрите комментарии, которые проясняют, что такое «перестановка» в этом контексте.

Я выбрал размер минимального доминирующего множества для диграфа включения в группу моногенных перестановок: https://oeis.org/A186202

Все, что вам нужно сделать, это проверить один член каждого разложения основного цикла.

Для каждого простого цикла достаточно кодировать элементы как (10101010 ...), затем (01010101 ..)?

------ Уточнение ------ Целью этого подхода является моделирование ваших 2 ^ n тестовых случаев в качестве орграфа. Если один успешный тестовый пример подразумевает другой успешный тестовый случай, то вам нужно только протестировать минимальный доминирующий набор этого орграфа тестового пространства. В пространстве перестановок OEIS A186202 - это максимум, который вы должны проверить, чтобы обнаружить нетривиальную подгруппу или доказать, что она не существует; это число все еще велико, но намного меньше n !.

--Musing-- Используя n-1 нули и 1 единицу в n итерациях, вы можете обнаружить фиксированную перестановку, которую вы ищете. После этого в O (n {(n-1) \ choose (k-1)} (2 ^ (k-1)) вы можете проверить, что каждый набор (k-1) переменных не влияет на каждый индекс тасования Так как k фиксировано, это полином. Я что-то упустил?

Чад Brewbaker
источник
Хм. Не уверен, что (01) *, (10) * достаточно. Возможно, вам придется попробовать все 2 ^ p конфигурации для каждого простого цикла.
Чад Brewbaker
2
(2n)!n11
2
C:{0,1}n{0,1}nx,x{0,1}nC(x)=C(x)xxCпереставляет (перемешивает / переупорядочивает / переупорядочивает) входные биты. Вы видите разницу? Я подозреваю, что вы отвечаете не на тот вопрос.
DW
2
Спасибо за попытку помочь, но, как объяснила DW, я боюсь, что вопрос, на который вы ответили, отличается от того, который я задавал. «Перестановка в {0,1} ^ n» означает биективную функцию от {0,1} ^ n до самой себя, и это не означает перестановку n битов.
Цуёси Ито
3
Чад, не могли бы вы удалить этот ответ или хотя бы добавить в начало заметку, что это не ответ на вопрос Цуёси?
Каве