Decidir se um determinado circuito

27

Qual é a complexidade de decidir se um circuito com bits de entrada e bits de saída calcula uma permutação de ? em outras palavras, se cada bit em é uma saída do circuito para alguma entrada? Parece um problema que foi estudado, mas não consigo encontrar nenhuma referência.NC0 0nn{0 0,1}n{0 0,1}n

QiCheng
fonte
1
O limite óbvio é que também funciona para (verifique se a função é injetiva). coNPP
Kaveh
O que você quer dizer com "um circuito NC0"? A frase usual é "família de circuitos NC0", que é (talvez infelizmente) frequentemente abreviada para "circuito NC0", mas não acho que você queira dizer uma família de circuitos NC0 em sua pergunta.
Tsuyoshi Ito
1
Por um circuito , quero dizer que cada bit de saída do circuito depende apenas do número constante de bits de entrada. NC0 0
QiCheng 20/10
3
Sim, estou perguntando sobre uma família. Para deixar as coisas mais claras, você pode alterar para N C 0 5 onde cada bit de saída depende apenas de 5 bits de entrada na família. NC0 0NC50 05
QiCheng 21/10
1
Isso não responde à sua pergunta, mas se o problema for generalizado para que cada bit de saída possa depender dos bits de entrada O (log n), então acho que o problema é coNP-completo sob redutibilidade de Turing. Isto decorre da coNP-completude da reversibilidade finita de autômatos celulares bidimensionais ( Durand 1994 ), representando cada célula em um autômato celular bidimensional como uma cadeia binária de bits O (log n).
Tsuyoshi Ito

Respostas:

29

Dureza

Após o seu comentário sobre a questão, chamaremos um circuito em que cada bit de saída depende no máximo de k bits de entrada de " circuito NC 0 k ". Com esse termo, seu problema é coNP completo no caso de circuitos NC 0 5 . Ou seja, o seguinte problema é coNP-completo.

Instância : Um circuito booleano C com n bits de entrada e n bits de saída em que cada bit de saída depende de no máximo cinco bits de entrada.
Pergunta : O mapeamento de {0,1} n para ele mesmo é calculado por C bijetivo?

Como Kaveh comentou, está claramente no coNP, mesmo sem o limite do número de bits de entrada dos quais cada bit de saída depende. Para provar a dureza do coNP, reduziremos o 3SAT para complementar o problema atual. A idéia principal da redução é a mesma usada no artigo [Dur94] de Durand, que mencionei em um comentário sobre a questão, mas toda a redução é muito mais simples no nosso caso.

Dada uma fórmula 3CNF φ com n variáveis ​​e cláusulas m , construímos um circuito booleano C com ( n + m ) bits de entrada e ( n + m ) bits de saída da seguinte maneira. Nós rotulamos os bits de entrada como x 1 ,…, x n , y 1 ,…, y m , e os bits de saída como x1 ,…, xn , z 1 ,…, z m . Consideramos que os bits de entrada x1 ,…, x n especifica uma atribuição de verdade para as n variáveis ​​em φ .

  • xi = x i para 1≤ in . Ou seja, os primeiros n bits de entrada são sempre copiados para os primeiros n bits de saída.
  • Para 1≤ im , se o i th cláusula de φ é satisfeita, então z i = y iy i 1 , onde o subscrito é interpretado modulo m . Caso contrário, z i = y i .

Observe que cada bit de saída depende de no máximo cinco bits de entrada. Eu omito a prova da correção da redução, mas a idéia principal (que peguei emprestada de [Dur94]) é que se φ é satisfatório e os bits de entrada x 1 ,…, x n são configurados para uma atribuição satisfatória de φ , então os m bits de saída z 1 ,…, z m são limitados a ter paridade par e, portanto, o circuito não pode ser uma permutação. Por outro lado, se os bits de entrada x 1 ,…, x n forem configurados para uma atribuição não satisfatória de φ , então os bits de saída z1 ,…, z m pode ser definido como qualquer coisa; por isso, se φ é insatisfatório, o circuito é uma permutação.

Rastreabilidade

No lado tratável, seu problema está em P no caso de circuitos NC 0 2 . Isso é mostrado da seguinte maneira. Em geral, cada bit de saída em um circuito booleano para uma permutação é balanceado ; ou seja, exatamente metade das seqüências de entrada define o bit de saída como 1. No entanto, toda função booleana balanceada de {0,1} 2 a {0,1} é afim ; isto é, uma cópia de um único bit de entrada, o XOR dos dois bits de entrada ou a negação deles. Portanto, podemos primeiro verificar se cada bit de saída está balanceado e depois verificar a bijetividade pela eliminação gaussiana.

Não sei a complexidade no caso de circuitos NC 0 3 ou no caso de circuitos NC 0 4 .

Referências

Bruno Durand. Inversão de autômatos celulares 2D: alguns resultados de complexidade. Teórico Computer Science , 134 (2): 387-401, novembro de 1994. DOI: 10.1016 / 0304-3975 (94) 90244-5 .

Tsuyoshi Ito
fonte
3
Eu postei uma pergunta de acompanhamento sobre o caso do NC ^ 0_3 circuitos.
Tsuyoshi Ito