Złożoność testowania wartości a obliczanie funkcji

Ogólnie wiemy, że złożoność testowania, czy funkcja przyjmuje określoną wartość na danym wejściu, jest łatwiejsza niż ocena funkcji na tym wejściu. Na przykład:

• Ocena stałej nieujemnej liczby całkowitej jest # P-trudna, ale powiedzenie, czy taka stała jest zerowa czy niezerowa jest w P (dopasowanie dwustronne)

• Istnieje n liczb rzeczywistych , tak że wielomian ma następujące właściwości (w rzeczywistości większość zestawów liczb rzeczywistych będzie miało te właściwości) . Dla danych wejściowych sprawdzenie, czy ten wielomian jest zerowy, wymaga mnożenia i porównań (według wyniku Ben-Or , ponieważ zbiór zerowy ma składników), ale ocena powyższego wielomianu zajmuje co najmniej kroki, autor: Paterson-Stockmeyer .∏ n i = 1 ( x - a i ) n x Θ ( log n ) n Ω ( $a_1,...,a_n$$\prod_{i=1}^{n}(x - a_i)$$n$$x$$\Theta(\log n)$$n$$\Omega(\sqrt{n})$

• Sortowanie wymaga kroków na drzewie porównania (także kroków na prawdziwym algebraicznym drzewie decyzyjnym, ponownie według wyniku Ben-Or), ale sprawdzenie, czy lista jest posortowana, wykorzystuje tylko Porównania .Ω ( n log n ) n - $\Omega(n \log n)$$\Omega(n \log n)$$n-1$

Czy istnieją ogólne warunki na wielomianu, które są wystarczające, aby sugerować, że (algebraiczna) złożoność testowania, czy wielomian jest zerowy, jest równoważna złożoności oceny wielomianu?

Szukam warunków, które nie zależą od wcześniejszego poznania złożoności problemów.

( Wyjaśnienie 10/27/2010 ) Dla jasności, wielomian nie jest częścią danych wejściowych. Oznacza to, że biorąc pod uwagę stałą rodzinę funkcji (po jednym dla każdego rozmiaru wejściowego (długość bitów lub liczba wejść)), chcę porównać złożoność problemu językowego / decyzyjnego ze złożonością oceny funkcji .$\{ f_n \}$ $\{ X : f_n(X) = 0 \text{ where } n \text{ is the "size" of } X \}$ $\{f_n\}$

Wyjaśnienie: Pytam o asymptotyczną złożoność oceniania / testowania rodzin wielomianów. Na przykład ponad stałym polem (lub pierścieniem, takim jak ) „permanent” nie jest pojedynczym wielomianem, ale nieskończoną rodziną gdzie jest stałą macierzy na tym polu (lub pierścieniu). { p e r m n : n ≥ 0 } p e r m n n × $\mathbb{Z}$$\{perm_{n} : n \geq 0 \}$$perm_{n}$$n \times n$

W przypadku testowanie na zero i ocena są „prawie” takie same w następującym znaczeniu: Załóżmy, że masz drzewo decyzyjne, które sprawdza, czy jakiś nieredukowalny wielomian jest niezerowy. Pracujemy nad , dlatego możemy testować tylko równość, ale nie mamy „<”. To ważna różnica w stosunku do drugiego przykładu w pytaniu! Teraz wybierz typową ścieżkę, tj. Ścieżkę podjętą przez prawie wszystkie dane wejściowe (zawsze podążamy za odgałęzieniem " "). Ponadto obierz typową ścieżkę wszystkich elementów w odmianie . Niech będzie węzłem, w którym te dwie ścieżki po raz pierwszy przyjmują inną gałąź. Niech f C ≠ V ( f ) v h 1 , … , h m V ( f ) V ( f ) v V ( h m ) f ( x ) = 0 h i x h 1 ⋯ h m f g = h 1 ⋯ h m g f f f ( x ) = $\mathbb{C}$$f$$\mathbb{C}$$\not=$$V(f)$$v$$h_1,\dots,h_m$być wielomianami testowanymi wzdłuż wspólnego przedrostka dwóch ścieżek. Ponieważ jest zamknięte, wszystkie elementy leżące w i osiągające również leżą w . Dlatego jeśli , to jeden z znika na . Stosujemy Nullstellensatz Hilberta do i otrzymujemy to dla niektórych wielomianów które coprime do . Krótko mówiąc, chociaż nie obliczamy , decydując, czy , musimy obliczyć dla jakiegoś coprime$V(f)$$V(f)$$v$$V(h_m)$$f(x) = 0$$h_i$$x$$h_1 \cdots h_m$$f g = h_1 \cdots h_m$$g$$f$$f$$f(x) = 0$$fg$$g$.

Prawdopodobnie trafne jest „Algorytmiczne zastosowanie twierdzenia Fefermana – Vaught”. Definiuje wielomiany poprzez zsumowanie struktur definiowanych przez MSOL na wykresach i pokazuje, że można je ocenić, gdy wykresy są ograniczone do szerokości drzewa.

Nie mówi to wiele o różnicy w złożoności testowania / oceny poza byciem FPT. Testowanie wartości oznacza pytanie, czy istnieje ustawienie zmiennych takich, że podana formuła MSO2 na danym wykresie ocenia się na prawdę, podczas gdy szacowanie obejmuje zliczanie ponad satysfakcjonujące przypisania formuły MSO2. Wydaje się, że jest to związane z pytaniem, w jaki sposób złożoność zliczania SAT odnosi się do złożoności SAT.

Edytuj 10/29 Inną przydatną koncepcją może być przyjrzenie się jednolitej trudnej własności punktu. Najwyraźniej wielomiany z tą właściwością są albo łatwe do oceny we wszystkich punktach, albo trudne do oceny prawie w każdym punkcie. Makowski podaje referencje na slajdach 46-52 - http://www.cs.technion.ac.il/admlogic/TR/2009/icla09-slides.pdf

Zaryzykuję pomysł, że ocena wielomianu w F p dla stałej liczby pierwszej p (lub dowolnego jego skończonego rozszerzenia pola i przy współczynnikach ograniczonych do tego samego pola) będzie pasować do twojego kryterium.$q(x)$$\mathbb F_p$$p$

bardziej konkretnie, rozważmy wielomian w . Wiemy, że x 2 = x w F 2 , więc jeśli założymy, że jakikolwiek wielomian jest już w formie zredukowanej, gdy jest podawany jako dane wejściowe, pozostawiamy po prostu rozważenie jednego z: 0 , 1 , x , x + 1 i odpowiednią ocenę dowolny z tych wielomianów o wartości 0 lub 1 zajmuje najwyżej 2 operacje arytmetyczne.$\mathbb F_2[x]$$x^2=x$$\mathbb F_2$$0,1,x,x+1$$0$$1$

Uważam, że podobna instrukcja „stały czas poprzez stałą liczbę operacji arytmetycznych” ma zastosowanie bardziej ogólnie dla gdzie q = p n, gdzie p jest liczbą pierwszą. zwróć uwagę, że jeśli n nie jest ustawione, to stwierdzenie nie jest już prawidłowe$\mathbb F_q$$q=p^n$$p$$n$

Nie jestem pewien, czy dobrze rozumiem pytanie, ale pozwól mi rzucić nieco światła.

Zazwyczaj ocena wielomianu przy określonych wartościach jest łatwiejsza niż testowanie tożsamości, szczególnie gdy reprezentacja wielomianu odbywa się za pomocą obwodu (pewna zwięzła reprezentacja). Istnieje jednak wiele algorytmów losowego testowania tożsamości ( Schwarz-Zippel jest najbardziej prosty), które działają tylko na ewaluacje.

$n^{O(1)}$

$x_i \mapsto y^{2^i}$$\sum_{i\in S} \alpha_i y^{a_i}$$y^r - 1$$r$$r$$y^a$$y^b$$y^r - 1$$r$$a - b$$r$$\prod_{i,j\in S} (a_i - a_j)$$r$

Osiągnięto większy postęp w zakresie algorytmów testowania czarnej skrzynki. W tej chwili większość z nich stoi na ograniczonych głębokościach 3 obwodów (suma iloczynów sum zmiennych). (FWIW) Niektóre z nich wymienione są bardziej szczegółowo w Rozdziale 3 i 4 mojej pracy magisterskiej . Niedawno wprowadzono także dalsze ulepszenia przez Saxenę i Seshadri .

$1-xy$$x$$y$$\mathbb{Z}[x_1,...,x_n]$$n$