Verificando se um polinômio se fator em fatores lineares

Seja $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ um polinômio dado por um circuito aritmético $C$ do tamanho $s$ . Dado $C$ como entrada, existe um algoritmo determinístico para verificar se todos os fatores irredutíveis de $f$ em $\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ são formas lineares? Em uma nota relacionada, dada uma forma linear $l=\sum_{i=1}^{n}l_{i}\cdot x_{i}$ , podemos verificar deterministically se $l$ é fator de $f$ . Obviamente, queremos que o tempo de execução seja polinomial nos dois casos. Por tamanho, queremos dizer o tamanho total do bit. Além disso, pode-se supor que o grau de $f$ é polinomial em $n$ .

ds.algorithms algebraic-complexity arithmetic-circuits Gorav Jindal
fonte

Quando você diz "tamanho

s

$s$ ", isso significa número de portas / fios ou tamanho total de bits (levando em consideração os bits usados para descrever quaisquer constantes no circuito)?

Joshua Grochow

@ JoshuaGrochow, sim tamanho é o tamanho do bit aqui.

Gorav Jindal

Três comentários que você provavelmente já tem em mente, mas apenas no caso de: 1. Com relação ao tempo polinomial, os algoritmos de fatoração para circuitos aritméticos são polinomiais no tamanho e no grau do polinômio, e eu não conheço algoritmos para tarefas relacionadas executadas em polinômio de tempo apenas no tamanho. 2. No que diz respeito ao determinismo, esses algoritmos são randomizados e as variantes determinísticas se tornam exponenciais no número de variáveis. 3. A segunda pergunta pode ser traduzida em um problema de PIT; portanto, sua pergunta equivale a des aleatorizar algum algoritmo PIT específico.

Bruno

Acrescento também que acho esses problemas muito interessantes e gostaria de saber o que já se sabe sobre isso!

Bruno

re PIT, teste de identidade polinomial via Schwartz-Zippel / wikipedia e há muita pesquisa ativa nessa área. (re que PIT pg pode ser usado para números inteiros fator, mas o que é um ref que descreve como usá-lo para polinômios fator?)

vzn

Verificando se um polinômio se fator em fatores lineares

Respostas: