Circuito polinomial reversível iff circuito reversível polinomial?

10

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 B={0,1} . Vamos definir uma porta de um elemento de Alt(Bn) para alguns finito n . Para finito N definir GN=nNAlt(Bn) , e definir G=nAlt(Bn) . Para dois portões π1Alt(Bm),π2Alt(Bn) gravaπ=π1|π2 para a permutaçãoBm+n definida porπ(uv)=π1(u)π2(v) parauBm,vBn , onde é concatenação de palavras. Para um conjunto de portasG gravaçãoG para o menor subconjunto denAlt(Bn) contendo os mapas de identidade e fechada sob composições de eventos bem definidos(π1,π2)π1π2 , e sob a operação|.

Sabe-se que GN=G para todos os N4 , vamos fixar N=4 para concretude. Concretamente, isso significa que qualquer πAlt(Bn) para qualquer nN podem ser escritas como π=ϕkϕ2ϕ1 para alguns k , onde para cada ϕi existe i eπiAlt(B4) tal queϕi(uvw)=uπi(v)w para todos|u|=i,|v|=4 .

Para πAlt(Bn) uma permutação uniforme. Se n4 , defina sua complexidade de porta reversível como o k mínimo, de modo que π possa ser escrito como uma composição como a acima. Se n<4 , defina a complexidade da porta de π como 1 . (Pode-se permitir a conjugação de portas pelas permutações de uabvubav. Isso altera a complexidade da porta apenas por um fator linear; portanto, para o presente objetivo, isso não importa.)

Suponha-se que tanto πAlt(Bn) 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 ?dπn

Estou interessado em uma resposta ou referências.

Algumas observações:

  • A prova do teorema de Barrington mostra que, para um m3 fixo 3 , se π é da forma especial π(uw)=ψ(u,w)w para alguma função ψ:Bm×BnBm , de modo que as permutações nas fibras w{uw|uBm} são pares para cadawBn , então a complexidade da porta reversível deπ é polinomial emn 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 m11ψ12m!/2mcoordenadas. 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 n . 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 πAlt(Bn) e π1 tem complexidade portão m (calculável por uma rede acíclico de m portões clássicos de duas de entrada), então não é permutação πAlts(Bn+m) com polinômio de complexidade de porta reversível em n+m modo que π(u0n+m)=(π(u)0n+m)para todosuBn . Ou seja, vamosfcalcular os valores da rede nos últimosmpedaços, wrt algum ordenação topológica da rede (assumindo que eles são0, caso contrário nós não nos importamos). Sejago mapa que soma osnbits de resposta aosnbits apósu. Permita quehtroque a primeira e a segunda palavra de comprimenton. Entãohf1gfcomprova a reivindicação.

  • Bijections unidirecionais em criptografia são permutações de Bn , 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 .

Ville Salo
fonte
LL(x,y)=(x,xf(y))fLf

Respostas:

1

f:2m2nLf:2m×2n2m×2nLf(x,y)=(x,f(x)y)LfkfO(k)m+nLff

Joseph Van Name
fonte