¿Algún polinomio que sea difícil de contar pero fácil de decidir?

Cada circuito aritmético monótono , es decir, un circuito , calcula algunos polinomios multivariados F ( x 1 , ... , x n ) con coeficientes enteros no negativos. Dado un polinomio f ( x 1 , … , x n ) , el circuito$\{+,\times\}$$F(x_1,\ldots,x_n)$$f(x_1,\ldots,x_n)$

• calcula si F ( a ) = f ( a ) se cumple para todos a ∈ N n ; $f$$F(a)=f(a)$$a\in \mathbb{N}^n$
• cuenta si F ( a ) = f ( a ) se cumple para todos a ∈ { 0 , 1 } n ; $f$$F(a)=f(a)$$a\in\{0,1\}^n$
• decide si F ( a ) > 0 exactamente cuando f ( a ) > 0 se cumple para todo a ∈ { 0 , 1 } n . $f$$F(a)>0$$f(a)>0$$a\in\{0,1\}^n$

Sé que los polinomios explícitos (incluso multilineales) muestran que la brecha del tamaño del circuito "calcula / cuenta" puede ser exponencial. Mi pregunta se refiere a la brecha "cuenta / decide".$f$

Pregunta 1: ¿Alguien sabe de algún polinomio que sea exponencialmente más difícil de contar que decidir por { + , × } -circuitos? $f$$\{+,\times\}$

Como posible candidato, uno podría tomar el polinomio PATH cuyas variables corresponden a los bordes del gráfico completo en { 1 , ... , n } , y cada monomio corresponde a una ruta simple desde el nodo 1 al nodo n en K n . Este polinomio puede decidirse por un circuito de tamaño O ( n 3 ) que implementa, digamos, el algoritmo de programación dinámica Bellman-Ford, y es relativamente fácil demostrar que cada computación de circuito { + , × $K_n$$\{1,\ldots,n\}$$1$$n$$K_n$$O(n^3)$$\{+,\times\}$La RUTA debe tener un tamaño de . $2^{\Omega(n)}$

Por otro lado, cada circuito de conteo resuelve PATH el problema del camino, es decir, cuenta el número de 1 -a-- n caminos en el especificado por el correspondiente 0 - 1 subgrafo de entrada de K n . Este es un problema llamado # P -complete . Entonces, todos "creemos" que PATH no puede tener ningún circuito contable { + , × } de tamaño polinómico. El "único" problema es demostrar esto ... $\#$$1$$n$$0$$1$$K_n$$\#$$\{+,\times\}$

Puedo demostrar que cada circuito cuenta un HP polinomial de ruta hamiltoniana relacionado requiere un tamaño exponencial. Los monomios de este polinomio corresponden a rutas de 1 a n en K n que contienen todos los nodos. Desafortunadamente, la reducción de # HP a # PATH por Valiant requiere calcular el inverso de la matriz de Vandermonde y, por lo tanto, no puede implementarse mediante un circuito { + , × } .$\{+,\times\}$$1$$n$$K_n$$\#$$\#$$\{+,\times\}$

Pregunta 2: ¿Alguien ha visto una reducción monótona de HP a # PATH? $\#$$\#$

Y finalmente:

Pregunta 3: ¿Se consideró en absoluto una "versión monótona" de la clase P ? $\#$

NB Tenga en cuenta que estoy hablando de una clase muy restringida de circuitos: ¡circuitos aritméticos monótonos ! En la clase de circuitos , sería injusto preguntar en absoluto la pregunta 1: no hay límites inferiores mayores que Ω ( n log n ) para tales circuitos, incluso cuando sea necesario para calcular un polinomio dado en todos se conocen entradas en R n . Además, en la clase de tales circuitos, un "análogo estructural" de la Pregunta 1: ¿hay # P -polinomios completos que se pueden decidir por tamaño de polietileno { + , $\{+,-,\times\}$$\Omega(n\log n)$$\mathbb{R}^n$$\#$ -circuitos? - Tiene una respuesta afirmativa. Tal es, por ejemplo, el polinomio permanente PER = ∑ h ∈ S n ∏ n i = 1 x i , h ( i ) . $\{+,-,\times\}$$=\sum_{h\in S_n}\prod_{i=1}^n x_{i,h(i)}$

AGREGADO: Tsuyoshi Ito respondió la pregunta 1 con un truco muy simple. Aún así, las preguntas 2 y 3 permanecen abiertas. El estado de conteo de PATH es interesante en sí mismo, tanto porque es un problema DP estándar como porque es # P-complete.

(Estoy publicando mis comentarios como respuesta en respuesta a la solicitud del OP).

En cuanto a la Pregunta 1, dejemos que f _n : {0,1} ⁿ → ℕ sea una familia de funciones cuyo circuito aritmético requiere un tamaño exponencial. Entonces también lo hace f _n +1, pero f _n +1 es fácil de decidir por un circuito aritmético monótono trivial. Si prefiere evitar constantes en los circuitos aritméticos monótonos, entonces f _n : {0,1} ⁿ → ℕ sea una familia de funciones de modo que el circuito aritmético para f _n requiera un tamaño exponencial y f _n (0, ..., 0) = 0, y considere f _n + x ₁ +… + x _n .