Ce înseamnă exact „Extinderea unui polinom”?

Aceasta din manuscrisul unei cărți despre dovezi de cunoștințe zero - https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

3.5 Extensii de grad scăzut și multiliniare Let $\mathbb F$ fie orice câmp finit și fie $f : \{0, 1\}^v \rightarrow \mathbb F$ fie oricare funcția de mapare a hipercubului boolean v-dimensional la $\mathbb F$. A $v$-polinom variabil $g$ peste $\mathbb F$ se spune că este o extensie de $f$ dacă $g$ este de acord cu toate intrările cu valori booleene, adică $g(x) = f (x)$ pentru toți $x \in \{0, 1\}^v$

Nu pot să înțeleg ce înseamnă asta.

• Nu cred că aici vorbesc despre câmpuri de extensie - adică atunci ar fi făcut-o $\mathbb F_p$ & $\mathbb F_{p^n}$

• cred $\{0,1\}^v$ este un pic șir de $v$ biți. Sau îl interpretez greșit?

• $f$ este o hartă - totuși cred că este și un polinom. Este probabil sub forma unui polinom de grad maxim $v$ și își ia coeficienții de la $\mathbb F_2$.

• Și $g$ este un alt polinom. Totuși, nu îmi este clar în ce domeniu $g$ ia coeficientul din.

• $g$ este o $v$ polinom variat. Deci, ce face exact $f(x) = g(x)$ pentru toți $x \in \{0, 1\}^v$ Rău. Dacă $g$ este un polinom multivariat, atunci g nu poate fi evaluat doar cu $x$ ca intrare - are nevoie $v$ diferite variabile pentru evaluare, de ex. $g(x_1, x_2 .... x_v)$. Deci cum avem $f(x) = g(x)$?

Una peste alta, nu înțeleg ce este această „Extensie a unui polinom”? Poate cineva să mă ghideze spre a înțelege ce înseamnă definiția citată.

Poate că un nume mai cunoscut pentru această tehnică este aritmetizarea. Ideea generală din spatele acesteia este de a codifica logica booleană în polinoame de grad scăzut, care (din anumite motive tehnice) au disponibile diverse tehnici analitice utile (probabil cel mai evident lema Schwartz-Zippel). Acest lucru este util în special pentru a demonstra corectitudinea dovezilor interactive și a fost cheia pentru demonstrația lui Shamir de $\mathsf{IP} = \mathsf{PSPACE}$.

$f$ este o hartă - totuși cred că este și un polinom. Este probabil sub forma unui polinom de grad maxim $v$ și își ia coeficienții de la $\mathbb{F}_2$.

Chiar dacă te poți gândi la $f$ ca polinom, este mai bine să nu. Avem un obiect de calcul „standard” inițial pe care dorim să-l analizăm, ceea ce înseamnă de obicei

• o formulă booleană sau
• un circuit boolean sau
• un tabel de adevăr.

Le puteți vedea pe toate ca polinoame $\mathbb{F}_2$ (și, probabil, asta este exact ceea ce sunt circuitele booleene), dar uneori veți avea o formulă în schimb sau orice altceva.

Ideea din spatele găsirii unui polinom de extensie (sau, după cum am spus mai devreme, apelarea la „aritmetizare”) este de a codifica acest obiect (standard) ca polinom $g(x) \in \mathbb{F}[x_1,\dots,x_v]$ care "este de acord cu" $f(x)$ in sensul că

$$\forall (x_1,\dots,x_v)\in\{0,1\}^v : f(x_1,\dots,x_v) = g(x_1,\dots,x_v).$$

Acest lucru se poate face cu ușurință pentru anumite operațiuni, de exemplu $g_{ȘI}(x,y) = xy$ este extensia lui AND, $g_{NU}(x) = 1-x$ este extensia lui NOT. Pentru alte operațiuni este puțin mai puțin simplu, de exemplu $$g_{XOR}(x,y) = x+y-2xy = 1 - (xy - (1-x)(1-y)).$$ este aritmetizarea XOR (cred), și poate nu este evidentă în prealabil.

În comentarii ați întrebat de ce ne pasă. Poate că cea mai bună motivație este lema Schwartz-Zippel, dar lema sa tehnică despre care este utilitatea poate să nu fie utilă imediat. „Elevator Pitch” pentru aritmetizare este

1. a fost cheia dovedirii $\mathsf{IP} = \mathsf{PSPACE}$ (prin protocolul „sumcheck” al lui Shamir), unul dintre primele rezultate mari în sistemele de dovezi interactive și
2. dovada acestui rezultat a fost foarte special (nerelativizant și nu o dovadă naturală). Se poate spune că „aritmetizarea” este una dintre ~3 sau 4 tehnici fundamentale de demonstrare pe care le cunoaștem în teoria complexității. Până în 2009, principalele tehnici „mare” au avut încă o șansă să arate asta $\mathsf{P} \neq \mathsf{NP}$ --- nu mai are totuși o șansă.

Oricum, pentru o referință explicită la carte, știu că cel puțin este conținută în Arora & Barak's Complexitatea computațională: o abordare modernă. Folosind ctrl+f pentru a căuta „aritmetizare” vă duce imediat la capitolul 8.5.2, care discută abordarea. În general, căutarea pe acest termen va fi probabil mult mai fructuoasă decât „polinomul de extensie”, care poate avea mai multe ciocniri accidentale de nume.