Wymiar VC wielomianów nad tropikalnymi półksiężycami?

$\mathbf{BPP}$$\mathbf{P}$$\mathrm{poly}$ $(\max,+)$$(\min,+)$

Niech będzie na pół wieku. Zerowej wzorzec sekwencji z wielomianów jest podzbiorem , dla których istnieją , a taki sposób, aby dla wszystkich , f i ( x ) = Y IFF ı ∈ S . Oznacza to, że wykresy dokładnie tych wielomianów f i z i ∈ S muszą trafić w punkt ( x ,$R$$(f_1,\ldots,f_m)$$m$$R[x_1,\ldots,x_n]$$S\subseteq \{1,\ldots,m\}$$x\in R^n$$y\in R$$i=1,\ldots,m$$f_i(x)= y$$i\in S$$f_i$$i\in S$$(x,y)\in R^{n+1}$ . („Wzór zerowy”, ponieważ warunek$f_i(x)=y$ można zastąpić$f_i(x)-y=0$ ). Niech$Z(m)$ = maksymalna możliwa liczba wzorów zerowych sekwencji$m$ wielomiany stopnia co najwyżej$d$ . Stąd$0\leq Z(m)\leq 2^m$ . Wymiar Vapnik-Chervonenkiswielomianów stopnia $d$ wynosi $VC(n,d) := \max\{m\colon Z(m)=2^m\}$ .

Uwaga: Zazwyczaj wymiar VC jest definiowany dla rodziny ${\cal F}$ zestawów jako największa liczność $|S|$z szeregu $S$ w taki sposób, $\{F\cap S\colon F\in{\cal F}\}=2^S$ . Aby dopasować się do tej ramki, możemy skojarzyć z każdą parą $(x,y)\in R^{n+1}$ zbiór $F_{x,y}$ wszystkich wielomianów stopnia f ≤ d, dla których f $f$$\leq d$$f(x)=y$ trzyma. Zatem wymiar VC rodziny${\cal F}$ wszystkich takich zbiorów$F_{x,y}$ jest dokładnie$VC(n,d)$ .

Trywialna górna granica na m = V C ( n , d ) wynosi m ≤ n log | R | (potrzebujemy co najmniej 2 m różnych wektorów x ∈ R n, aby mieć wszystkie 2 m możliwych wzorów), ale jest to bezużyteczne w nieskończonych półporównaniach. Aby mieć dobre górne granice wymiaru VC, potrzebujemy dobrych górnych granic na Z ( m ) . Ponad polami takie granice są znane.$m=VC(n,d)$$m\leq n\log |R|$$2^m$$x\in R^n$$2^m$$Z(m)$

Twierdzenie 1: Na dowolnym polu R mamy Z ( m ) ≤ ( m d + $R$n ) . $Z(m)\leq \binom{md+n}{n}$

Podobne górne granice wcześniej udowodnili Milnor , Heintz i Warren ; ich dowody wykorzystują ciężkie techniki z prawdziwej geometrii algebraicznej. Natomiast półstronicowy dowód twierdzenia 1 Ronyai, Babai i Ganapathy (który podajemy poniżej) jest prostym zastosowaniem algebry liniowej.

Szukając małych m spełniających ( m d + $m$n ) <2m, otrzymujemy, że VC(n,d)=O(nlogd)utrzymuje się na dowolnympolu. Biorąc pod uwagęBPPvs.P/poly, ważne jest tutaj, że wymiar jestlogarytmicznytylkow stopniud. Jest to ważne, ponieważ obwody wielomianowe mogą obliczać wielomiany o wykładniczym stopniu oraz ponieważ wynik Hausslera w uczeniu się PAC (wniosek 2 na stronie 114$\binom{md+n}{n} < 2^m$$VC(n,d)=O(n\log d)$$\mathbf{BPP}$$\mathbf{P}$$\mathrm{poly}$$d$ten artykuł ) daje następujące wyniki (przy założeniu, że obwody deterministyczne mogą wykorzystywać większość głosów do wyprowadzania swoich wartości).

Twierdzenie 2: B P P ⊆ P / p o l y dotyczy obwodów w dowolnym półprzewodniku R , gdzie V C ( n , d ) jest tylko wielomianem w n i log d . $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$$R$$VC(n,d)$$n$$\log d$

Zobacz tutaj, jak wynik Hausslera implikuje Twierdzenie 2.

W szczególności, zgodnie z twierdzeniem 1 B P P ⊆ P / P O l Y posiada na dowolną dziedzinie. (Interesujące jest tutaj tylko pole nieskończone : w przypadku skończonych działają znacznie prostsze argumenty: Chernoff związany jest wtedy.) Ale co z (nieskończonymi) półpierścieniami, które nie są polami, a nawet nie dzwonią? Zmotywowani programowaniem dynamicznym, interesują mnie głównie tropikalne ( maksimum , + ) i ( min , + ) semirings, ale interesujące są również inne semirings „non-field” (nieskończone). Pamiętaj, że ponad ( $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$$(\max,+)$$(\min,+)$, + ) semiring, wielomian f ( x ) = ∑ a ∈ A c a ∏ n i = 1 x a i i z A ⊆ N i c a ∈ R , zamienia się w problem maksymalizacji f ( x ) = max a ∈ A { c a + a 1 x 1 + a 2 x $(\max,+)$$f(x)=\sum_{a\in A} c_a\prod_{i=1}^n x_i^{a_i}$$A\subseteq\mathbb{N}$$c_a\in \mathbb{R}$ + ⋯ + a n x n } ; stopień F jest (jak zwykle) maksimum o 1 + ⋯ + z n na całej w ∈ A .$f(x)=\max_{a\in A}\ \{c_a+a_1x_1+a_2x_2+\cdots+a_nx_n\}$$f$$a_1+\cdots+a_n$$a\in A$

Pytanie: Czy wymiar VC stopnia wielomianów stopnia ≤ d względem wielomianów tropikalnych półwymiarów w n log d ? $\leq d$$n\log d$

Przyznaję, że odpowiedź na szybką odpowiedź może być trudna: algebra tropikalna jest raczej „szalona”. Ale może ktoś ma jakieś pomysły, dlaczego (jeśli w ogóle) tropikalne wielomiany mogą wytwarzać więcej zerowych wzorów niż prawdziwe wielomiany? Lub dlaczego „nie powinni”? Lub niektóre powiązane odniesienia.

A może dowód na to, że Babai, Ronyai i Ganapathy (poniżej) można w jakiś sposób „przekręcić” do pracy nad tropikalnymi półksiężycami? Lub nad jakimkolwiek innym nieskończonym półkolem (które nie są polami)?

Dowód twierdzenia 1: Załóżmy, że sekwencja ( f 1 , … , f m ) ma p różnych wzorów zerowych i niech v 1 , … , v p ∈ R n będą świadkami tych wzorów zerowych. Niech S i = { k : f k ( v i ) ≠ 0 } będzie wzorem zerowym obserwowanym przez i -ty wektor v i , i rozważmy wielomiany $(f_1,\ldots,f_m)$$p$$v_1,\ldots,v_p\in R^n$$S_i=\{k\colon f_k(v_i)\neq 0\}$$i$$v_i$i : = ∏ k ∈ S i f k . Twierdzimy, że te wielomiany są liniowo niezależne od naszego pola. Twierdzenie to uzupełnia dowód twierdzenia, ponieważ każdy g i ma stopień co najwyżej D : = m d , a wymiar przestrzeni wielomianów stopnia co najwyżej D wynosi ( n + $g_i:=\prod_{k\in S_i}f_k$$g_i$$D:=md$$D$D ) . Aby udowodnić twierdzenie, wystarczy zauważyć, żegi(vj)≠0wtedy i tylko wtedy, gdySi⊆Sj. Załóżmy, że przeciwnie, istnieje nietrywialna zależność liniowa λ1gi(x)+⋯+λpgp(x)=0. Niechjbędzie indeksem takim, że| Sj| minimalna wśródSIz$\binom{n+D}{D}$$g_i(v_j)\neq 0$$S_i\subseteq S_j$$\lambda_1 g_i(x)+\cdots+\lambda_p g_p(x)=0$$j$$|S_j|$$S_i$$\lambda_i\neq 0$. Substitute $v_j$ in the relation. While $\lambda_jg_j(v_j)\neq 0$, we have $\lambda_ig_i(v_j)=0$ for all $i\neq j$, a contradiction. $\Box$

I've realized that the answer to my question is - yes: the VC dimension of degree $\leq d$ polynomials on $n$ variables over any tropical semiring is at most a constant times $n^2\log(n+d)$. This can be shown using Theorem 1 above. See here for details. So, BPP $\subseteq$ P/poly holds also for tropical circuits and, hence, also for "pure" dynamic programming algorithms.

---

N.B. (added 25.06.2019) In the mean time, I've resolved the problem completely in this paper. In such a generality, which I haven't even dreamed at the beginning. Tropical case is here just a very, very special case. And even more curiously: by just an appropriate combination of already know (deep in any respect) results of other authors.

What remains else to do in this (BPP vs. P/poly) direction? Besides the decrease of the size of resulting deterministic circuits (an interesting question in itself).