O teste de identidade polinomial sobre expressões * aritméticas * é trivial?

8

Testes de identidade polinómio é o padrão exemplo de um problema conhecido por ser em co-RP mas não conhecido por ser em P . Nos circuitos aritméticos , parece realmente difícil, pois o grau do polinômio pode ser aumentado exponencialmente por meio de quadrados repetidos. Esta pergunta aborda a questão de como contornar isso e manter o problema em tempo polinomial aleatório.

Por outro lado, quando o problema é apresentado inicialmente (por exemplo, aqui ), é frequentemente ilustrado sobre expressões aritméticas contendo apenas constantes, variáveis, adição e multiplicação. Tais polinômios têm grau total no máximo polinômio no comprimento da expressão de entrada e, para qualquer polinômio, o tamanho do valor de saída é polinomial no tamanho dos valores de entrada. Mas desde que um polinômio de graud tem no máximo draízes, isso não é trivial? Apenas avalie o polinômio sobre os racionais em qualquer d+1pontos distintos e verifique se o resultado é zero em cada ponto. Isso deve levar apenas tempo polinomial. Isso está correto? Se sim, por que expressões aritméticas sem subexpressões compartilhadas são frequentemente usadas como exemplos, quando o compartilhamento é essencial para a dificuldade do problema?

Aaron Rotenberg
fonte

Respostas:

6

Isso não é conhecido por ser trivial .

O polinômioxyTem infinitas raízes. (Quando uma variável é zero, a outra variável não afeta o valor do polinômio.)

Juho
fonte
Ah ok. Não sei como eu perdi que polinômios multi-variáveis ​​possam ter infinitas raízes.
Aaron Rotenberg
A propósito, o Corolário 3.1 deste artigo fornece uma conseqüência interessante para melhorias significativas (mesmo não determinísticas) no algoritmo que você descreve.
7

Para um polinômio univariadop(x), sim, é assim tão fácil.

Para um polinômio multivariadop(x1,x2,,xk), não, esse algoritmo não funciona.

Em particular, quando você escreve "um polinômio de grau d tem no máximo d raízes ", isso é verdade para polinômios univariados p(x), mas não é verdade em geral para polinômios multivariados. Ricky Demer dá um exemplo simples:p(x,y)=xy é de grau dois, mas tem infinitas raízes.

DW
fonte
-1

Aqui está uma maneira mais geral / abstrata de entender a significância / dureza do teste de identidade polinomial no CS. um dos motivos pelos quais o teste de identidade polinomial está sendo estudado intensamente agora, porque há muito se sabe que está intimamente ligado à complexidade do circuito booleano. imagine pegar dois circuitos booleanos arbitrários e depois convertê-los (isto é, basicamente configurar um mapeamento 1-1) em polinômios multivariados. isso não é tão difícil. basicamente, usa-se valores de 0/1 para representar falso / verdadeiro e as construções são configuradas em documentos antigos. então as raízes do polinômio correspondem às atribuições de variáveis ​​T / F que satisfazem as fórmulas / circuitos.

após essa configuração, o PIT é basicamente quase o mesmo problema que determinar se dois circuitos binários são equivalentes. existem também outras provas profundas (mais recentes) que dizem que é quase equivalente em complexidade a fatorar polinômios. [ 1 ] Então, acabamos com um resultado como o seguinte: se alguém pode resolver o PIT "rapidamente", significa que dois circuitos grandes podem ser comparado com a equivalência "rapidamente", o que é improvável. portanto, uma maneira aproximada de entender o problema é que é quase equivalente a problemas não triviais na teoria dos circuitos booleanos.

vzn
fonte