Avaliando a multilinearização de um circuito aritmético?

Deixe ser um polinómio de multi-variada com coeficientes de mais de um campo . A multilinearização de , denotada por , é o resultado da substituição repetida de cada por por . O resultado é obviamente um polinômio multilinear. $p(x_1,\ldots,x_n)$ $F$ $p$ $\hat{p}$ $x_i^d$ $d > 1$ $x_i$

Considere o seguinte problema: dado um circuito aritmético $C(x_1,\ldots,x_n)$ sobre $F$ e dados os elementos de campo $a_1,\ldots,a_n$ , calcule $\hat{C}(a_1,\ldots,a_n)$ .

Pergunta: Supondo que a aritmética de campo possa ser feita em tempo unitário, existe um algoritmo de tempo polinomial para isso? Adicionado mais tarde: eu também estaria interessado no caso especial em que $C$ é realmente uma fórmula (um circuito de fan-out $1$ ).

cc.complexity-theory polynomials Slimton
fonte

Por que seria equivalente a calcular a saída de um circuito fechado? O problema que estou enfrentando é que o circuito pode ter caminhos separados de uma entrada para vários nós de multiplicação internos, e avaliar cada um desses nós de multiplicação internos exigiria a substituição de por em um caminho e por no outro. Em um circuito com um número exponencial de caminhos, parece que há um número exponencial de casos para resolver.

x_{i}

$x_i$

x_{i}

$x_i$

a_{i}

$a_i$

1

$1$

@ Kaveh: Eu não entendo. Veja o circuito . Se você apenas substituir o nó de entrada por um nó com o valor de e avaliar de forma padrão você acaba voltando em vez de . Modelo de computação: tempo polinomial apenas normal em máquinas de Turing. Pense no campo como sendo para concretude, se desejar.

(x * x)

$(x * x)$

x

$x$

a

$a$

a^{2}

$a^2$

a

$a$

Z / 3 Z

$Z/3Z$

slimton

@ Kaveh: Eu não entendo como esse algoritmo implica o que você diz, mas isso de fato contradiz uma hipótese comum na complexidade dos circuitos aritméticos: que o Permanent não possui circuitos aritméticos de tamanho poli (sobre campos diferentes de F_2). Considere o polinômio . A parte multilinear desse polinômio tem a propriedade de que sua parte de maior grau ( ) é apenas . Se houver um pequeno circuito aritmético computando , então pode-se mostrar que existe um pequeno circuito aritmético computando .

p = \prod_{i} (\sum_{j} x_{i j} y_{j})

$p=\prod_i(\sum_j x_{ij} y_j)$

q

$q$

= 2 n

$=2n$

r = y_{1} y_{2} \dots y_{n} P e r (x_{11}, \dots, x_{n n})

$r = y_1y_2\cdots y_n Per(x_{11},\ldots,x_{nn})$

q

$q$

r

$r$

Srikanth

@Srikanth: Eu não vi seu comentário antes de postar minha resposta (que acabou sendo a mesma construção que você deu em seu comentário). Desde então, excluí minha resposta e você deve postar seu comentário como resposta.

13139 Joshua Grochow

@ Josué: Eu não adicionei meu comentário como resposta, pois não entendo por que a construção da Kaveh funciona. Vejo que o circuito aritmético calcula um polinômio que concorda com a multilinearização em todas as entradas, mas não tenho certeza se calcula formalmente a multilinearização do polinômio fornecido (veja meus comentários após a resposta de Kaveh). Minha construção (e a sua) pressupõe que a multilinearização seja computada formalmente.

Srikanth

Respostas:

No caso de o campo tamanho de pelo menos , acho que esse problema é difícil. Mais especificamente, acho que se o acima pode ser resolvido com eficiência para desse tamanho, o CNF-SAT possui algoritmos aleatórios eficientes. Digamos que recebemos uma fórmula CNF . Pode-se facilmente criar um circuito aritmético que calcula uma `` aritmetização '' de , onde o polinômio concorda com a fórmula nas entradas - . Considere a multilinearização de . Observe que $F$ $2n$ $F$ $\varphi$ $C$ $p$ $\varphi$ $p$ $\varphi$ $0$ $1$ $q$ $p$ $q$ concorda com portanto, em . $p$ $\varphi$ $\{0,1\}^n$

Eu afirmo que é diferente de zero se for satisfatório. Claramente, se , então não pode ser satisfeito. Por outro lado, pode-se mostrar que qualquer polinômio multilinear diferente de zero não pode desaparecer em todos os . Isso implica que um diferente de zero (e, portanto, o correspondente ) não desaparece em alguma entrada em . $q$ $\varphi$ $q=0$ $\varphi$ $\{0,1\}^n$ $q$ $\varphi$ $\{0,1\}^n$

