Jakiś wielomian, który trudno policzyć, ale łatwo go wybrać?

Każdy monotoniczny obwód arytmetyczny , tj. Obwód , oblicza pewną wielomianową wielomian z nieujemnymi współczynnikami całkowitymi. Biorąc pod uwagę wielomian , obwódF ( x 1 , … , x n ) f ( x 1 , … , x n$\{+,\times\}$$F(x_1,\ldots,x_n)$$f(x_1,\ldots,x_n)$

• oblicza $f$ jeśli $F(a)=f(a)$ dla wszystkich $a\in \mathbb{N}^n$ ;
• zlicza $f$ jeśli $F(a)=f(a)$ dla wszystkich $a\in\{0,1\}^n$ ;
• decyduje $f$ jeśli $F(a)>0$ dokładnie wtedy, gdy $f(a)>0$ odnosi się do wszystkich $a\in\{0,1\}^n$ .

Znam wyraźne wielomiany $f$ (nawet wieloliniowe) pokazujące, że przerwa w obwodzie „oblicza / liczy” może być wykładnicza. Moje pytanie dotyczy luki „liczy / decyduje”.

Pytanie 1: Czy ktoś zna jakiś wielomian $f$ który jest wykładniczo trudniejszy do policzenia, niż decydowanie o układach $\{+,\times\}$ ?

Jako potencjalny kandydat można wziąć wielomian PATH, którego zmienne odpowiadają krawędziom pełnego wykresu $K_n$ na $\{1,\ldots,n\}$ , a każdy monomial odpowiada prostej ścieżce od węzła $1$ do węzła $n$ w $K_n$ . O tym wielomianu może decydować obwód o rozmiarze $O(n^3)$ implementujący, powiedzmy, algorytm programowania dynamicznego Bellmana-Forda, i stosunkowo łatwo jest pokazać, że każdy $\{+,\times\}$ obwód obliczający PATH musi mieć rozmiar $2^{\Omega(n)}$ .

Z drugiej strony, każdy obwód liczący ŚCIEŻKA rozwiązuje problem ŚCIEŻKA, tzn. Zlicza liczbę ścieżek -do- w określonym przez odpowiedni wejściowej - . Jest to tak zwany problem P - kompletny . Wszyscy więc „wierzymy”, że ŚCIEŻKA nie może mieć żadnych obwodów -w obwodzie wielomianowym. „Jedynym” problemem jest udowodnienie, że ... 1 n 0 1 K n #$\#$$1$$n$$0$$1$$K_n$$\#$$\{+,\times\}$

Mogę pokazać, że każdy obwód zliczający powiązany wielomian HP na ścieżce hamiltonowskiej wymaga wielkości wykładniczej. Monomialy tego wielomianu odpowiadają - - ścieżkom w zawierającym wszystkie węzły. Niestety, redukcja z HP do ścieżkę Valiant wymaga, aby obliczyć odwrotność macierzy Vandermonde, a zatem nie mogą być realizowane przez Circuit.$\{+,\times\}$n K $1$$n$$K_n$# { + , × $\#$$\#$$\{+,\times\}$

Pytanie 2: Czy ktoś widział monotoniczną redukcję HP do ŚCIEŻKI? $\#$$\#$

I w końcu:

Pytanie 3: Czy w ogóle rozważano „wersję monotoniczną” klasy P ? $\#$

Uwaga Należy pamiętać, że mówię o bardzo ograniczonej grupy obwodów: Monotone obwodów arytmetyka! W klasie obwodów pytanie 1 byłoby niesprawiedliwe, jeśli w ogóle zadawano by pytania: nie ma niższych granic większych niż dla takich obwodów, nawet jeśli jest to wymagane do obliczeń dany wielomian na wszystkich wejściach w , jest znany. Ponadto, w klasie takich obwodów „analogiem strukturalnym” pytania 1 - czy istnieją P -kompletne wielomiany, o których można decydować w układach wielorakich ? - ma odpowiedź twierdzącą. Taki jest na przykład stały wielomian PER . Ω ( n log n ) R n$\{+,-,\times\}$$\Omega(n\log n)$$\mathbb{R}^n$$\#$= ∑ h ∈ S n ∏ n i = 1 x i , h ( i $\{+,-,\times\}$$=\sum_{h\in S_n}\prod_{i=1}^n x_{i,h(i)}$

DODANE: Tsuyoshi Ito odpowiedział na pytanie 1 bardzo prostą sztuczką. Mimo to pytania 2 i 3 pozostają otwarte. Stan liczenia PATH jest interesujący sam w sobie, ponieważ jest to standardowy problem DP i ponieważ jest on # P-complete.

(Publikuję swoje komentarze jako odpowiedź w odpowiedzi na prośbę PO).

Jeśli chodzi o pytanie 1, niech f _n : {0,1} ⁿ → ℕ będzie rodziną funkcji, których obwód arytmetyczny wymaga wielkości wykładniczej. Następnie tak nie f _n + 1, lecz f _n +1 jest łatwo zdecydować przez obwód arytmetyczna trywialne monotonii. Jeśli wolisz, aby uniknąć stałych monotonnie arytmetycznych obwodów, pozwól f _n : {0,1} ⁿ → ℕ będzie rodziną funkcji takich, że obwód arytmetyczny dla f _n wymaga wykładniczy rozmiar i f _n (0, ..., 0) = 0 i rozważmy f _n + x ₁ +… + x _n .