Decidir se um circuito NC calcula uma permutação ou não

27

Eu gostaria de perguntar sobre um caso especial da pergunta “ Decidir se um determinado circuito NC 0 calcula uma permutação ” por QiCheng que foi deixada sem resposta.

Um circuito booleano é chamado de circuito NC 0 k se cada porta de saída depende sintaticamente da maioria das k portas de entrada. (Dizemos que uma porta de saída g depende sintaticamente de uma porta de entrada g 'quando existe um caminho direcionado de g ' para g no circuito, visto como um gráfico acíclico direcionado.)

Na pergunta acima mencionada, QiCheng perguntou sobre a complexidade do seguinte problema, onde k é uma constante:

Exemplo : Um NC 0 k circuito com n de entrada -bit e n saída de bits.
Pergunta : O circuito fornecido calcula uma permutação em {0, 1} n ? Em outras palavras, a função calculada pelo circuito é uma bijeção de {0, 1} n a {0, 1} n ?

Como Kaveh comentou sobre essa questão, é fácil perceber que o problema está no coNP. Em uma resposta, mostrei que o problema é coNP-completo para k = 5 e que está em P para k = 2.

Pergunta . Qual é a complexidade para k = 3?

Esclarecimento em 29 de maio de 2013 : “Uma permutação em {0, 1} n ” significa um mapeamento bijetivo de {0, 1} n para ele mesmo. Em outras palavras, o problema pergunta se cada sequência de n bits é a saída do circuito fornecido para alguma sequência de entrada de n bits.

Tsuyoshi Ito
fonte
1
Nota pessoal: Quando postei uma resposta à pergunta de QiCheng, fiz isso apenas porque o problema parecia interessante, sem nenhuma aplicação específica em mente. Vários meses depois disso, eu estava em uma situação em que precisava explicar a alguém que está longe de ser trivial decidir se um determinado programa calcula uma permutação ou não. Graças à pergunta de QiCheng, tive um exemplo perfeito (que coincidência!). Depois disso, fiquei mais curioso sobre os casos de k = 3 e k = 4. Suspeito que o caso de k = 3 já esteja coNP-completo, mas não consegui provar isso.
Tsuyoshi Ito
esse problema parece ser um caso particular do problema do circuito de pigeonhole definido por Papadimitriou ( sciencedirect.com/science/article/pii/S0022000005800637 ) que está completo para o PPP com relação às reduções de politempo entre os problemas de pesquisa.
Marcos Villagra
@Marcos Villagra: Obrigado pelo comentário, mas receio que, ao dizer “caso particular de”, você esteja mudando significativamente a definição do problema do circuito de Pigeonhole. Uma propriedade importante do problema do Pigeonhole Circuit é que ele é um problema de pesquisa total , enquanto o problema atual (visto como um problema de pesquisa para duas entradas que produzem a mesma saída) não é um problema de pesquisa total.
Tsuyoshi Ito

Respostas:

3

Esse problema com é difícil de coNP (e, portanto, completo de coNP).k=3

Para provar isso, reduzirei de 3-SAT para o complemento desse problema (para um determinado circuito , o circuito executa uma função não-bijetiva).NC30

Primeiro, uma definição preliminar que será útil:

Definimos um gráfico rotulado como um gráfico direcionado, cujas bordas são rotuladas com literais, com a propriedade de que todo vértice possui uma borda de entrada não rotulada, uma borda de entrada rotulada ou duas arestas de entrada não rotuladas.

A redução

Suponha que tenhamos uma fórmula 3-SAT consiste em cláusulas, cada uma contendo três literais. O primeiro passo é construir um gráfico rotulado partir de . Este gráfico rotulado contém uma cópia do seguinte gadget (desculpe pelo terrível diagrama) para cada cláusula em . As três arestas rotuladas L1, L2 e L3 são rotuladas com os literais na cláusula.m G ϕ ϕϕmGϕϕ

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

Os gadgets (um para cada cláusula) são todos organizados em um grande ciclo, com a parte inferior de um gadget sendo vinculada à parte superior do próximo.

Observe que esse arranjo de gadgets de fato forma um gráfico rotulado (todo vértice tem indegree 1 ou 2 com apenas arestas levando a vértices do indegree 1 a serem rotulados).