Portanto, verificar a satisfação de é equivalente a verificar se é diferente de zero. Digamos, agora, que poderíamos avaliar em um campo grande $\varphi$ $q$ $q$ . Então, usando o Lema de Schwartz-Zippel, poderíamos testar a identidadeusando um algoritmo aleatório eficiente e verificar se é o polinômio zero (o tamanho deé usado para limitar o erro no Lema de Schwartz-Zippel). $F$ $q$ $F$

Srikanth
fonte

Parece-me que F é um campo fixo porque não há nada na entrada que especifique F. Observe também que a pergunta assume que as operações de campo levam tempo unitário.

Kaveh

Obrigado Srikanth. Como Kaveh adivinhou, eu estava realmente interessado no caso de campo finito fixo, mas essa resposta que você deu me ajuda a entender um pouco melhor a pergunta.

Suponha que exista um algoritmo polytime que forneceu e calculou o resultado da multi-linearização de em . (wlog, assumirei que a saída será um vetor de números binários bits é se for um.) $C(\vec{x}) \in F(\vec{x})$ $\vec{a}$ $C$ $\vec{a}$ $\vec{b}$ $p$ $b_i$ $k$ $b_{i,k}$

Desde , existe um circuito booleano polysize que dada a codificação do circuito aritmético e os valores para as variáveis calcula a multi-linearização do circuito aritmético nas entradas. Vamos chamar esse circuito . $P \subseteq P/poly$ $M$

Seja um circuito aritmético arbitrário. Corrija as variáveis do circuito booleano que descrevem o circuito aritmético, para que tenhamos um circuito booleano que calcula a multi-linearização de em determinadas entradas. $C$ $M$ $C$

Nós podemos transformar este circuito para um circuito aritmético sobre notando que é para todos os valores, mas de maneira que primeiro levantar todas as entradas para a alimentação . Substituir cada portão por multiplicação , cada portão por e cada gate por . $F_p$ $x^{p-1}$ $1$ $0$ $p-1$ $f \land g$ $f.g$ $f \lor g$ $f+g-f.g$ $\lnot f$ $1-f$

Pela suposição que fizemos acima sobre o formato da saída, podemos transformar a saída de binária em valores acima de . Tome a saída para e combine-os para obter . $F_p$ $b_i$ $\sum_{0 \leq k \leq p-1}{kb_{i,k}}$

Também podemos converter a entrada fornecida como valores acima de para a forma binária, pois existem polinômios passando por qualquer número finito de pontos. Por exemplo, se estamos trabalhando no , considere os polinômios e que fornecem o primeiro e o segundo bits da entrada . $F_p$ $\bmod 3$ $2x(x+1)$ $2x(x+2)$ $x \in F_3$

Combinando estes temos um circuito aritmético sobre computar a multi-linearização de com tamanho polynomail no tamanho de . $F_p$ $C$ $C$

Kaveh
fonte

Não está claro para mim por que o circuito aritmético que você descreveu calcula a multilinearização de

, ou mesmo um polinômio multilinear. Eu só consigo ver que o circuito aritmético calcula algum polinômio que concorda com a multilinearização de

nas entradas

C

$C$

C

$C$

0

$0$

1

$1$

Srikanth

@ Krikanth: a versão aritmética do circuito booleano

(com algumas entradas fixas) calcula a versão multilinear de

, não precisa ser multilinear. Em seguida, o único problema é que a entrada / saída estão em binário não os valores superiores a

, então eu só preciso para corrigir a codificação para entrada / saída de binário para originais valores de entrada e saída. O circuito resultante é um circuito aritmético que obtém os valores para variáveis de

, codifica-os em binário, calcula o valor da multilinearização de

sobre essas entradas e gera a resposta em binário e depois converte-os novamente em

M

$M$

C

$C$

F_{p}

$F_p$

C

$C$

C

$C$

F_{p}

$F_p$

Kaveh

[continuou] O resultado é um circuito aritmético com as mesmas variáveis que

tem, e com os mesmos resultados, e é computar o multilinearization de

C

$C$

C

$C$

Kaveh

@ Kaveh: Você assumiu que a entrada para o circuito booleano

é da mesma forma que a saída de

? De qualquer forma, ainda não estou convencido. É perfeitamente possível que um circuito aritmético calcule um polinômio

que concorda com um polinômio

em todas as entradas do campo e ainda assim

. Por exemplo, o polinômio

concorda com

em todas as entradas e, no entanto, elas não são iguais a polinômios. Como você sabe que o circuito

não está simplesmente computando um polinômio não multilinear que concorda com a multilinearização de

em todas as entradas?

M

$M$

M

$M$

f

$f$

g

$g$

f \neq g

$f\neq g$

x^{p}

$x^p$

x

$x$

M

$M$

C

$C$

Srikanth

@ Krikanth: descrevi a forma de entrada e saída na minha resposta. A entrada para

está em binário, a saída de

está na forma declarada acima. Eu não disse que é multilinear, eu só disse que ele calcula a multilinearization do .

M

$M$

M

$M$ $C$

Kaveh