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.
27
Respostas:
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 x ′ 1 ,…, x ′ n , 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 φ .
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 .
fonte