A partir da fórmula e do gráfico rotulado (que foi construído a partir de ), em seguida, construímos um circuito (isso concluirá a redução). O número de entradas e saídas para este circuito é , onde é o número de variáveis em e é o número de vértices em . Uma entrada e uma saída é atribuído a cada variável na e para cada vértice em . Se é alguma variável em , vamos nos referir aos bits de entrada e saída associados a comoG ϕ N C 0 3 n + v n ϕ v G ϕ G x ϕ x 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 G v v i n v o u tϕGϕNC30n+vnϕvGϕGxϕxxin e . Além disso, se é um literal com , definimos e se é um literal com então definimos . Finalmente, se é algum vértice em então nos referimos aos bits de entrada e saída associados a como e .xoutll=xlin=xinll=¬xlin=¬xinvGvvinvout

Existem quatro tipos de bits de saída:

1) Para cada variável in , . Observe que esta saída depende de apenas um bit de entrada.ϕ x o u t = x i nxϕxout=xin

2) Para cada vértice no gráfico rotulado com exatamente uma aresta de entrada forma que a aresta não seja rotulada, . Observe que essa saída depende apenas de dois bits de entrada.( u , v ) v o u t = v i nu i nv(u,v)vout=vinuin

3) Para cada vértice no gráfico rotulado com exatamente uma aresta de entrada modo que a aresta seja rotulada , . Observe que essa saída depende de apenas três bits de entrada, pois depende apenas de para qualquer variável usada no literal .( u , v ) l v o u t = v i n( u i nl i n ) l i n x i n x lv(u,v)lvout=vin(uinlin)linxinxl

4) Para cada vértice no gráfico rotulado com exatamente duas arestas de entrada e , . Observe que essa saída depende de apenas três bits de entrada.( u , v ) ( w , v ) v o u t = v i n( u i nw i n )v(u,v)(w,v)vout=vin(uinwin)

Como em todos os casos a saída depende de apenas três entradas, o circuito que construímos está em conforme desejado.NC30

Caso de prova de correção 1: é satisfatórioϕ

Suponha que exista uma tarefa satisfatória para . Em seguida, construa os dois conjuntos de valores a seguir para as entradas.ϕ

1) As entradas associadas às variáveis ​​de recebem os valores da atribuição satisfatória. Todas as entradas associadas aos vértices de recebem o valor 0.GϕG

2) As entradas associadas às variáveis ​​de recebem os valores da atribuição satisfatória. Considere os vértices em um gadget cláusula no . Se o valor de um rótulo for 0 (na atribuição satisfatória), a entrada associada ao vértice no ponto final de destino da aresta rotulada com esse rótulo receberá um valor 0. Se L1 e L2 tiverem valor 0, o segundo O vértice -top no gadget (como mostrado acima) também recebe o valor 0. Todos os outros vértices recebem o valor 1.GϕG

Queremos mostrar que esses dois conjuntos de entradas produzem saídas idênticas e, portanto, que o circuito não codifica uma permutação.NC30

Considere os quatro tipos de bits de saída:

1) Para cada variável in , . Como é o mesmo para os dois conjuntos de entradas, as saídas deste formulário sempre serão as mesmas nos dois conjuntos de entradas.ϕ x o u t = x i n x i nxϕxout=xinxin

2) Para cada vértice no gráfico rotulado com exatamente uma aresta de entrada forma que a aresta não seja rotulada, . Examinando o gadget cujas cópias compõem , vemos que todas essas arestas consistem apenas em pares de vértices cujos valores de entrada são sempre 1s no segundo conjunto de entradas. Assim sob o primeiro conjunto de entradas e no segundo conjunto de entradas. Assim, as saídas desse formulário sempre serão as mesmas (e de fato zero) nos dois conjuntos de entradas.( u , v ) v o u t = v i nu i n L v o u t = v i nu i n = 0 0 = 0 v o u t = v i nu i n = 1 1 = 0v(u,v)vout=vinuinGvout=vinuin=00=0vout=vinuin=11=0

3) Para cada vértice no gráfico rotulado com exatamente uma aresta de entrada , de forma que a aresta seja rotulada , . Se for falso na atribuição, será 0 nos dois conjuntos de entradas; então nos dois conjuntos de entradas. Se for verdadeiro na atribuição, será 0 no primeiro conjunto de entradas e 1 no segundo; Observe também que no gadget, as únicas arestas rotuladas têm vértices que sempre têm( u , v ) l v o u t = v i n( u i nl ) l v i n v o u t = v i n( u i nl ) = v i n( u i n0 ) = v i n = 0v(u,v)lvout=vin(uinl)lvinvout=vin(uinl)=vin(uin0)=vin=0v i n ( u , v ) u u i n = 1 u i n = v i n l v o u t = v i n( u i nl ) = v i n( u i n1 ) = v i nu i n = vlvin(u,v)uuin=1 no segundo conjunto de entradas. Como resultado, vemos que, nos dois conjuntos de entradas, sempre que for verdadeira; então . Assim, as saídas desse formulário sempre serão as mesmas (e de fato zero) nos dois conjuntos de entradas.uin=vinlvout=vin(uinl)=vin(uin1)=vinuin=vinvin=0

