Un polynôme difficile à compter mais facile à décider?

Chaque circuit arithmétique monotone , c'est-à-dire un circuit $\{+,\times\}$ , calcule un polynôme multivarié avec des coefficients entiers non négatifs. Étant donné un polynôme , le circuitf ( x 1 , … , x n$F(x_1,\ldots,x_n)$$f(x_1,\ldots,x_n)$

• calcule si est valable pour tout ; F ( a ) = f ( a ) a ∈ N$f$$F(a)=f(a)$$a\in \mathbb{N}^n$
• compte si est valable pour tout ; F ( a ) = f ( a ) a ∈ { 0 , 1 } $f$$F(a)=f(a)$$a\in\{0,1\}^n$
• décide si exactement quand est valable pour tout . F ( a ) > 0 f ( a ) > 0 a ∈ { 0 , 1 } $f$$F(a)>0$$f(a)>0$$a\in\{0,1\}^n$

Je connais des polynômes explicites (même multilinéaires) montrant que l'écart de taille de circuit "calcule / compte" peut être exponentiel. Ma question concerne l'écart "compte / décide".$f$

Question 1: Quelqu'un connaît-il un polynôme qui est exponentiellement plus difficile à compter que de décider par des circuits ? { + , × $f$$\{+,\times\}$

Comme candidat possible, on pourrait prendre le polynôme PATH dont les variables correspondent aux bords du graphe complet sur , et chaque monôme correspond à un chemin simple du nœud au nœud dans . Ce polynôme peut être déterminé par un circuit de taille implémentant, par exemple, l'algorithme de programmation dynamique de Bellman-Ford, et il est relativement facile de montrer que chaque PATH de calcul de circuit doit ont la taille . { 1 , … , n } 1 n K $K_n$$\{1,\ldots,n\}$$1$$n$$K_n${ + , × $O(n^3)$$\{+,\times\}$$2^{\Omega(n)}$

D'autre part, chaque circuit de comptage permet de résoudre le PATH problème PATH, par exemple compte le nombre de -à- chemins dans le spécifié par le correspondant - entrée de sous - graphe . Il s'agit d'un soi-disant problème P -complet . Donc, nous "croyons" tous que PATH ne peut avoir aucun circuit de comptage de taille polynomiale. Le "seul" problème est de le prouver ... 1 n 0 1 K n #$\#$$1$$n$$0$$1$$K_n$$\#$$\{+,\times\}$

Je peux montrer que chaque circuit de comptant un polynôme de chemin hamiltonien connexe HP nécessite une taille exponentielle. Les monômes de ce polynôme correspondent à des trajets dans contenant tous les nœuds. Malheureusement, la réduction de HP en PATH par Valiant nécessite de calculer l'inverse de la matrice Vandermonde, et ne peut donc pas être implémentée par un circuit .$\{+,\times\}$n K $1$$n$$K_n$# { + , × $\#$$\#$$\{+,\times\}$

Question 2: Quelqu'un a-t-il vu une réduction monotone de HP à PATH? $\#$$\#$

Et enfin:

Question 3: une "version monotone" de la classe P a-t-elle été envisagée? $\#$

NB : je parle d'une classe de circuits très restreinte: les circuits arithmétiques monotones ! Dans la classe des circuits , la question 1 serait tout simplement injuste de se poser du tout: pas de bornes inférieures plus grandes que pour de tels circuits, même lorsqu'il est nécessaire de calculer un polynôme donné sur toutes les entrées de , est connu. De plus, dans la classe de ces circuits, un "analogue structurel" de la question 1 - existe-t-il des polynômes P complets qui peuvent être déterminés par des circuits de taille poly ? - a une réponse affirmative. Tel est, par exemple, le polynôme permanent PER . Ω ( n log n ) R n # { + , - , × } = ∑ h ∈ S n ∏ n i = 1 x i , h ( i $\{+,-,\times\}$$\Omega(n\log n)$$\mathbb{R}^n$$\#$$\{+,-,\times\}$$=\sum_{h\in S_n}\prod_{i=1}^n x_{i,h(i)}$

AJOUT: Tsuyoshi Ito a répondu à la question 1 avec une astuce très simple. Pourtant, les questions 2 et 3 restent ouvertes. Le statut de comptage de PATH est intéressant en soi parce qu'il s'agit d'un problème DP standard et parce qu'il est # P-complet.

(Je poste mes commentaires en réponse à la demande du PO.)

Quant à la question 1, soit f _n : {0,1} ⁿ → ℕ une famille de fonctions dont le circuit arithmétique nécessite une taille exponentielle. Il en va de même pour f _n +1, mais f _n +1 est facile à décider par un circuit arithmétique monotone trivial. Si vous préférez éviter les constantes dans les circuits arithmétiques monotones, alors f _n : {0,1} ⁿ → ℕ soit une famille de fonctions telles que le circuit arithmétique pour f _n nécessite une taille exponentielle et f _n (0,…, 0) = 0, et considérons f _n + x ₁ +… + x _n .