Existe um circuito aritmético equivalente para cada função computável?

6

Existe um circuito aritmético equivalente para cada função computável?

Eu tenho tentado entender a afirmação acima, mas não encontrei um exemplo contrário, apesar de acreditar que a afirmação é falsa.

O que me deixou curioso é que li alguns teoremas afirmando que um protocolo (teoria do protocolo de criptografia) pode computar qualquer função computável, mas exige que a função seja especificada como um circuito aritmético.

Shuzheng
fonte
Circuitos aritméticos só pode calcular multinomiais
Ariel
@Ariel - Você pode descrever para um programador que estuda um pouco de criptografia como um hobby o que é um multinomial? :-)
Shuzheng
Os circuitos aritméticos calculam funções em muitas entradas finitas. Eles podem calcular todos os polinômios.
Yuval Filmus

Respostas:

10

Os circuitos aritméticos calculam um polinômio em suas entradas. Um circuito aritmético sobre algum campoF com n variáveis ​​e grau total d pode calcular funções f:FnF do formulário:

f(x1,...,xn)=i1+...+indαi1,...,inx1i1x2i2...xnin

Onde αi1,...,inF são os coeficientes do polinômio multivariado.

Existem muitas funções computáveis ​​que não podem ser expressas como um polinômio, por exemplo, f:QQ qual é 1 às x=0e zero em qualquer outro lugar. Desde af não é constante com um número infinito de zeros, não pode ser escrito como um polinômio univariado.

Ariel
fonte
Qual é o grau total d?
Shuzheng
A soma máxima de poderes i1+...+in tal que o monômio x1i1...xninaparece com coeficiente diferente de zero na função calculada pelo circuito. Observe que isso já pressupõe que qualquer circuito aritmético calcule algum polinômio, mas você pode mostrar isso facilmente por indução.
Ariel
14

Qualquer função booleana computável com uma entrada de comprimento fixo pode ser calculada por um circuito aritmético. Considere qualquer função booleanaf:{0,1}n{0,1}. Então existe um polinômio multivariadop(x1,,xn) de tal modo que f(x1,,xn)=p(x1,,xn) para todos x1,,xn, onde a aritmética é feita no módulo dois (ou seja, sobre o campo F2={0,1}) Agora, todo polinômio multivariado pode ser calculado por um circuito aritmético, entãof pode ser calculado por um circuito aritmético.

Em certo sentido, as restrições às entradas de comprimento fixo são inevitáveis, pois qualquer circuito possui inerentemente um número fixo de entradas e um número fixo de saídas. Então, quando você decide se concentrar nas funções booleanas, a afirmação que você viu na literatura criptográfica é justificada: qualquer função booleana que possa ser calculada por um circuito, pode ser calculada por um circuito aritmético. E qualquer função booleana computável pode ser calculada por circuitos aritméticos, onde entendemos "computado" como uma família de circuitos aritméticos, um por comprimento de entrada (o modelo não uniforme; isso é inevitável, se você quiser calcular usando circuitos, pois qualquer circuito pode ter apenas um comprimento de entrada fixo).

DW
fonte