4) Para cada vértice no gráfico rotulado com exatamente duas arestas de entrada e , . Existem dois desses vértices em cada gadget. O vértice superior e o segundo do vértice superior. Consideramos esses dois casos separadamente.( u , v ) ( w , v ) v o u t = v i n( u i nw i n )v(u,v)(w,v)vout=vin(uinwin)

4a) Quando é o segundo vértice superior de um dispositivo, e são os dois pontos finais de destino das arestas rotuladas L1 e L2. Sob o primeiro conjunto de entradas, . Sob o segundo conjunto de entradas, é 0 se L1 tiver o valor 0 sob a atribuição satisfatória (aka ); da mesma forma, é 0 se L2 tiver o valor 0 na atribuição satisfatória (também conhecida como ); e finalmente, é definido como 0 se L1 e L2 tiverem valor 0 (também conhecido como ). Assim, no segundo conjunto de entradas,u w v o u t = v i n( u i nw i n ) = 0 ( 0 0 ) = 0 u i n u i n = L 1 w i n w i n = L 2 v i n v i n = L 1 L 2vuwvout=vin(uinwin)=0(00)=0uinuin=L1winwin=L2vinvin=L1L2vout=vin(uinwin)=(L1L2)(L1L2)=0 . Assim, as saídas desse formulário sempre serão as mesmas (e de fato zero) nos dois conjuntos de entradas.

4b) Quando é o vértice superior de um gadget, é o segundo vértice superior é o ponto final de destino da aresta rotulada como L3. Sob o primeiro conjunto de entradas, . Sob o segundo conjunto de entradas, é 0 se L1 e L2 tiverem valor 0 (aka ); é 0 se L3 tiver o valor 0 (também conhecido como ); e finalmente . Assim, no segundo conjunto de entradas, onde a igualdadeu w v o u t = v i n( u i nw i n ) = 0 ( 0 0 ) = 0 u i n u i n = L 1 L 2 w i n w i n = L 3 v i n = 1 v o u tvuwvout=vin(uinwin)=0(00)=0uinuin=L1L2winwin=L3vin=1( L 1 L 2 L 3 ) = 1vout=vin(uinwin)=1((L1L2)L3)=1(L1L2L3)=11=0(L1L2L3)=1 é mantido por definição em uma atribuição satisfatória para cada cláusula. Assim, as saídas desse formulário sempre serão as mesmas (e de fato zero) nos dois conjuntos de entradas.

Claramente, vemos que as saídas são iguais para dois conjuntos diferentes de entradas e, portanto, o circuito uma função não-bijetiva.NC30

Caso 2 de prova de correção: é insatisfatórioϕ

Suponha agora que não exista uma atribuição satisfatória para . Então, suponha, por uma contradição, que dois conjuntos diferentes de entradas levem o circuito ter a mesma saída.N C 0 3ϕNC30

Claramente, as duas entradas devem ter os mesmos valores para para cada variável em . Assim, podemos agora nos referir inequivocamente ao valor de . x ϕ xxinxϕx

Defina como o conjunto de vértices em modo que seja diferente nos dois conjuntos de valores de entrada.v G v i nSvGvin

Vamos provar os seguintes lemas abaixo:

Lema 1: Se em algum dispositivo todos os três vértices nas extremidades alvo das bordas marcadas não estão em , em seguida, não há vértices superiores aos três no dispositivo estão em .SSS

Lema 2: Se em algum gadget o vértice superior não está em , em seguida, na próxima dispositivo se nenhum vértice está em .SSS

Como os gadgets formam um loop, isso implica que, se em qualquer gadget, todos os três vértices nos pontos de extremidade das bordas rotuladas não estiverem em , nenhum vértice em estará em (em outras palavras, estará vazio).G S SSGSS

