[SCRÂȘIT] [FOSȘIT] [CLIC] MICHAEL SIPSER: Bine ai revenit. Sper că ați avut o Ziua Recunoștinței bună și toți împrospătați și gata să vă gândiți la o teorie a calculului. Suntem în cursa acasă acum. Mai avem această prelegere și încă două. Și așa că astăzi, am pentru voi, o completare a teoremei pe care am început-o înainte de pauză, în care am introdus calculul probabilistic și am vorbit despre clasa BPP, după cum sper să vă amintiți, și am analizat, în special, aceste probleme care implică programe de ramificare, de unde am început demonstrarea că problema echivalenței a două programe de ramificare read-once poate fi rezolvată în această clasă BPP. Așa că ceea ce voi face este să petrec primele 15 minute sau cam așa ceva doar analizând unde am fost, pentru că am început asta, se simte demult acum. Și vreau doar să mă asigur că sunteți pe aceeași pagină și că ne amintim cu toții ce făceam. Și apoi, voi termina dovada. Și împreună cu aceasta, vom introduce o metodă importantă. Ei bine, noi am început asta. Ne-am uitat la metoda de aritmetizare data trecută. Deci vom revizui asta. Vom folosi asta din nou în lucrarea pe care o vom începe joi cu privire la sistemele de dovezi interactive . Deci, acesta este un fel de, într-un fel, atât o teoremă interesantă în sine, cât și o pregătire pentru ceea ce vom face în ultimul subiect al semestrului. BINE. Deci, să ne amintim ce făceam. Așa că am introdus mașinile Turing probabilistice. Deci acelea sunt aceste mașini care au... un fel de mașină nedeterministă, dar există o regulă diferită pentru acceptare. Și acestea sunt, de asemenea, mașini nedeterministe care pot fie să facă o singură alegere, doar pentru a avea o mișcare deterministă la un pas, fie pot face două alegeri. Și când mașina face două alegeri, ne gândim de fapt că există o probabilitate acolo, în care mașina aruncă o monedă pentru a decide pe ce ramură să meargă. Deci, cu asta, există un copac de ramuri posibile. Și probabilitatea unei anumite ramuri va fi 1 peste 2 la numărul de aruncări de monede pe acea ramură. Și așa o folosim apoi pentru a defini probabilitatea pe care mașina o acceptă, care este suma tuturor probabilităților ramurilor care acceptă. Iar probabilitatea ca acesta să respingă este 1 minus probabilitatea ca acesta să accepte. Deci, gândindu-mă la asta, aceasta surprinde ideea că dacă rulați mașina pe un set aleatoriu de intrări de la aruncările de monede, care este probabilitatea ca mașina să accepte. Aceasta este probabilitatea de acceptare, definită în acest fel. Acum, dacă ne gândim la mașina care decide un anumit limbaj, ar trebui să accepte șirurile din limbă și să respingă șirurile care nu sunt în limbaj. Dar, din cauza naturii probabilistice a mașinii, ar putea primi răspunsul greșit pe unele ramuri. Și așa spunem că o mașină decide un limbaj cu o anumită probabilitate de eroare, înseamnă că probabilitatea de a obține un răspuns greșit va fi, cel mult, acel epsilon de probabilitate de eroare peste toate intrările posibile ale mașinii. Deci, dacă spunem că mașina are probabilitatea de eroare 1/3, înseamnă că primește răspunsul corect pentru fiecare șir cu probabilitate de cel puțin 2/3. OK, așa că asta ne-a condus la definirea acestei clase de complexitate BPP, pe care nici nu-mi amintesc dacă v-am spus ce înseamnă. Este un timp polinom probabilist mărginit. Asta înseamnă BPP. Mijlocul „mărginit” este delimitat de 1/2 pentru că nu vrem să permitem mașinii să aibă probabilitate 1/2, pentru că atunci se întâmplă lucruri rele. Aparatul poate doar să arunce o monedă atunci când decide să dea un răspuns și să nu ne ofere cu adevărat nicio informație. Apoi, am trecut și peste lema de amplificare. Nu am dat dovada, dar am trecut peste enunțul teoremei. Dovada este de fapt doar un calcul că puteți reduce acea probabilitate de eroare la ceva extrem de mic doar prin repetarea mașinii și luând votul majoritar din ceea ce face în mai multe runde diferite. Dacă rulați mașina de 100 de ori și vedeți dacă în mare parte acceptă, atunci doriți să acceptați. Și șansele ca mașina să fie cu adevărat părtinitoare spre respingere, deși sunteți în eșantionul dvs., să vedeți în mare parte acceptarea, sunt extrem de mici. Și poți să calculezi asta, dar poți să faci asta foarte mic. Atât de mic încât, pentru toate scopurile practice, îți oferă într-adevăr răspunsul corect. Dar nu este determinist. Deci nu este chiar 100% garantat. Și felul în care îmi place să mă gândesc la BPP în ceea ce privește arborele de calcul al mașinii, astfel încât atunci când acceptă, majoritatea ramurilor acceptă, ponderate de probabilitatea lor, desigur. Deci, există multe ramuri care acceptă atunci când accepți și multe ramuri care resping atunci când respingi. Deci, un alt mod de a spune același lucru. Acum, vom interveni direct cu un check-in. Și acesta este puțin mai mult, nu tocmai materialul cursului, ci un pic mai mult din partea filozofică. Dar să vedem cum te descurci cu el. Când rulați de fapt o mașinărie probabilistică, vă imaginați că mașina, așa cum o descriem noi în mod informal , aruncă monede. De fiecare dată are un non-determinist - de fiecare dată are de ales. Deci, alegerea aruncă o monedă pentru a decide în ce direcție să meargă. Desigur, un computer adevărat nu are o monedă de aruncat, probabil. Ei bine, poate că ați putea construi ceva hardware în mașină care să îi permită să acceseze aleatoriu într-un anumit sens. Poate că folosește un efect mecanic cuantic pentru a obține o valoare aleatorie sau poate că folosește cronometrul. Nu sunt exact sigur. Vă puteți imagina că aveți o grămadă de moduri de a implementa asta. O modalitate tipică prin care oamenii implementează aleatoritatea într-un algoritm este să folosească un generator de numere pseudoaleatoare , care este o procedură care vă poate oferi un fel de valoare care pare aleatorie, dar care poate să nu fie de fapt aleatorie. De exemplu, vă oferă cifrele lui pi. Dacă doriți binar, care exprimă pi ca un număr binar, atunci ați putea calcula diferitele cifre succesive ale lui pi și să le utilizați ca pentru generatorul de numere aleatorii. Desigur, aceasta este o procedură deterministă, deci nu este chiar întâmplătoare. Dar adesea, oamenii folosesc astfel de lucruri atunci când simulează mașini aleatorii. Deci ce crezi despre a face asta? Am putea folosi un generator pseudo-aleatoriu ca sursă de aleatorie pentru algoritmul nostru randomizat? Da, sau nu, sau ce crezi? Deci, haideți să lansăm un sondaj în acest sens, ca să văd ce părere aveți despre utilizarea generatoarelor de numere pseudoaleatoare în loc de aleatorietatea adevărată pentru algoritmii noștri. Îți voi acorda câteva secunde, un minut pentru a analiza asta. BINE. Vom închide asta. Toată lumea a participat cine vrea? 1, 2, 3. OK. Da, cred că probabil cel mai bun răspuns este A. Să aruncăm o privire. Au fost câteva răspunsuri aici care, într-adevăr, nu fac... care nu sunt la fel de bune. Aș spune, B, ei bine, de obicei oamenii cred că generatoarele pseudoaleatoare sunt niște proceduri destul de rapide. Nu sunt chiar atât de interesante, în rest. Deci nu aș spune că B este o alegere bună, deoarece sunt de obicei destul de rapid de implementat. C este o alegere mai proastă, chiar și pentru că mașinile Turing pot face orice poate face orice alt algoritm. Deci, cu siguranță, dacă există un generator de numere pseudoaleatoare și există, atunci l-ați putea implementa pe mașina Turing. D este un răspuns interesant, pentru că spui, ei bine, asta ar implica că P este egal cu BPP dacă ai putea simula de fapt aleatoritatea cu o procedură deterministă. Dar, de fapt, motivul pentru care nu aș alege D este pentru că este perfect de imaginat că P este egal cu BPP. Nu știm că P este diferit de BPP, așa că este de imaginat că sunt egali. Și, de fapt, cred că dacă ai chestiona cei mai mulți teoreticieni ai complexității, cei mai mulți oameni din domeniul meu ar crede că P este egal cu BPP tocmai din acest motiv, că, dacă ai avea generatoare de numere pseudoaleatoare suficient de bune , ai putea elimina probabilitatea din acestea. calcule probabilistice. Le puteți rula doar pe generatorul de numere pseudoaleatoare. Și, de fapt, există o teorie în jurul căreia a fost dezvoltată. Dar în prezent , nu știm cum să dovedim că au existat generatoare de numere pseudoaleatoare . Și are unele, de fapt, există de fapt, într-o anumită linie a acestei cercetări, o anumită legătură cu problema P versus NP, dar nu știm cum să dovedim că există generatoare de numere pseudoaleatoare suficient de bune care ți-ar permite să rulați-le pe un algoritm probabilistic și aveți un comportament garantat, care este la fel de bun ca rularea unor numere cu adevărat aleatorii în algoritmul probabilistic. Și deci răspunsul pe care l-aș alege ar fi A, că l-ai putea folosi, sigur. S- ar putea să primiți răspunsul corect, dar nu este garantat. Pur și simplu nu știm cum să facem analiza pentru generatoarele de numere pseudoaleatoare. Și dacă ai avea unele destul de bune, ar arăta că P este egal cu BPP. Dar asta ar putea fi, de fapt, corect... asta ar putea fi de fapt adevărat. OK, deci hai să continuăm. Și amintiți-vă, acum, programele de ramificare. Aveam astfel de rețele de noduri și margini. Și a existat o procedură, vom vedea din nou câteva exemple , unele dintre cele pe care le-am avut înainte, unde aveți programe de ramificare care arată așa. Și aveți o grămadă de noduri de interogare. Te uiți la setările variabilelor pentru a decide dacă să cobori la 0 muchie sau la 1 muchie. Și, în cele din urmă, veți ajunge la un nod de ieșire și acesta va fi rezultatul programului de ramificare. Și în acest fel, aceste programe de ramificare au definit funcții booleene, de la setările variabilelor de intrare la o ieșire 0 sau 1. Acum, s-ar putea să aveți două programe de ramificare și să vă întrebați dacă calculează aceeași funcție booleană sau nu. Și testarea este o problemă completă a conp, așa cum vi se cere să arătați în temele. Acum, dacă programul de ramificare, totuși, are o restricție, și anume că nu este permis să se solicite interogarea aceleiași variabile de mai multe ori pe o cale, atunci cu această restricție, îl numim un program de ramificare care se citește o dată . Și atunci, situația pentru testarea echivalenței pare să fie diferită. De fapt, putem oferi un algoritm BPP pentru testarea echivalenței programelor de ramificare read-once, chiar dacă un astfel de lucru este puțin probabil să fie cazul pentru programele generale de ramificare din cauza completității coNP. OK, deci sper că te simți confortabil și cu mine în tot acest raționament. BINE. În regulă. Deci, ideea pentru a demonstra acest lucru este că ceea ce vom face este să luăm cele două programe de ramificare și să le rulăm pe o intrare selectată aleatoriu. Dar, așa cum am observat data trecută, dacă le rulați doar pe o intrare booleană selectată aleatoriu unde atribuim variabilele 0 și 1, atunci asta nu vă oferă răspunsul corect cu o probabilitate mare, deoarece cele două programe de ramificare ar putea fi diferite. , calculând diferite funcții booleene, dar diferă doar pentru o singură setare de intrare. Și apoi, doar alegându- le la întâmplare, nu vei avea o probabilitate foarte mare de a găsi acel singur loc de diferență. Deci, în schimb, ceea ce vom face este să definim o modalitate de a rula aceste programe de ramificare pe intrări non-booleene, unde variabilele sunt setate la alte valori decât 0 și 1-- 2, 3, 7, 22-- și facem sensul asta. Și apoi argumentați că, prin rularea celor două programe de ramificare pe o intrare non-booleană selectată aleatoriu, aceasta este probabilitatea foarte mare de a vă oferi răspunsul corect. Deci, cumva, extinzând domeniul posibilităților, îți vei spori foarte semnificativ șansele de a obține răspunsul corect. BINE. Deci, chiar dacă aceste două programe de ramificare ar putea fi de acord cu aproape toate intrările booleene, vom arăta că făcând această aritmetizare-- deci aceasta este metoda-- dacă ele nu sunt într-adevăr echivalente, vor diferă aproape tot timpul pe domeniul extins. OK, și atunci avem dovada. Acolo va fi munca de astăzi. BINE. Deci de ce nu ne oprim și să ne asigurăm că suntem cu toții împreună în acest sens? Pot răspunde la orice întrebări. Voi revizui, de asemenea, cum decurge aritmetizarea. Dar asta voi face mai departe. Deci, suntem cu toții în regulă cu asta? Bun. Deci hai să mergem mai departe. Deci, pentru a trece la înțelegerea a ceea ce înseamnă să rulezi programele de ramificare pe aceste valori non-booleene , va trebui să obținem o perspectivă oarecum diferită asupra calculului unui program de ramificare. Deci, perspectiva standard este că vă luați setarea, atribuirea dvs. la intrare, care este 0,1,1 pentru x1, x2 și x3, și să utilizați asta pentru a urma o cale de execuție prin mașină. Deci știm că x1 este 0, x2 este 1, x3 este 1, rezultatul este 1, așa cum am indicat cu galben. Această altă perspectivă spune, ei bine, vom opera prin etichetarea nodurilor și marginilor mașinii. Și asta va avea o corespondență foarte directă cu perspectiva căii de execuție. Deci, vom eticheta toate nodurile și marginile de pe cale cu un 1, așa cum este indicat în galben, și toate nodurile și marginile care nu sunt pe cale, toate celelalte noduri și margini vor fi etichetate 0. Deci, urmând 1-urile, este ca pesmetul din Hansel și Gretel. Aceasta este calea pe care trebuie să o urmați pentru a trece prin mașină. 0-urile sunt locurile în care nu mergi. OK, deci eticheta de ieșire, aici, ieșirea va fi eticheta unui singur nod de ieșire, indiferent de ceea ce etichetați. Pentru că dacă este un 1, înseamnă că calea a mers la 1, iar dacă este un 0, înseamnă că calea nu a mers la 1, a mers la 0. Deci, doar privind această valoare, puteți vedea care este ieșirea mașinii. În regulă. Deci, să descriem un mod diferit de a defini această etichetare fără doar să ne uităm la cale. Ei bine, va surprinde exact același lucru. Deci, vom spune, dacă ați etichetat deja un nod, vă voi spune cum să etichetați cele două margini care emană din acel nod. Voi eticheta o margine a și variabila de interogare. De ce este asta? Ei bine, a va fi fie 0, fie 1. Și ne va spune dacă calea a intrat sau nu în acel nod. Deci, dacă este 1, a intrat în acel nod, dacă este 0, nu a intrat în acel nod. Singurul mod în care va merge în această ramură aici este dacă a intrat în nodul xi. Dacă nu a intrat în nodul xi, nu există nicio modalitate de a merge în această ramură. Deci vom merge și acea valoare. Așadar, singura modalitate prin care poți coborî în această ramură este dacă a trecut prin acel nod-- deci aceasta este a, valoarea lui a-- și xi este a 1. De aceea spunem a și xi. Deci trebuie să înțelegi această mică expresie aici. Dacă nu înțelegi asta, ești toast. Bine, așa că înțelegeți mai bine asta ca să putem merge mai departe. Mă bucur să răspund la o întrebare. Acestea sunt cele mai simple întrebări, uneori cele mai valoroase. Dacă nu înțelegi de ce îl etichetez astfel, trage-mi o conversație. BINE. Acum, cealaltă ramură, o să spun, ei bine, voi coborî pe această margine doar dacă, ei bine, a este adevărat, așa că am trecut prin acel nod. Și xi este fals. Deci acesta va fi a și complementul lui xi. În regulă. Așa le voi eticheta. Acesta este un alt mod, oferind aceste expresii pentru etichetarea acestor margini pe baza etichetei nodului respectiv. Și, în mod similar, pentru a completa imaginea, trebuie să vă spun cum să etichetați nodurile în funcție de marginile care intră în el. Deci, dacă știu că am a1, a2 și a3, care îmi spun starea în ceea ce privește calea dacă calea a trecut prin oricare dintre aceste margini, ei bine, știu că va merge la acel nod dacă sau dintre aceste valori-- dacă calea a trecut prin aici, sau a trecut prin acolo, sau a trecut prin acolo, atunci va merge la acel nod. De aceea sau este ceea ce trebuie spus. Așa că asta îmi oferă un alt mod de a construi etichetarea aici fără măcar să vorbesc despre căi. Așa cum o descriu, susțin că va da același rezultat. În regulă. Deci există o întrebare. Putem spune rapid din nou de ce nu putem face asta pe Boolean? Nu sunt sigur că înțeleg întrebarea. Așa că trimite-mi-l din nou. În acest moment, totul este boolean. Nu am făcut încă nimic, din punct de vedere aritmetic. Și motivul pentru care nu putem trăi doar în lumea booleană este că, doar luând aici valori booleene ale atribuirilor booleene , nu avem o probabilitate suficient de mare de a găsi o diferență între cele două mașini. În regulă. Deci hai sa continuam. În regulă. Așa că acum, voi vorbi despre cum vom extinde acest lucru la cazul non-boolean, folosind metoda de aritmetizare. Deci, în primul rând, aritmetizarea este o simulare a și și sau cu plus și timpi, astfel încât dacă mă gândesc la adevărat ca 1 și fals ca 0, aceasta îmi va oferi o simulare fidelă. Va face ceea ce trebuie. Va calcula exact aceleași valori la care ne așteptăm. Deci ca a și b, ei bine, timpii funcționează la fel ca și. Funcționează pentru 1 și 0 ca adevărat și fals, timpii funcționează exact ca și. Și negația este 1 minus. Sau va fi suma minus produsul. Și apoi, acestea vă oferă doar valorile corecte, a sau b. Dacă îl calculezi doar introducând 1 sau 0, obții răspunsul corect doar folosind această aritmetică. Deci, acum, ceea ce vom face, în loc să folosim etichetarea booleană, vom folosi doar etichetarea aritmetică. Dar va calcula exact același lucru, deoarece aritmetica simulează booleanul. Deci trecem întotdeauna prin nodul de pornire. Deci, nu există nicio îndoială despre etichetarea nodului de început cu un 1. Dar acum, voi da expresii la fel ca expresiile booleene, dar acum vor folosi plus și times în loc de ands și ors. Deci, să vedem. Amintiți-vă ce am făcut de înainte. Am avut a și xi pentru această margine. O să-l înlocuiesc. Ce este și? Căutăm doar aici în tabelul nostru, în tabelul nostru de traducere. Și devine vremuri. Așa că o vom înlocui cu un ori xi. Și va funcționa exact la fel. Dar diferența este că acest lucru are sens chiar și atunci când avem valori non-booleene. Timpul și plus sunt definite pentru valori non-booleene, în timp ce și și sau nu sunt. Deci, ce se întâmplă pe marginea asta? Ei bine, acesta a fost a și complementul lui xi, după cum vă amintiți. Deci asta va deveni ori 1 minus xi. Și apoi, în mod similar, am avut sau aici. Și iată un mic truc, dar asta va fi important pentru analiza pe care o vom face. În loc să folosim rețeta pentru sau în termeni de plus și timpi, vom avea ceva puțin mai simplu. Va fi doar suma. Și motivul pentru care funcționează -- bine de înțeles -- este că, din cauza naturii aciclice a programelor de ramificare, cel mult una dintre aceste margini poate avea o cale prin ea. Deci, acesta este un fel de foarte special sau, uneori numit disjunct sau. Nu ai voie ca mai mult de una dintre valori să fie 1, pentru că asta nu se întâmplă niciodată când ai un grafic aciclic. Niciodată nu poți avea calea să coboare în acest fel și apoi, din nou, să coboare în acel fel. Atunci ar fi intrarea în acel nod de două ori. Trebuie să fie un ciclu. Așa că va fi suficient de bun pentru noi și necesar pentru a reprezenta asta sau ca o sumă. BINE. Așa că cred că asta este tot ce am vrut să spun pe acest slide. Deci cineva se întreabă, este posibil ca unele dintre aceste valori să fie negative? Da. Așa cum stau lucrurile acum, unele dintre aceste valori pot fi negative. Nu am pus nicio restricție cu privire la valorile care vor fi. Deci intrarea ar putea fi un număr negativ. Și apoi, o să se întâmple lucruri negative. De fapt, aici se fac scăderi. Deci, chiar și cu numere pozitive, cred că am făcut un exemplu data trecută. Cred că voi face din nou acel exemplu de exclusivitate sau, în care apar numere negative. Asta nu contează. Dar, de fapt, ceea ce vom ajunge să facem este să facem aceste calcule modulo un număr prim q. BINE. Voi alege unele prime precum 17 și voi face toate calculele mod 17. Și motivul pentru care procedăm astfel este de fapt pentru că vom alege alocații aleatorii ale variabilelor ca intrare. Și este cel mai logic să faci asta atunci când ai un set limitat de posibilități de a le ridica. Deci nu vom alege ca un număr întreg aleatoriu. Există infinit de posibilități. Și da, ai putea crea o distribuție acolo, dar asta e foarte complicat. Asta chiar ar putea funcționa. Nu sunt sigur. De fapt, nu am trecut prin această analiză. Dar modul în care oamenii fac acest lucru este să se uite la ceea ce se numește un câmp finit. Așa că voi vorbi despre asta într-o secundă. De ce există cel mult unul dintre a1, a2 și a3? 1s-- Voi spune încă o dată-- dar 1-urile corespund căii. Deci acesta este un 1 dacă calea a mers în acest fel. Gandeste-te la asta. Calea nu poate trece prin a1 și poate trece, în același timp, prin a2, deoarece asta înseamnă că calea a trecut prin acest nod. Atunci, cum va ajunge la a2? Va trece prin acel nod de două ori. Într-un grafic aciclic, nu puteți avea o cale care trece prin același nod de mai multe ori. Deci va trebui să te gândești la asta. OK, hai să mergem mai departe. Așa că acum vom vorbi despre același lucru -- ne vom uita la acea etichetare non-booleană aplicată unui exemplu. Deci, aici este un program de ramificare foarte simplu care calculează de fapt exclusivitatea sau funcția în lumea booleană. Deci aceasta este etichetarea pe care tocmai am dezvoltat-o ​​pentru tine, etichetarea aritmetică. Și etichetăm întotdeauna nodul de pornire cu 1, pentru că calea trece întotdeauna prin acolo. Și acum, să ne uităm la asta înainte de a trece înainte, hai să ne uităm la această margine aici. Amintește-ți ce este. Aici trebuie să aplicăm această regulă. Aceasta este marginea care iese dintr-un nod care este deja etichetat. Deci este acea etichetă de pe acel nod înmulțit cu xi. Pentru că dacă te gândești la asta, asta e și, surprinde și. Deci este doar un timp xi. Deci este x1, în acest caz. Deci x1 este un 2 în intrarea noastră. Deci va fi 1, care este a, ori x1, care este 2. Deci această margine este etichetată 2. Acum, aceasta-- bine, OK, să ne uităm la această margine acum. Cred că asta urmează. Acesta este 1 minus xi, este 1 minus x1. Deci este 1 minus 2. Deci vei ajunge cu minus 1. 1 minus ori minus 2. 1 ori 1 minus 2, care este minus 1, deci este minus 1. Acum le vom eticheta. două noduri folosind cealaltă regulă. Deci, acesta primește un 2 pentru că aceasta este o sumă a marginilor de intrare. Acesta primește un minus 1, deoarece aceasta este suma marginilor sale de intrare. Și acum ne vom uita la... în ce ordine am făcut asta? OK, o să fac această margine acum. 0 margine, care va fi de 2 ori 1 minus variabila sa. Deci este 1 minus x2. X2 este un 3. Deci este 1 minus 3 până la minus 2. Deci de 2 ori minus 2 este minus 4. OK, nu vreau să mă grăbesc prin asta. Nu are rost să vorbești. Încerc doar să lucrez acest exemplu, ca să înțelegeți ideea. OK, deci ai putea să o completezi singur pe următorul? Deci aceasta este singura margine de ieșire din acest nod x2. Deci, x2 este etichetat cu 2 aici. Deci există a este 2. Aceasta este o margine care iese, deci este una pe această parte aici. Deci este de 2 ori x2. x2 este un 3, deci este de 2 ori 3. Deci acesta ar trebui să fie 6. Hopa. Chiar aici... 6. O să fac același lucru. Deci x2 este etichetat minus 1. Deci minus 1 ori 1 minus. Deci primești un 2 aici, primești un minus 3 aici, doar urmând, din nou, același proces. Și acum, care este eticheta de pe acest nod 0 aici? Deci, din nou, luați suma etichetelor primite. Deci au fost un 2 și un 6. Deci acesta este un 8. Și acesta este un minus 3 și un minus 4. Deci este un minus 7. Care este rezultatul? Ieșirea este minus 7, deoarece aceasta este eticheta de pe 1 nod. OK, ieșirea este minus 7. OK. Deci acesta va fi modul nostru de a defini ieșirea unui program de ramificare atunci când are o setare non-booleană la intrările sale. Dacă ați avea setarea booleană pe intrările sale și ați urma această procedură, ce ați obține? Veți obține același răspuns pe care l-ați obține urmând calea, deoarece simularea aritmetică este o simulare fidelă a ands și ors. Și și-urile și sau-urile surprind exact când... ce face calea. Deci aceasta este o extensie strictă a funcționării programului de ramificare într-un domeniu nou, aceste valori non-booleene. Pe tărâmul vechi, se comportă exact așa cum a făcut inițial. Și asta este esențial pentru a înțelege asta. Da, cineva întreabă care este valoarea finală a 0-urilor, și ele ar fi aceleași. Sigur. În cazul boolean, dacă urmărim acest lucru în cazurile booleene, toate etichetele ar fi exact ceea ce au fost. Ar fi doar 0 și 1 pe care le aveam de înainte. Așadar, acesta imită exact x sau dacă luați toate modurile 2? Nu știu. Ar trebui să mă gândesc la asta. Nu cred că asta este esențial. În acest caz, s- ar putea să se comporte corect dacă luați răspunsul mod 2 pentru XOR. Dar XOR-ul va fi foarte special. Și nu sunt sigur. S-ar putea întâmpla să fie adevărat. Ar trebui să mă gândesc la asta o secundă, dar nu sunt sigur că este relevant. OK, deci aceasta este o întrebare bună. Dacă aș alege un alt program de ramificare care implementează și XOR-- sau-- deci ar fi un program de ramificare echivalent-- s- ar comporta la fel și în cazul valorilor non-booleene? Și răspunsul la asta este da și nu. Înțelegi întrebarea? Este o întrebare foarte bună. Și de fapt, vom demonstra acest lucru în analiză. Va fi ușor de dovedit pentru că v-am oferit amândoi posibilități, da și nu. Dar hai să-ți spun ce vreau să spun prin asta. Deci intelegi intrebarea. Să presupunem că am un alt program de ramificare. Nu sunt sigur că poți veni cu un alt program de ramificare, dar să presupunem că ai putea. Aveți un alt program de ramificare, da, sigur că puteți veni -- puteți face variabilele într-o ordine diferită, de exemplu. Deci, să presupunem că ai venit cu un alt program de ramificare care îți oferă XOR. Și acum ai conectat 2 și 3. Aș obține întotdeauna aceeași valoare? Da, dacă acel alt program de ramificare a fost citit o dată. Nu, nu neapărat dacă nu este citit o dată. Și de aceea citirea o dată este esențială. După cum vom demonstra, pentru două programe de ramificare care se citesc o dată, dacă se comportă la fel pe valorile booleene, se comportă la fel chiar și pe valorile non-booleene. Acest lucru nu este neapărat adevărat dacă programele de ramificare nu sunt citite o singură dată. OK, vom vedea asta. Vom demonstra asta și vom folosi asta. Asta va fi important. OK, deci iată schița algoritmului, care este cam sugerată de această întrebare foarte bună. Deci ceea ce vom face este să dorim să luăm cele două programe de ramificare pe care încercăm să le testăm dacă sunt echivalente. Vom alege o atribuire aleatorie de intrare non-booleană - deci setați valorile alese aici din câmp, dar vom ajunge acolo. O valoare aleatoare pentru x1, valoare aleatoare pentru x2 și așa mai departe. Acestea ar putea fi numere precum 17, și 25 și 23 și așa mai departe. Și apoi, folosind acest proces, rulați programele de ramificare pentru a le evalua pe acea atribuire non-booleană. Dacă nu sunt de acord, atunci vom ști că cele două programe de ramificare nu au fost echivalente, chiar și în cazul non-boolean. Chiar și în cazul boolean. Am spus asta greșit? Deci, dacă nu sunt de acord, chiar și în cazul non-boolean, trebuie să fie un echivalent chiar și în cazul boolean. Nu este evident. Dar dacă sunt de acord, atunci nu este o garanție că sunt echivalente, dar va fi o dovadă foarte puternică că sunt echivalente. OK, deci aici va intra natura probabilistică . Așa că vom demonstra asta. Deci, mai întâi, trebuie să dezvoltăm un fapt algebric. Și asta implică polinoame. Acesta este un lucru simplu cu care cred că mulți dintre voi v-ați întâlnit deja, poate chiar în liceu. Nu voi demonstra faptele algebrice, dar le voi afirma. Și de fapt, dovezile nu sunt dure. Sunt în manual. Deci, să presupunem că avem aici un polinom de grad d. Se întâmplă să aibă p. Deci există o grămadă de constante. Aceste a sunt constante. x este variabila polinomului. Și presupun că ați văzut polinoame scrise așa. Și așadar, dacă atribuiți x unei valori, unei valori constante z și polinomul evaluează la 0, adesea numim asta o rădăcină a polinomului. Deci, acestea sunt locurile în care polinomul evaluează la 0 pe care le-am arătat aici. Acestea sunt rădăcinile. Nu este greu să arăți că un polinom de grad scăzut nu poate avea multe rădăcini. Practic, dacă polinomul are gradul cel mult d, poate avea cel mult d rădăcini, atâta timp cât polinomul în sine nu este polinomul 0 de peste tot, pentru că, evident, atunci totul este o rădăcină. Hopa, greșeală de scriere. Mulțumesc. Ar trebui să fie d minus 2 acolo. Prefă-te că e un 2. În regulă, deci dacă avem un polinom de grad scăzut... să nu ne devansăm. Dacă avem un polinom de grad scăzut, un polinom de grad de cel mult d, acesta are cel mult d rădăcini. Și asta e o dovadă simplă. Ideea de bază este de fiecare dată când aveți a-- dacă aveți o rădăcină a polinomului, deci dacă setarea x egală cu 5 vă oferă o rădăcină a polinomului, este un 0 a polinomului, atunci x-- puteți ușor să vezi că x minus 5 este un factor al polinomului. Puteți împărți cu x minus 5 și obțineți un nou polinom cu un grad mai mic. Și poți doar, care merge prin inducție, să aibă o rădăcină mai puțin. Deci, puteți împărți doar după rădăcini, practic. Este foarte simplu. Și un alt lucru foarte important -- dacă am două polinoame care sunt ambele de grad scăzut, nu pot fi de acord în foarte multe locuri. Asta rezultă din ceea ce tocmai am demonstrat mai sus. Pentru că ceea ce voi face este să iau acele două polinoame și ei se uită la diferență, care este, de asemenea, un polinom de grad scăzut. De fiecare dată când există un acord între cele două polinoame originale, există un zero al polinoamului diferență. Și pentru că acel polinom de diferență nu poate avea prea multe zerouri, cele două polinoame originale nu pot avea prea multe acorduri. Deci corolarul este că, dacă x și y sunt ambele polinoame de cel mult d, și nu sunt același polinom, pentru că atunci diferența ar fi polinomul 0, atunci numărul de locuri în care sunt egale este cel mult d. Deci, dovada constă doar să lăsăm p să fie diferența dintre p1 și p2 -- un tip foarte standard de truc. Acum, cele de mai sus vor fi valabile pentru orice domeniu. Un câmp este doar un set cu plus și timpi cu proprietățile familiare ale legii distributive și așa mai departe și identități și toate lucrurile pe care te- ai aștepta ca plus și timpi să le aibă în lumea normală. Și așa vom vorbi despre câmpul finit care are doar q elemente - care are exact q elemente, unde q este un număr prim. Deci, se dovedește că-- și nu voi demonstra toate acestea, dar sunt lucruri destul de simple-- că dacă luați doar numerele de la 1 la q minus 1-- de la 0 la q minus 1 și folosiți plus de n ori mod q, care are toate proprietățile potrivite pentru a fi un câmp. Așa că gândește-te la asta-- doar aritmetică modulară, modifică niște q prim. Și apoi putem alege într-un mod natural o atribuire aleatorie a unei variabile din câmp, deoarece este doar alegerea dintre q posibilități. Da, deci am o întrebare aici. Coeficienții polinomului și alocarea variabilelor-- toți vor veni din acest câmp. Deci totul va funcționa în acest domeniu. Nu lăsa asta să te arunce. Doar intuiția ta obișnuită despre modul în care funcționează aritmetica va fi bine. Dar acest lucru este important aici din perspectiva gândirii probabilistice la acest lucru. Așa că mă voi regândi la această lemă polinomială, care spune că nu există prea multe rădăcini. În ceea ce privește probabilitatea de a alege un element din câmp, care sunt șansele ca acesta să fie o rădăcină? Deci, dacă aveți un polinom de grad scăzut și alegeți o valoare aleatorie în câmp, care este probabilitatea să aveți o rădăcină? Ei bine, este doar numărul de rădăcini împărțit la dimensiunea câmpului. Deci, dacă aveți acest câmp foarte mare și aveți acest polinom de grad scăzut, va fi destul de puțin probabil să ajungeți să alegeți unul dintre zerouri, una dintre rădăcini, doar la întâmplare. Asta e tot ce spune asta. Deci există cel mult d rădăcini din posibilitățile q. Și ultimul lucru pe care îl voi prezenta aici este versiunea multivariabilă a acesteia, care se numește, poate oarecum pe nedrept, dar se numește lema Schwartz-Zippel, deși, în diferite forme, fusese cunoscută înainte de munca lor. În unele cazuri, literatura de fapt merge în urmă cu mult timp în urmă. Dar oricum, aceasta se numește lema Schwartz-Zippel. Nu contează cu adevărat, cu excepția persoanelor cărora li se refuză creditul. Dar acesta nu este unul dintre noi. Deci, oricum, lema Schwartz-Zippel spune că, dacă acum aveți un polinom în mai multe variabile, care nu este polinomul 0, unde fiecare variabilă are un grad scăzut - deci dacă spun dacă are gradul cel mult d în fiecare xi. Deci, fiecare variabilă va avea cel mult un exponent al lui d care apare în acel polinom. Și acum, dacă alegem valori aleatorii pe care să le atribuim tuturor acelor n variabile din câmp, probabilitatea ca am ajuns cu o rădăcină, că am ajuns cu un 0, este ceva ce o poți lega. Deci este m ori d, deci numărul de variabile ori acest grad maxim, împărțit la dimensiunea câmpului. Și asta va apărea mai târziu pentru noi. Și aceasta este o altă dovadă destul de simplă, puțin mai sofisticată decât cea pe care o aveam mai sus. Și, de fapt, o folosește pe aceea ca lemă pentru a demonstra această teoremă. Așa că vom... nu vom demonstra nimic din toate acestea, dar vă trimit la carte dacă sunteți curios. Da, deci câteva întrebări bune aici. Ce se întâmplă dacă aceste valori sunt mai mari decât q, de exemplu? Atunci nu- ți spune nimic. Dacă d este mai mare decât q, m este mai mare decât q sau produsul este mai mare decât q, atunci nu înveți nimic din această lemă - din această teoremă. Deci, de obicei, în aplicații, veți alege un mare -- veți avea flexibilitate. Puteți alege q să fie ceva ce doriți. Deci, vom alege câmpul să fie suficient de mare, astfel încât m și d să fie relativ mici. De fapt, d va ajunge să fie 1, după cum vom vedea. Și m este numărul de variabile. Deci vom alege q, care va fi substanțial mai mare decât numărul de variabile. Și cum este definit gradul în polinoamele multivariabile? Dacă polinomul are xy pătrat plus 3x până la al 5-lea y pătrat z, trebuie doar să scoți fiecare variabilă separat. Și te uiți la gradul maxim al acelei variabile. Deci, x în acel caz avusese un aspect de gradul 5. Y avea un aspect de gradul 2. Deci, luați maximul peste toate variabilele gradului acelei variabile. Și aceasta va fi limita pentru gradul polinomului. Deci, de fapt, în cazul nostru, d va fi 1. Deci toate variabilele-- nu vor fi exponenți pentru nimic. Totul va fi exponentul 1. Este q legat de numărul pe care îl alegem pentru mod? Da, q este numărul pe care îl alegem pentru mod. Facem totul cu mod q. Deci toată aritmetica va funcționa în mod q și aceasta este dimensiunea câmpului pe care o vom alege. Deci cred că suntem aici la pauză. Încântați să mai răspundem la câteva întrebări, dar de ce nu începem cu asta. Și ne vedem în cinci minute. Dar între timp, bucuros să-mi pun întrebări. Deci, ce se întâmplă dacă folosim atribuiri booleene în exemplul XOR? Ar funcționa asta pentru a putea verifica acordul? Ar fi. Deci este greu să faci un argument pe baza unui singur exemplu. Cred că cel mai bine ar fi să te uiți la două programe de ramificare care diferă într-un singur loc. Așa că pot chiar să sugerez două. Puteți crea un program de ramificare care să iasă întotdeauna adevărat. Nici măcar nu își citește variabilele. Sau dacă le citește, merg mereu în același loc. Și ajunge întotdeauna la ieșirea q. Așa că vă imaginați un program de ramificare care scoate întotdeauna 1, indiferent care sunt atribuirile variabilelor. Și poți face cu ușurință așa ceva. Și apoi faci un alt program de ramificare care calculează funcția sau. Deci citește fiecare variabilă. Și va fi 1 dacă oricare dintre aceste variabile este setată la 1. Deci, singura dată când funcția sau este 0 este dacă totul este setat la 0. Dar acum, dacă încercați să verificați aleatoriu dacă funcția întotdeauna una este egal cu funcția sau -- desigur, fără a ști dinainte care sunt, pentru că asta înseamnă înșelăciune. Tocmai vi s-au dat aceste două funcții și doriți să știți... aceste două programe de ramificare. Și vrei să știi, calculează același lucru sau nu? Și prin această procedură de eșantionare aleatorie, veți obține întotdeauna aceste programe de ramificare să spună ambele 1, cu excepția cazului în care se întâmplă să alegeți alocarea aleatorie a tot ceea ce este setat la 0. Și este foarte puțin probabil să alegeți asta. . Dacă vă imaginați că aveți... programul dumneavoastră de ramificare are 100 de variabile în el. Sunt doar 2 la minus 100 de șanse să le setați pe toate la 0 aleatoriu. Și așa că este foarte puțin probabil să găsiți acel loc de diferență dacă există doar un singur loc. Dacă există o mulțime de locuri de diferență, atunci nu este atât de rău. Dar dacă numărul, fracția de diferențe, este mic, va trebui să faci o mulțime de mostre pentru a găsi că-- posibil exponențial multe mostre. Și atunci nu vei rula în timp polinomial. Așa că lasă-mă să văd dacă mai sunt și alte întrebări aici. De ce putem accepta - revenind la partea de etichetare booleană , de ce putem accepta că b1 este egal cu b2 dacă b1 și b2 sunt de acord asupra - doar pentru o singură atribuire de intrare? Nu, nu am spus asta. Bine, mă voi întoarce acolo. Misiunea booleană... este aceasta... Nu sunt sigur la care te referi. Acesta este cel la care te referi? Nu știu... Etichetare booleană, așa că trebuie să fie. De ce etichetăm non-boolean? Nu, văd ce spui. Despre asta spui aici. Vom alege doar o misiune aleatorie. Și dacă sunt de acord cu acel caz aleatoriu, atunci vom spune că acceptă, pentru că ai putea crede că ar trebui să luăm o grămadă de mostre. Asta e o intrebare buna. Dar, de fapt, vom aranja probabilitatea astfel încât, dacă cele două lucruri nu sunt echivalente, atunci va fi -- valorile vor fi diferite aproape peste tot sau într-un număr mare de locuri. Așa că doar alegerea uneia și ca ei să fie de acord va fi o dovadă suficient de puternică pe care încă o vei accepta. Și veți avea încă o probabilitate scăzută de a obține o eroare. Ar trebui să vezi analiza. Presupunem că rădăcinile polinoamelor sunt numere întregi? Nu, operăm peste un câmp aici. Nici măcar a vorbi despre numere întregi nu are total sens. Dar nu prea contează. Nu presupunem asta. Oh, ar fi trebuit să iau asta. Legatul încă funcționează. Legatura funcționează în continuare chiar dacă avem non-întregi. Nu sunt sigur dacă sunt de ajutor aici. De ce nu mergem mai departe? Dar nu presupunem că acestea sunt numere întregi, deoarece limita nu contează. Dacă spune că există cel mult cinci rădăcini, inclusiv reale, vor fi încă cinci rădăcini, inclusiv numerele întregi. Bine, deci hai să continuăm. Bine, bine. Deci acum toți s-au întors, sper? Să vorbim despre trecerea mai departe aici. În cazul în care mergem cu asta, dorim să analizăm algoritmul, care alege o intrare aleatorie non-booleană și evaluează cele două programe de ramificare. Și pentru a face asta, ne vom uita puțin mai atent la ceea ce se întâmplă atunci când aritmezăm programul de ramificare și îl rulăm pe aceste valori non-booleene. Și deci ceea ce voi face este să iau acest program de ramificare. Să presupunem că acesta este același program XOR, exclusiv sau de ramificare. Dar, în loc să-l etichetăm așa cum am făcut înainte, setând x1 la 2 și x2 la 3, voi lăsa variabilele x1 și x2 și voi face doar o execuție simbolică. Așa că voi eticheta aceste lucruri, lăsând doar x1 și x2 ca variabile. Deci, să vedem ce obținem dacă facem asta. Așa că nu uitați, am atribuit asta să fie 1. Acum această margine aici este... iată regula. Este a, care este 1, ori x1. Deci asta ar trebui să fie... fără să știm care este valoarea lui x1, lăsând-o ca o variabilă, vom pune x1 aici. Pe aici, ce se întâmplă acolo? Ei bine, este de 1 ori 1 minus x1-- doar 1 minus x1. Acum vom aduna lucrurile, așa cum am făcut înainte. Și acum, ce se întâmplă, de exemplu... Cred că va urma acest avantaj. Să ne uităm la această margine, cea care iese. Eticheta acum este x1 pe acest nod. Aceasta este marginea care iese, așa că înmulțiți cu valoarea lui x2. O lăsăm ca o variabilă, așa că o vom înmulți doar cu x2. Și așa vom obține doar x1 ori x2-- x1x2 pe această margine. Și acum ce se întâmplă pe marginea asta? Deci de x1 ori-- gândește-te cu mine-- ori de 1 minus x2. Și în mod similar aici, avem 1 minus x1 pe acest nod. Așa că cred că pe o margine care iese, este 1 minus x1, acum ori x2, pentru că aceasta este din nou această regulă. 1 minus x, de 1 ori x2. Și acesta va fi 1 minus x1 ori 1 minus x2. Acum vom aduna acest lucru pentru nodul 0. Deci avem această valoare, 1 minus x1, 1 minus x2, plus x1 x2. Și pe această notă aici, vom aduna aceste două valori. Deci 1 minus x1 ori x2 plus x1 ori 1 minus x2. Și aceasta este rezultatul, acum exprimat simbolic. Acum ai putea conecta lucrurile și vei obține aceeași valoare ca și înainte. Dar să lăsăm un polinom deocamdată pentru că asta ne va ajuta și să analizăm asta. Deci acum, observați că forma acestui polinom este ceva special. Ce se întâmplă este că va arăta ca o grămadă de produse de xi și 1 minus xi adunat. Deci este o sumă de produse de această formă. Deci, fiecare rând de aici este un produs al lui xi și 1 minus xi. Și apoi acele rânduri se adună toate împreună. Eu susțin că aceasta va fi forma acestui polinom. Vezi că asta are deja această formă. Și motivul pentru asta este că de fiecare dată când mergi la un nod, doar însumezi lucrurile. Deci asta va fi ca și cum ai adăuga mai multe rânduri. Și de fiecare dată când cobori până la o muchie, înmulți ceea ce ai până acum fie cu un xi, fie cu 1 minus xi. Deci doar acumulezi produse de xi și 1 minus xi și doar le adunați. Deci, așa va arăta acel polinom . Acum să ne uităm puțin mai atent la forma acesteia. Deci, pentru un singur lucru, am putea avea puteri mai mari aici, cum ar fi x2 cuburi? S-ar putea întâmpla asta? Și când spun că sunt produse de la xi și 1 minus xi, poate că vor fi niște xi care apar de mai multe ori în produs. Ei bine, asta nu se poate întâmpla. De ce? Este un program de ramificare citit o dată. Deci, de fiecare dată când înmulțiți cu un xi sau cu 1 minus xi, nu veți mai face asta niciodată, deoarece acest lucru ar implica că interogați acea variabilă de mai multe ori. Deci asta nu se poate întâmpla. Așa că elimin asta. Acesta tocmai a apărut. E pe o parte, aici. Dar da, elimin asta. Asta nu se întâmplă. Un alt lucru care face parte din-- care merită-- care va fi util de observat despre acest polinom-- și, apropo, poate că sunt confuz aici. Aceasta ar trebui să o reprezint ca o formă generică a polinomului. Acesta nu este ceva special... da, ar fi trebuit să spun asta la început. Acesta nu este un polinom anume care provine din orice. Încerc doar să descriu cum arată forma generală a polinomului, doar ca o ilustrare. Deci, acest polinom este 1 minus x1 ori x2 ori 1 minus x3 ori x4 și așa mai departe, și adunând o grămadă de rânduri ca acesta. Spun doar că așa va arăta polinomul pentru, poate, un program de ramificare. Deci, fiecare program de ramificare fie va avea un polinom care arată cam așa. Și ceea ce o să spun -- pentru comoditate, acum, vreau să spun că fiecare rând va avea fiecare variabilă să apară fie ca xi, fie ca 1 minus xi. Deci, pentru a obține asta, trebuie să fac o altă presupunere minoră despre programul de ramificare - că este o citire exactă o dată. În prezent, când spun „citește o dată”, poate evita citirea unor variabile pe unele ramuri, pentru că este ca o citire cel mult o dată. Dar acum vreau să spun că fiecare variabilă este citită exact o dată pe fiecare ramură. Și ceea ce va însemna este că fiecare rând va conține fiecare variabilă, fie ca xi, fie ca 1 minus xi. Putem elimina cu ușurință această presupunere suplimentară. Și o să-ți las asta ca un exercițiu. Nu este foarte greu de făcut. Deci cred că dacă mă urmărești, poți vedea... și te joci cu el un minut sau două, vei vedea că nu contează cu adevărat. Dar cred că doar pentru prima dată prin asta, să presupunem că fiecare rând are fiecare variabilă - atât de important de înțeles. Deci acesta este polinomul de ieșire al acestui program de ramificare. Deci, să ne uităm în continuare la acest polinom și să înțelegem rândurile. Să luăm un rând din acest polinom pentru a înțelege ce reprezintă. Deci, un rând aici-- este un produs al unui grup de lucruri, produs al unui grup de variabile, fie variabile, fie 1 minus variabilele. Să ne gândim la asta în setarea booleană, în primul rând. Deci, în setarea booleană, fiecare dintre aceste variabile va fi 0 și 1. Și 1 minus variabilele vor fi, de asemenea, 0 și 1. Deci va fi un produs de 0 și 1. Dacă există un 0 care apare în acel produs, acel produs va fi un 0, deoarece de 0 ori orice este un 0. Deci singurul mod în care produsul nu poate fi 0 este dacă toate aceste valori sunt 1 în cazul boolean. Deci asta înseamnă că x1-- ei bine, să ne uităm la al doilea rând. Deci x1 trebuia să fie un 1. x2 trebuia să fie un 1. x3 trebuia să fie un 1. x4 trebuia să fie un 0 pentru a continua produsul lui 1 și așa mai departe. Deci, de fapt, există doar o singură atribuire booleană la aceste variabile care fac acel rând 1. Orice altă atribuire la acele variabile face acel rând 0. Spunând că într-un alt mod, fiecare dintre aceste rânduri corespunde unuia dintre rândurile tabelului de adevăr pentru funcția booleană, unde tabelul de adevăr este adevărat, dă o valoare adevărată, dă o valoare 1 pentru funcția de pe acel rând. Așa că sper că sunteți cu toții familiarizați cu noțiunea de tabel de adevăr al unei funcții booleene. Scrieți doar funcția booleană, fiecare atribuire posibilă la funcția booleană și notați 1 sau 0 sau adevărat sau fals pentru care este valoarea acelei funcție. Este doar o reprezentare tabelară a funcției booleene. Se numește masă de adevăr. Acest lucru de aici vă oferă toate 1-- toate rândurile care sunt 1 în acea funcție booleană. Asta iti ofera acest polinom. Deci cred că suntem într-un punct de pauză pentru acest slide. E o tăcere de moarte pe chat. Așa că am sentimentul că ți-a fost greu. Este important să înțelegeți forma acestui polinom aici. Ea corespunde tabelului de adevăr al funcției booleene. Deci fiecare dintre aceste rânduri va fi doar -- din nou, gândindu-mă boolean acum, fiecare dintre aceste rânduri va fi doar 1 într- o atribuire care face ca funcția 1 -- una dintre atribuțiile care face funcția 1. Și cineva spune, și în mod similar pentru expresia pentru nodul 0. Da, nodul 0, pe care nu mă concentrez, dar, da, nodul 0 ar fi toate rândurile false ale tabelului de adevăr. Dar nodul 1, polinomul pentru nodul 1, sunt toate rândurile adevărate -- corespund tuturor rândurilor adevărate în funcția de ramificare -- funcția pe care o calculează programul de ramificare. Lasă-mă să-ți spun doar unde mergem. Este posibil să existe două rânduri care sunt la fel? Dacă te gândești la modul în care sunt produse rândurile, nu. Nu puteți avea două rânduri care vor fi la fel, pentru că, în primul rând, trebuie să vă gândiți la cum arată acest lucru în cazul boolean. Dacă aveți două rânduri identice, asta înseamnă că acest lucru va avea o ieșire care nu este booleană, deoarece veți ajunge cu un 2 care iese astfel prin adăugarea acestor rânduri împreună. Asta nu se poate întâmpla niciodată. Și dacă te uiți doar la felul în care este construit, nu vei avea niciodată de gând să-- pentru că de fiecare dată când ai o ramificare, o cale este un xi. Celălalt este 1 minus xi. Deci, de fiecare dată când ramificați acolo, de fiecare dată când există un nod, ele sunt diferite. Deci nu veți avea niciodată două rânduri care vor fi la fel. Dar permiteți-mi să vă spun importanța conectării acestui polinom cu tabelul de adevăr, deoarece asta ne spune că dacă cele două funcții ale celor două programe de ramificare cu care am început sunt de acord în valorile lor booleene, atunci cele două polinoame vor fi aceeași. Pentru că dacă cele două programe de ramificare au aceeași funcție booleană, deci sunt echivalente, atunci tabelele de adevăr vor fi aceleași. Și, prin urmare, aceste polinoame vor fi aceleași. Și, prin urmare, se vor comporta la fel pe toate valorile non-booleene , deoarece sunt același polinom. Așa că mă devansez, dar asta o să argumentăm. De aceea este important să înțelegem conexiunea cu tabelul de adevăr, deoarece se bazează pe-- înțelegerea ceva despre modul în care acest lucru se comportă în cazul boolean ne va oferi informații despre cum se comportă în cazul non-boolean. Dar să continuăm aici, atunci. Da, acesta este în esență ultimul diapozitiv, dar vom petrece ceva timp pe acesta. Deci iată algoritmul. Vom lua cele două programe de ramificare. Variabilele sunt x1 la xm. În primul rând, vom găsi un prim care este de cel puțin 3 ori m, numărul de variabile. m nu este un număr foarte mare. Este doar numărul de variabile. Deci, găsirea unui prim care este mai mare decât atât este simplă. Nu vorbim aici de numere prime uriașe. Vorbim de numere prime de dimensiuni foarte modeste. Chiar și încercarea și eroarea vor fi suficient de bune. Acum asta va fi dimensiunea câmpului. Va fi un câmp de dimensiune q. Și acum vom alege o atribuire non-booleană pentru variabile. Vom alege o atribuire non-booleană a variabilelor și vom evalua cele două programe de ramificare pe acea atribuire non-booleană utilizând aritmetizarea. Dacă ei sunt de acord, atunci vom accepta. Dacă ei nu sunt de acord, atunci vom respinge. Acum trebuie să argumentăm că acest lucru funcționează. Deci, în primul rând, vom aritmetica aceste două programe de ramificare și vom obține aceste două polinoame. Fiecare are forma care-- așa cum am descris-o, deci o grămadă de rânduri care corespund tabelelor de adevăr ale acelor două programe de ramificare respective. Prima afirmație - că dacă programele de ramificare ar fi echivalente, deci calculează aceeași funcție booleană, atunci cele două polinoame sunt de acord peste tot. Deci, cele două programe de ramificare vor obține aceeași valoare pentru fiecare caz non-boolean, precum și pentru cazurile booleene. Deci ei sunt de acord în Boolean. Asta înseamnă că sunt întotdeauna de acord, chiar și în ceea ce privește non-booleanul. Și am argumentat deja asta. Celălalt punct este că, dacă cele două programe de ramificare nu sunt echivalente, deci diferă la o valoare booleană, alegând acum o valoare aleatorie pentru evaluarea polinomului, veți avea doar 1/3 șansă ca acestea să de acord, deci o mică șansă. În regulă, deci acum să demonstrăm aceste două fapte. Pe primul l-am cam certat deja. Dacă cele două programe de ramificare sunt de acord asupra tuturor valorilor booleene, atunci funcțiile lor au aceeași tabelă de adevăr. Deci polinoamele sunt identice deoarece polinoamele corespund tabelului de adevăr. Prin urmare, ei sunt întotdeauna de acord, chiar și cu privire la valorile non-booleene. Deci, asta înseamnă că probabilitatea ca, dacă evaluezi cele două polinoame într-un loc aleatoriu, dacă vor fi egale, aceasta este o certitudine, deoarece, de fapt, în acest caz, p1 și p2 sunt același polinom. Acum doi, dacă programele de ramificare diferă undeva, chiar și într-un singur loc, bine știți că polinoamele nu ar putea fi aceleași. Ele trebuie să fie polinoame diferite, deoarece polinoamele includ comportamentul în cazul boolean, precum și tot restul câmpului. Deci polinoamele trebuie să fie aceleași. Și acum vom aplica lema Schwartz-Zippel. Avem două polinoame diferite. Ei pot fi de acord doar într-un număr relativ mic de locuri. Deci, asta spune că, din teorema Schwartz-Zippel, atunci probabilitatea ca p1 și p2 să fie de acord în această locație aleatorie este cel mult această valoare pe care o aveam de înainte, gradul înmulțit cu numărul de variabile împărțit la dimensiunea câmpului. Gradul este 1. Și câmpul este de cel puțin 3 ori numărul de variabile ca dimensiune. Deci asta înseamnă că obțineți această inegalitate aici. Prin urmare, probabilitatea este de 1/3 - cel mult 1/3. Și asta e destul de bun. Aceasta este probabilitatea ca să obțineți un răspuns greșit va fi de cel mult 1/3. Deci veți obține răspunsul corect cu cel puțin 2/3 probabilitate. Deci, chiar și doar efectuarea unui singur punct de probă va fi suficient pentru a-i oferi un algoritm PPP. Ceea ce am sunt câteva check-in-uri aici acum pentru tine. Hopa, cumva asta... mă va scoate de aici. Bine, deci este puțin greu, dar hai să vedem cum te descurci. Să presupunem că programul de ramificare este... ei bine, poate că am discutat deja puțin despre asta, dar este în regulă. Programele de ramificare nu au fost citite o dată. Polinoamele ar putea avea exponenți mai mari decât 1. Deci, unde ar eșua demonstrația? Ar eșua în punctul în care b1 și echivalentul cu b2 implică faptul că sunt de acord cu toate intrările booleene? Deci, acesta este primul pas aici. Sau a fost faptul că acordul asupra tuturor intrărilor booleene implică faptul că polinoamele sunt aceleași? Sau ar fi faptul că dacă cele două polinoame sunt egale implică faptul că ele sunt întotdeauna de acord? Deci, aceștia sunt cei trei pași din demonstrația primei părți. Deci, să vedem. Ce crezi acolo? Primesc câteva întrebări despre alegerea numărului prim. Numărul prim de aici este... acesta este un număr prim foarte mic. Ați putea chiar reprezenta acel număr prim în unară în intervalul de timp pe care îl avem, pentru că nu uitați, acesta este un număr prim a cărui magnitudine este cel mult numărul de variabile. Deci, puteți scrie acel număr prim în unară. Și găsirea primului și testarea primului, testarea dacă numărul este prim, este ceva ce poți face chiar și cu un algoritm de forță brută și ar fi suficient de bun. În acest caz, nu trebuie să faci nimic fantezist pentru a testa primalitatea . Deci de ce trebuie să fie prime? Aveți nevoie de ea pentru amorsare pentru a fi un câmp. Deci aceasta este doar partea de algebră. Dacă nu ați avut un număr prim, atunci unele dintre proprietățile câmpului nu funcționează. Și este posibil să nu mai înțelegeți faptul că polinomul are un număr mic de rădăcini. Deci, asta e tot ce pot spune despre asta. Este polinomul ca o funcție hash pentru programul de ramificare? Sunt egale dacă sunt aceleași, dar uneori valoarea este egală și dacă programele sunt diferite? Este o idee interesantă. Polinomul acționează ca o funcție hash? Cred că este ceva în ceea ce spui, dar cred că de fapt este în cealaltă direcție. Este legat de o funcție hash, dar de fapt acționează mai mult ca un cod de corectare a erorilor. Să păstrăm asta pentru mai târziu. Este un punct foarte bun. Este o întrebare foarte bună. Poate putem vorbi despre asta după, dacă îmi amintești. OK, să încheiem acest sondaj aici. Ar trebui să fie C-- dacă aceste două sunt de acord implică-- ei bine, vreau să spun, întrebarea este, ar trebui să schimbăm p1 și p2 întotdeauna de acord ca b1 și b2 să fie întotdeauna de acord? Ei bine, b1 și b2 se comportă exact așa cum se comportă p1 și p2, așa că nu sunt sigur că contează cu adevărat. Prea mult timp pe acest chat, la acest sondaj aici. Să încheiem acest sondaj... oh, partajarea rezultatelor. Da, deci răspunsul corect este B, că acordul asupra tuturor intrărilor booleene implică faptul că acestea sunt egale. Ceilalți doi urmează imediat. Sunt încă adevărate. Dar dacă nu este citit o dată, chiar dacă sunt de acord cu toate intrările booleene, nu vor fi neapărat de acord ca polinoame. În primul rând, dacă luați doar cele două polinoame x1 pătrat și x1, acestea sunt de acord cu toate intrările booleene, dar nu sunt la fel. Ei sunt de acord în lumea booleană, deoarece 0 pătrat este 0, iar 1 pătrat este 1. Dar nu sunt același polinom. Sa trecem peste. De fapt, am încă o înregistrare pe același slide aici. Și asta răspunde de fapt la o întrebare pe care am primit-o în chat. Dacă p1 și p2 ar fi... cât de mari sunt aceste polinoame? Acestea par că ar putea fi mari. Dacă sunt exponențial de mari, ar fi aceasta o problemă pentru complexitatea timpului? Deci alegeți A sau B aici. Nu avem timp aici. Deci de ce nu spun prea multe și te las să mergi cu asta. Am de gând să închid asta. Toate în? Ei bine, o, Doamne, până la un moment dat. Este ca Georgia aici... fă o renumărare. De fapt, B este corect cu un fir de păr. Nu au dimensiuni polinomiale. Tabelele de adevăr pot fi foarte mari. Așa cum am făcut cu programul de ramificare pentru exclusiv sau caz, de fapt nu scrieți polinoamele pentru a le evalua. Le poți evalua pe măsură ce mergi. Polinoamele sunt uriașe. Dar nu trebuie să scrieți polinoamele pentru a le evalua. Asta e doar o parte din dovadă. Algoritmul nu trebuie să se ocupe de polinoamele în sine, așa că poate e bine să te gândești la asta. Și cineva spune, am inventat această dovadă? Nu, nu am inventat această dovadă. Este o dovadă minunată, dar nu este a mea. Mi-ar fi plăcut să fi fost... să-mi iau meritul pentru asta. Deci, de ce nu încheiem asta? Există vreo modalitate de a simplifica polinoamele pe măsură ce mergem, astfel încât să nu ajungem să fie prea mari și să ne putem uita apoi la polinoame? Nu din cate stiu eu. Cred că polinoamele vor fi cu adevărat mari. Și așa că nu va exista nicio modalitate de a-l vedea așa cum... dacă ai putea, ar fi fantastic, pentru că asta ți-ar oferi un algoritm determinist. Cred că singurul mod prin care oamenii știu cum să facă acest lucru în ceea ce privește intrările aleatorii la un polinom, care este prea mare pentru a fi scris. Dacă ai putea să-l notezi și să analizezi doar polinoamele, ai avea un rezultat uriaș, uriaș acolo. Oh, mă bucur că oamenilor le place această dovadă. Asta e bine. Câte cantități reale există în formulă? Nu sunt sigur ce înseamnă asta. Ce formulă? Adică, polinomul este uriaș. Numărul de polinoame diferite... ei bine, cred că nu înțeleg întrebarea. Ce motivează ideea de aritmetizare? Ce ar face pe cineva să se gândească la asta? Nu sunt sigur, de fapt. Dar îl vom folosi chiar și într-un mod mai remarcabil în ultimele două prelegeri ale cursului, așa că rămâneți pe fază. Adică, acesta este un fel de inteligent, dar pare foarte specializat. Dar următoarea parte, în care trecem la următoarea aplicație, o vom folosi pentru a analiza satisfacabilitatea, care este o situație mult mai generală. Și asta, cred, este deosebit de remarcabil. Pentru polinoamele p1 și p2, este doar un număr polinom-- nu cred, pentru că-- ei bine, depinde de dimensiunea câmpului. Dimensiunea de... nu, va fi ceva de genul m la puterea a l-a, nu? Deci acestea sunt numărul de intrări posibile. Fiecare element de câmp are 3m de posibilități, aproximativ. Și există m elemente de câmp, deci sunt de la m la 3m de intrări posibile diferite pe care le alegeți la întâmplare. Deci, oricum, voi închide acest lucru și voi trece la programul de lucru Zoom. Simțiți-vă liber să mă alăturați acolo. Altfel, ne vedem cu toții joi. Ai grijă.