Avalie o circuito booleano em lotes de entradas semelhantes

10

Suponha que eu tenha um circuito booleano que calcule alguma função f : { 0 , 1 } n{ 0 , 1 } . Suponha que o circuito seja composto de portas AND, OR e NOT com entrada e saída de ventilador no máximo 2.Cf:{0,1}n{0,1}

Vamos ser um dado de entrada. Dados C e x , quero avaliar C nas n entradas que diferem de x em uma única posição de bit, ou seja, para calcular os valores n C ( x 1 ) , C ( x 2 ) , , C ( x n ) onde x i é o mesmo que x, exceto que seu ix{0,1}nCxCnxnC(x1),C(x2),,C(xn)xixio bit é invertido.

Existe uma maneira de fazer isso que seja mais eficiente que avaliar independentemente n vezes nas n entradas diferentes?C nn

Suponha contém m portões. A avaliação independente de C em todas as n entradas levará tempo O ( m n ) . Existe uma maneira de calcular C ( x 1 ) , C ( x 2 ) , , C ( x n ) em o ( m n ) tempo?CmCnO(mn)C(x1),C(x2),,C(xn)o(mn)


Contexto opcional: se tivéssemos um circuito aritmético (cujas portas são multiplicação, adição e negação) sobre , seria possível calcular as n derivadas direcionais fRnemS(m)o tempo. Basicamente, poderíamos usar métodos padrão para o cálculo do gradiente (retropropagação / regra da cadeia), emO(m)tempo. Isso funciona porque a função correspondente é contínua e diferenciável. Gostaria de saber se algo semelhante pode ser feito para circuitos booleanos. Os circuitos booleanos não são contínuos e diferenciáveis, então você não pode fazer o mesmo truque, mas talvez haja alguma outra técnica inteligente que se possa usar? Talvez algum tipo de truque de Fourier, ou algo assim?fxi(x)O(m)O(m)

(Pergunta variante: se tivermos portões booleanos com fan-in ilimitado e fan-out limitado, você pode se sair assintoticamente melhor do que avaliar n vezes?)C n

DW
fonte
11
Como Andrew respondeu muito bem à sua pergunta, deixarei um comentário. Se for grande (como O ( 2 n / n ) ) e você estiver avaliando C em muitas entradas (até 2 o ( n / log n ) ), haverá um C de tamanho apenas O ( 2 n / n ) que pode avaliar C em qualquer mmO(2n/n)C2o(n/logn)CO(2n/n)Cmentradas. (O problema também é chamado de "produção em massa" na literatura.) Veja Uhlig, "Sobre a síntese de esquemas de autocorreção a partir de elementos funcionais com um pequeno número de elementos confiáveis". Math.Notes Acad.Sci. URSS 15, 558--562. Portanto, em alguns casos, você pode fazer melhor com a não uniformidade.
Ryan Williams

Respostas:

10

Eu consideraria improvável que esse truque seja fácil de encontrar e / ou lhe traga ganhos significativos, pois daria algoritmos de satisfação não triviais. Aqui está como:

CNx0,,xN1CO~(N|C|)CC|C|+O~(Nn)0i10N1iC(xi)0i10N1ixiC

O~(|C|2ϵ+(N|C|)1ϵ/2+N2ϵ)ϵ>0CCC2n/2|C|n/2CC2n/2CCO~(2(n/2)(2ϵ)|C|2ϵ)=O~(2n(1ϵ/2)poly(|C|))

Andrew Morgan
fonte