No entanto, considere um gadget associado a uma cláusula que não seja satisfeita. Neste gadget, todos os três rótulos têm valor 0. Sabemos que a borda chamada deve satisfazer , mas , então . Portanto, como a saída é a mesma para as duas entradas, os valores de também devem ser os mesmos nos dois conjuntos de entradas. Em outras palavras, mostramos que não está em( u , v ) L v o u t = v i n( u i nL ) L = 0 v o u t = v i n( u i nL ) = v i n( u i n(L1L2L3)(u,v)Lvout=vin(uinL)L=0 v i n v S Svout=vin(uinL)=vin(uin0)=vin0=vinvinvS. Assim, vemos que neste dispositivo particular, os três vértices nas extremidades alvo das bordas marcadas não estão em .S

Como resultado, concluímos que está vazio. No entanto, isso implica que entre os dois conjuntos de entradas não houve diferenças, o que contradiz a suposição de que esses conjuntos de entradas são diferentes. Como resultado, vemos que a função executada pelo circuito é injetiva e, portanto, uma bijeção.N C 0 3SNC30

Tudo o que resta é provar os lemas.

Para fazer isso, observamos que, para todo tipo de vértice em (indegree 1 com label, indegree 1 sem label e indegree 2), se todas as arestas de entrada vierem de vértices que não estão em , o vértice em questão também não está em . Isso ocorre porque nos três casos que é alguma função das entradas associadas a variáveis ​​e / ou vértices com arestas a . Como todos esses vértices não estão em por suposição, o valor de deve ser o mesmo nos dois conjuntos de entradas. Portanto também é o mesmo nos dois conjuntos de entradas. Em outras palavras,S S v o u t = v i nX X v S X v i n = v o u tX v SGSSvout=vinXXvSXvin=voutXvnão é em .S

Agora que temos a regra de que um vértice não está em sempre que todos os seus predecessores não estiverem em , os lemas seguem simplesmente aplicando a regra repetidamente ao diagrama de gadgets acima.SSS

Mikhail Rudoy
fonte
-1

Não é a resposta que o autor estava procurando; veja comentários que esclarecem o que é "permutação" neste contexto.

Aumentei o tamanho do conjunto dominante mínimo para o dígrafo de inclusão do grupo de permutação monogênica: https://oeis.org/A186202

Tudo o que você precisa fazer é testar um membro de cada decomposição do ciclo principal.

Para cada ciclo principal, deve ser suficiente codificar os elementos como (10101010 ...) e depois (01010101 ..)?

------ Esclarecimento ------ O objetivo dessa abordagem é modelar seus 2 ^ n casos de teste como um dígrafo. Se um caso de teste bem-sucedido implica outro caso de teste bem-sucedido, você só precisa testar o conjunto dominante mínimo deste dígrafo do espaço de teste. No espaço de permutações, o OEIS A186202 é o máximo que você precisa testar para detectar um subgrupo não trivial ou provar que não existe; esse número ainda é grande, mas muito menor que n !.

--Musing-- Usando n-1 zeros e 1 um em n iterações, é possível detectar a permutação fixa que você está procurando. Depois disso, em O (n {(n-1) \ escolha (k-1)} (2 ^ (k-1)), você pode testar se todo conjunto de variáveis ​​(k-1) não afeta cada índice do shuffle Como k é fixo, isso é polinomial. Estou perdendo alguma coisa?

Chad Brewbaker
fonte
Hmm. Não tenho certeza se o (01) *, (10) * é suficiente. Pode ser necessário tentar todas as configurações 2 ^ p para cada ciclo principal.
Chad Brewbaker
2
Desculpe, Chad, você me perdeu. Você está ciente de que a pergunta está perguntando se a função é bijetiva? (Existem Tais funções bijetivas.) Não está perguntando se os bits de saída são uma permutação (reordenação) dos bits de entrada - esse é um problema muito mais fácil, que pode ser respondido simplesmente executando o comando circuito em todas as entradas possíveis com zeros e um. n - 1 1(2n)!n-11
DW 28/05
2
Chad, sim, acredito que esteja perdendo alguma coisa. O pôster está perguntando se a função é uma função bijetiva (ou seja, não existe tal que e ). Ele / ela não está perguntando se a função permite (embaralha / reorganiza / reordena) os bits de entrada. Você vê a diferença? Eu suspeito que você esteja respondendo à pergunta errada. x , x '{ 0 , 1 } n C ( x ) = C ( X ' ) x x ' CC:{0 0,1}n{0 0,1}nx,x{0 0,1}nC(x)=C(x)xxC
DW
2
Obrigado por tentar ajudar, mas, como o DW explicou, tenho medo de que a pergunta que você respondeu seja diferente da que eu fiz. “Uma permutação em {0,1} ^ n” significa uma função bijetiva de {0,1} ^ n para si mesma, e isso não significa reorganizar os n bits.
Tsuyoshi Ito
3
Chad, você se importaria de excluir esta resposta ou, pelo menos, adicionar uma nota no topo de que isso não está respondendo à pergunta de Tsuyoshi?
Kaveh