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