Minha pergunta é sobre funções bijetivas eficientemente computáveis. Informalmente, estou interessado em:
Se uma bijeção é computável em tempo polinomial, podemos calculá-la por um número polinomial de portas bijetivas?
Verifiquei a lista de perguntas relevantes e não localizei essa. Minha configuração precisa pode ou não ser ortodoxa, por isso incluo minhas definições. Acredito que a pergunta seja de nível de pesquisa, mas estou feliz por provar que estou errado.
Seja . Vamos definir uma porta de um elemento de para alguns finito . Para finito definir , e definir . Para dois portões grava para a permutação definida por para , onde é concatenação de palavras. Para um conjunto de portas gravação para o menor subconjunto de contendo os mapas de identidade e fechada sob composições de eventos bem definidos , e sob a operação.
Sabe-se que para todos os , vamos fixar para concretude. Concretamente, isso significa que qualquer para qualquer podem ser escritas como para alguns , onde para cada existe e tal que para todos .
Para uma permutação uniforme. Se , defina sua complexidade de porta reversível como o mínimo, de modo que possa ser escrito como uma composição como a acima. Se , defina a complexidade da porta de como . (Pode-se permitir a conjugação de portas pelas permutações de . Isso altera a complexidade da porta apenas por um fator linear; portanto, para o presente objetivo, isso não importa.)
Suponha-se que tanto e o seu inverso são eficientemente calculável em certo sentido, por exemplo, o tempo polinomial, NC d , logspace ... é a complexidade porta reversível de π então necessariamente polinomial em N ?
Estou interessado em uma resposta ou referências.
Algumas observações:
A prova do teorema de Barrington mostra que, para um fixo ≥ 3 , se é da forma especial para alguma função , de modo que as permutações nas fibras são pares para cada , então a complexidade da porta reversível de é polinomial em sempre que está em NC 1 . Ou seja, se existe umcircuitoNC 1 para ψ , existe umcircuitoNC 1 (maior por um fator constante) com 2 m ! / 2 nós de saída especiais que registram se uma permutação específica foi executada no primeiro mcoordenadas. Podemos então mostrar (como na prova do teorema de Barrington) que para cada nó nesta rede, toda permutação uniforme condicionada a qualquer valor desse nó tem uma complexidade de circuito de tamanho polinomial em . Agora combine os correspondentes aos novos nós especiais para obter uma complexidade polinomial de porta para .
Mostra truque de Bennett (entre outras coisas) que se e tem complexidade portão (calculável por uma rede acíclico de portões clássicos de duas de entrada), então não é permutação com polinômio de complexidade de porta reversível em modo que para todos . Ou seja, vamoscalcular os valores da rede nos últimospedaços, wrt algum ordenação topológica da rede (assumindo que eles são, caso contrário nós não nos importamos). Sejao mapa que soma osbits de resposta aosbits após. Permita quetroque a primeira e a segunda palavra de comprimento. Entãocomprova a reivindicação.
Bijections unidirecionais em criptografia são permutações de , que têm a propriedade de poderem ser computadas em tempo polinomial, mas não podem ser invertidas em tempo polinomial. (Sua propriedade definidora é muito mais forte, mas não acho relevante aqui.) Não sei se essa definição específica tem algo a ver diretamente com o problema atual, pois estamos lidando com um modelo de computação não uniforme .
fonte
Respostas:
fonte