Complexidade de minimizar o tamanho da fórmula polinomial

Seja um polinômio grau em variáveis ​​acima de , onde é constante (digamos 2 ou 3). Gostaria de encontrar a menor fórmula para , em que "fórmula" e "tamanho da fórmula" são definidos da maneira óbvia (por exemplo, a menor fórmula para o polinômio é ).$f(x_1,\dots,x_n)$$d$$n$$\mathbb{F}_2$$d$$f$$x_1 x_2 + x_1 x_3$$x_1(x_2+x_3)$

Qual é a complexidade desse problema - é NP-difícil? A complexidade depende de ?$d$

[Mais formalmente, uma fórmula (também conhecida como "fórmula aritmética") é uma árvore binária enraizada, cujas folhas são rotuladas com uma variável de entrada ou a constante 1. Todos os outros vértices da árvore são rotulados com ou \ times . O tamanho da fórmula é o número de folhas usadas. A fórmula calcula um polinômio recursivamente: + vértices calculam a soma de seus filhos em \ mathbb {F} _2 , \ times vértices calculam o produto. ]$+$$\times$$+$$\mathbb{F}_2$$\times$

Você pode reduzir o problema de co-NP-Complete TAUTOLOGY (dada uma fórmula booleana, é uma tautologia?) Ao problema de minimizar o tamanho da fórmula (já que uma fórmula é uma tautologia se for equivalente a VERDADEIRO). Além disso, TAUTOLOGY for 3DNFs (analogamente ao SAT para 3CNFs) é co-NP-Complete.

Não é exatamente a resposta, mas espero que ajude:

Essa questão já deve ser NP difícil para d = 2 se você quiser saber a fórmula mínima para polinômios e não apenas para um. A prova é a seguinte: Existe uma correspondência individual entre n fórmulas bi-lineares (fórmulas do tipo$n$ ) e as matrizes do tensor 3, isto é, elementos em F n 2 ⊗ F n 2 ⊗ F n 2 . Tal que a classificação tensorial da matriz é exatamente a complexidade de multiplicação de n fórmulas bi-lineares.$\sum a_{ij}x_iy_j$$F_2^n\otimes F_2^n\otimes F_2^n$

Sabe-se que a classificação do tensor é um problema NP-difícil (provavelmente aproximar a classificação do tensor também é NP-difícil). Assim, a complexidade de multiplicação de n fórmulas b lineares é um problema NP-difícil$3$$n$

Qualquer resposta para isso depende muito do vocabulário que você permite na resposta. Se você deseja sua resposta no mesmo idioma da entrada (ou seja, como um polinômio), isso leva a um conjunto de respostas, que é o que os outros pôsteres estão enfrentando.

Mas se você permitir que o seu vocabulário de respostas seja ampliado, coisas maravilhosas podem acontecer. Você pode ver um exemplo na diferenciação simbólica versus automática: na diferenciação simbólica, apenas se permitem 'expressões', que tendem a explodir bastante; na diferenciação automática, permite -se programas lineares na resposta (mesmo que a entrada seja uma expressão), o que ajuda bastante a controlar o aumento da expressão. Para polinômios univariados, James Davenport e eu meditamos que você precisa inserir polinômios ciclotômicos como parte de seu vocabulário básico (consulte as referências sobre por que esses polinômios parecem ser a única fonte real de explosão, bem como os trabalhos que mostram vários resultados de redutibilidade entre problemas polinomiais e 3SAT).

Em outras palavras, se você permitir variar um pouco a resposta que você considera uma resposta clássica, talvez consiga obter uma resposta bastante diferente, ou seja, uma com uma complexidade muito melhor. Depende da sua motivação original para fazer a pergunta, seja puramente teórica ou com um aplicativo em mente, decidir se essa variação no vocabulário é aceitável para você. No cenário em que James e eu estávamos pensando sobre isso (computação simbólica), ajustar o vocabulário para diminuir a complexidade é perfeitamente aceitável (embora raramente seja feito).

A minimização geral do circuito / fórmula é certamente mais difícil que o teste de identidade, pois o tamanho mínimo da fórmula de qualquer identidade é simplesmente zero. Quanto mais difícil, não tenho uma resposta definitiva, mas talvez os "algoritmos de reconstrução" estudados em circuitos / fórmulas aritméticos possam ser algo nesse sentido.

$\mathcal{C}$$3$$\mathcal{C}$

$d$

$d=2$$x_1x_2 + x_3x_4 + .. + x_{2k-1}x_{2k} + \ell$