Oceniając multilinearyzację obwodu arytmetycznego?

Niech $p(x_1,\ldots,x_n)$ jest wielomianem wielu zmiennych współczynnikach nad polem $F$ . Multilinearization z $p$ , oznaczony przez , jest wynikiem zastąpienia wielokrotnie każdy o o . Wynikiem jest oczywiście wielomianowy wielomian. $\hat{p}$ $x_i^d$ $d > 1$ $x_i$

Rozważmy następujący problem: podany arytmetyczna obwód przez i biorąc pod uwagę pole elementów , obliczyć . $C(x_1,\ldots,x_n)$ $F$ $a_1,\ldots,a_n$ $\hat{C}(a_1,\ldots,a_n)$

Pytanie: Zakładając, że arytmetykę pola można wykonać w jednostce czasu, czy istnieje do tego algorytm wielomianowy? Dodane później: Byłbym również zainteresowany szczególnym przypadkiem, w którym jest tak naprawdę formułą (obwód fan-out ). $C$ $1$

cc.complexity-theory polynomials

— slimton
źródło

Dlaczego miałoby to być równoważne z obliczeniem mocy wyjściowej obwodu zamkniętego? Problem m przeciwległych jest to, że układ może mieć rozłączne ścieżki wejścia

kilka wewnętrznych węzłów mnożenie i oceny każdego z tych wewnętrznych węzłów mnożenia wymaga zastąpienia

w jednej ścieżce i

w drugim . W obwodzie z wykładniczą liczbą ścieżek wygląda na to, że istnieje wykładnicza liczba przypadków do załatwienia.

x_{i}

$x_i$

x_{i}

$x_i$

a_{i}

$a_i$

1

$1$

— slimton,

@Kaveh: Nie rozumiem. Spójrz na obwód

. Jeśli po prostu zastąpić węzeł wejściowy

przez węzeł z wartością

i ocenić w sposób standardowy skończyć się powrotem

zamiast . Model obliczeniowy: po prostu normalny czas wielomianowy na maszynach Turinga. Pomyśl o polu jako o

dla konkretności, jeśli chcesz.

(x * x)

$(x * x)$

x

$x$

a

$a$

a^{2}

$a^2$

a

$a$

Z / 3 Z

$Z/3Z$

— slimton,

@Kaveh: Nie rozumiem, w jaki sposób taki algorytm implikuje to, co mówisz, ale w rzeczywistości jest to sprzeczne z powszechną hipotezą złożoności obwodu arytmetycznego: że Permanent nie ma obwodów arytmetycznych o wielkiej wielkości (ponad polami innymi niż F_2). Rozważmy wielomian

. Część wieloliniowa

tego wielomianu ma właściwość polegającą na tym, że jej najwyższy stopień (

) to po prostu

p = \prod_{i} (\sum_{j} x_{i j} y_{j})

$p=\prod_i(\sum_j x_{ij} y_j)$

q

$q$

= 2 n

$=2n$

. Jeśli istnieje mały obwód arytmetyczny obliczający

, wówczas można pokazać, że istnieje mały obwód arytmetyczny obliczający

r = y_{1} y_{2} \dots y_{n} P e r (x_{11}, \dots, x_{n n})

$r = y_1y_2\cdots y_n Per(x_{11},\ldots,x_{nn})$

q

$q$

r

$r$

— Srikanth,

@ Srikanth: Nie widziałem twojego komentarza przed opublikowaniem mojej odpowiedzi (która okazała się być tą samą konstrukcją, którą podałeś w komentarzu). Od tego czasu usunąłem moją odpowiedź i powinieneś opublikować swój komentarz jako odpowiedź.

— Joshua Grochow

@Joshua: Nie dodałem swojego komentarza jako odpowiedzi, ponieważ nie rozumiem, dlaczego konstrukcja Kaveha działa. Widzę, że obwód arytmetyczny oblicza wielomian, który zgadza się z wieloliniowością na wszystkich wejściach, ale nie jestem pewien, czy formalnie oblicza wieloliniowość danego wielomianu (patrz moje komentarze po odpowiedzi Kaveha). Moja konstrukcja (i twoja) zakłada, że multilinearyzacja jest obliczana formalnie.

— Srikanth,

Odpowiedzi:

