Gibt es Polynome, die schwer zu zählen, aber leicht zu entscheiden sind?

Jede monotone arithmetische Schaltung , dh eine -Schaltung, berechnet ein multivariates Polynom mit nichtnegativen ganzzahligen Koeffizienten. Bei einem Polynom ist die SchaltungF ( x 1 , … , x n ) f ( x 1 , … , x n$\{+,\times\}$$F(x_1,\ldots,x_n)$$f(x_1,\ldots,x_n)$

• berechnet wenn für alle ; F ( a ) = f ( a ) a ≤ N$f$$F(a)=f(a)$$a\in \mathbb{N}^n$
• zählt wenn für alle ; F ( a ) = f ( a ) a ∈ { 0 , 1 } $f$$F(a)=f(a)$$a\in\{0,1\}^n$
• entscheidet wenn genau dann, wenn für alle a \ in \ {0,1 \} ^ n gilt . F ( a ) > 0 f ( a ) > 0 a ∈ { $f$$F(a)>0$$f(a)>0$$a\in\{0,1\}^n$

Ich kenne explizite Polynome $f$ (sogar mehrlinear), die zeigen, dass die Lücke der Schaltungsgröße "rechnet / zählt" exponentiell sein kann. Meine Frage betrifft die Lücke "zählt / entscheidet".

Frage 1: Kennt jemand ein Polynom $f$ das exponentiell schwerer zu zählen ist als durch $\{+,\times\}$ -Schaltungen zu bestimmen?

Als ein möglicher Kandidat könnte man das PATH-Polynom nehmen, dessen Variablen Kanten des vollständigen Graphen $K_n$ auf $\{1,\ldots,n\}$ , und jedes Monom entspricht einem einfachen Pfad von Knoten $1$ zu Knoten $n$ in $K_n$ . Dieses Polynom kann entschieden durch eine Schaltung der Größe $O(n^3)$ Umsetzung der , sagen wir, die Bellman-Ford dynamischen Programmieralgorithmus, und es ist relativ leicht zu zeigen , dass alle $\{+,\times\}$ -Schaltung Berechnung Pfad muss haben Größe $2^{\Omega(n)}$ .

Auf der anderen Seite, jede Strecke Zählen des PATH löst $\#$ PATH Problem, zählt , dh die Anzahl der $1$ -zu- $n$ Pfade in dem angegebenen durch den entsprechenden $0$ - $1$ Eingang Subgraph von $K_n$ . Dies ist ein so genanntes $\#$P -komplette Problem . Wir alle "glauben" also, dass PATH keine Zählkreise $\{+,\times\}$ mit polynomieller Größe haben kann. Das "einzige" Problem ist , dies zu beweisen ...

Ich kann zeigen, dass jeder $\{+,\times\}$ -Kreis, der ein verwandtes Hamilton- Pfadpolynom HP zählt, eine exponentielle Größe benötigt. Monome dieses Polynoms entsprechen $1$ zu- $n$ Pfaden in $K_n$ die alle Knoten enthalten. Leider erfordert die Reduktion von $\#$ HP zu $\#$ PATH durch Valiant die Berechnung der Umkehrung der Vandermonde-Matrix und kann daher nicht von einer $\{+,\times\}$ Schaltung implementiert werden.

Frage 2: Hat jemand eine monotone Reduzierung von $\#$ HP auf $\#$ PATH gesehen?

Und schlussendlich:

Frage 3: Wurde eine "monotone Version" der Klasse P überhaupt in Betracht gezogen? $\#$

NB Beachten Sie, dass ich über eine sehr eingeschränkte Klasse von Schaltungen spreche: monotone Rechenschaltungen! In der Klasse der -Circuits wäre Frage 1 überhaupt nicht fair zu stellen: Keine Untergrenze größer als für solche Circuits, auch wenn dies zur Berechnung erforderlich ist Ein gegebenes Polynom für alle Eingaben in ist bekannt. Auch in der Klasse solcher Schaltungen gibt es ein "strukturelles Analogon" von Frage 1 - Gibt es P- vollständige Polynome, die durch Poly-Size -Schaltkreise entschieden werden können? - hat eine positive Antwort. Dies ist beispielsweise das permanente Polynom 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)}$

ADDED: Tsuyoshi Ito beantwortete Frage 1 mit einem sehr einfachen Trick. Die Fragen 2 und 3 bleiben weiterhin offen. Der Zählstatus von PATH ist an sich schon deshalb interessant, weil es sich um ein Standard-DP-Problem handelt und weil es # P-vollständig ist.

(Ich poste meine Kommentare als Antwort auf die Anfrage des OP.)

Was Frage 1 betrifft, sei f _n : {0,1} ⁿ → ℕ eine Familie von Funktionen, deren arithmetische Schaltung eine Exponentialgröße erfordert. Dann so tut f _n + 1, aber f _n + 1 ist einfach durch eine triviale monotone Rechenschaltung zu entscheiden. Wenn Sie Konstanten in monotonen Arithmetikschaltungen vermeiden möchten, dann sei f _n : {0,1} ⁿ → ℕ eine Familie von Funktionen, so dass die Arithmetikschaltung für f _n Exponentialgröße und f _n (0,…, 0) erfordert. = 0 und betrachte f _n + x ₁ +… + x _n .