W przypadku, gdy pole ma rozmiar co najmniej , myślę, że ten problem jest trudny. Mówiąc dokładniej, myślę, że jeśli powyższe można skutecznie rozwiązać dla tak dużego , to CNF-SAT ma wydajne algorytmy losowe. Powiedzmy, że otrzymaliśmy wzór CNF . Można łatwo wymyślić arytmetyczna obwodem , który oblicza się `arithmetization„” o , gdzie wielomian zgadza się ze wzoru na - wejściach. Rozważmy multilinearization z . Zauważ, że $F$ $2n$ $F$ $\varphi$ $C$ $p$ $\varphi$ $p$ $\varphi$ $0$ $1$ $q$ $p$ $q$ zgadza się z a zatem dniu . $p$ $\varphi$ $\{0,1\}^n$

Twierdzę, że jest niezerowe, iff jest zadowalające. Oczywiście, jeśli , to nie może być spełnione. Z drugiej strony można pokazać, że żaden niezerowy wielomian wielomianowy nie może zniknąć na wszystkich . To implikuje, że niezerowe (i stąd odpowiadające ) nie znika przy niektórych danych wejściowych w . $q$ $\varphi$ $q=0$ $\varphi$ $\{0,1\}^n$ $q$ $\varphi$ $\{0,1\}^n$

Dlatego sprawdzenie zgodności jest równoważne sprawdzeniu, czy jest niezerowe. Powiedz teraz, że możemy ocenić na dużym polu . Następnie, korzystając z Schwartz-Zippel Lemma, moglibyśmy przetestować tożsamość przy użyciu wydajnego algorytmu losowego i sprawdzić, czy jest to zerowy wielomian (wielkość jest używana do górnej granicy błędu w Schwartz-Zippel Lemma). $\varphi$ $q$ $q$ $F$ $q$ $F$

— Srikanth
źródło

Wydaje mi się, że F jest polem stałym, ponieważ w danych wejściowych nie ma niczego, co określa F. Należy również zauważyć, że pytanie zakłada, że operacje w polu zajmują czas jednostkowy.

— Kaveh

Dzięki Srikanth. Jak zgadł Kaveh, rzeczywiście interesowałem się ustalonym przypadkiem pola skończonego, ale ta odpowiedź, którą dałeś, pomaga mi lepiej zrozumieć pytanie.

— slimton,

$C(\vec{x}) \in F(\vec{x})$ $\vec{a}$ $C$ $\vec{a}$ $\vec{b}$ $p$ $b_i$ $k$ $b_{i,k}$

$P \subseteq P/poly$ $M$

$C$ $M$ $C$

$F_p$ $x^{p-1}$ $1$ $0$ $p-1$ $f \land g$ $f.g$ $f \lor g$ $f+g-f.g$ $\lnot f$ $1-f$

$F_p$ $b_i$ $\sum_{0 \leq k \leq p-1}{kb_{i,k}}$

$F_p$ $\bmod 3$ $2x(x+1)$ $2x(x+2)$ $x \in F_3$

Łączenie to mamy arytmetyczną obwodu nad obliczeniowej wielofunkcyjnego linearyzację o rozmiarze polynomail w rozmiarze . $F_p$ $C$ $C$

— Kaveh
źródło

Nie jest dla mnie jasne, dlaczego opisany obwód arytmetyczny oblicza wieloliniową , a nawet wielomianową wielomianową. Jestem tylko w stanie zobaczyć, że obwód arytmetyczną oblicza jakiś wielomian, że zgadza się z multilinearization z na - wejść.

C

$C$

C

$C$

0

$0$

1

$1$

— Srikanth,

@ Srikanth: arytmetyczna wersja obwodu logicznego (z pewnymi ustalonymi wejściami) oblicza wieloliniową wersję , nie musi to być wieloliniowa. Wtedy jedynym problemem jest to, że wejścia / wyjścia są w wartościach binarnych, a nie w , więc po prostu muszę naprawić kodowanie wejścia / wyjścia z binarnych na oryginalne wartości wejściowe i wyjściowe. Powstały obwód jest układem arytmetycznym, który pobiera wartości dla zmiennych , koduje je binarnie, oblicza wartość multilinaryzacji na tych wejściach i wysyła odpowiedź w formacie binarnym, a następnie tłumaczy je z powrotem na .

M

$M$

C

$C$

F_{p}

$F_p$

C

$C$

C

$C$

F_{p}

$F_p$

— Kaveh,

[nadal] Wynikiem jest arytmetyczną z obwodu tych samych czynników, które ma, oraz z tych samych wyjść i jest obliczenie multilinearization z .

C

$C$

C

$C$

— Kaveh

@Kaveh: Czy założyłeś, że wejście do obwodu logicznego ma taką samą postać jak wyjście ? W każdym razie nadal nie jestem przekonany. Jest całkowicie możliwe, aby obwód arytmetyczny obliczył wielomian który zgadza się z wielomianem na wszystkich wejściach z pola, a jednak . Na przykład wielomian zgadza się z na wszystkich wejściach, a jednak nie są one równe wielomianom. Skąd wiesz, że obwód nie oblicza po prostu wielomianu nieliniowego, który zgadza się z multilinaryzacją na wszystkich wejściach?

M

$M$

M

$M$

f

$f$

g

$g$

f \neq g

$f\neq g$

x^{p}

$x^p$

x

$x$

M

$M$

C

$C$

— Srikanth

@ Srikanth: Opisałem formę danych wejściowych i wyjściowych w mojej odpowiedzi. Dane wejściowe do są binarne, dane wyjściowe mają postać podaną powyżej. Nie powiedziałem, że to multilinear, powiedziałem tylko, że oblicza multilinearization o .

M

$M$

M

$M$ $C$

— Kaveh