[SCRÂȘIT] [FOSȘIT] [CLIC] MICHAEL SIPSER: Salutări, tuturor. Bun venit la ultima noastră prelegere a trimestrului. Am supraviețuit unui semestru online în 18.404 și vom încheia ultimul nostru subiect astăzi, care este sistemele de dovezi interactive pe care le-am început data trecută. Și cu mare-- ei bine, marea teoremă a sistemelor de dovezi interactive este că IP este egal cu PSPACE. Și vom oferi ideea principală pentru asta într-o teoremă puțin mai slabă, după cum vom vedea. Așa că de ce nu sărim înăuntru? Deci am făcut dovezi interactive. Am dat un exemplu de a arăta că problema izomorfismului grafic , complementul acesteia este un IP, așa cum sper să vă amintiți. Am avut acea interacțiune cu autorizatorul și un verificator. O să trecem repede prin asta. Nu acel protocol, ci doar configurația. Și apoi vom încheia prin a arăta că această problemă de număr SAT este o IP și ar trebui să concluzionăm că conP este un subset de IP. Bine, așa că hai să mergem. Da. Deci, amintiți-vă, sistemele de dovezi interactive, există aceste două părți, doveditorul și verificatorul. Proverul are o capacitate de calcul nelimitată. Am un fel de model ca o armată de studenți, poate care poate... unde noi nu... ei pot lucra toată noaptea. Ei pot folosi resurse de calcul. Și probatorul, totuși, nu vom măsura puterea de calcul a doveditorului. Asta e nelimitat. Și astfel probatorul poate face lucruri precum găsirea de certificate. Poate testa dacă lucrurile sunt satisfăcătoare. Poate factoriza numerele. Nu ne pasă. Poate face orice ne dorim și nu există nicio taxă pentru cerințele de calcul ale doveditorului. BINE. Deci configurația pe care am avut-o a fost probatorul și verificatorul. Ambele văd intrarea. Schimbul de număr polinom de mesaje. Și apoi verificatorul acceptă sau respinge. Și am avut această noțiune a probabilității pe care verificatorul ajunge să o accepte atunci când este asociat cu un anumit doveditor. Și ceea ce ne dorim este ca pentru șirurile dintr-o limbă, probabilitatea să fie mare pentru un probator. Și pentru șirurile care nu sunt în limbaj, probabilitatea ar trebui să fie scăzută, indiferent de ceea ce face probatorul. Deci nu poate face nimic demonstratorul. Și felul în care sugerează asta la orice proba. Dar oricare ar fi strategia probatorului nu poate face verificatorul să accepte cu mare probabilitate. Pur și simplu nu are suficiente informații sau nu-- pur și simplu nu poate face verificatorul să accepte cu mare probabilitate. S- ar putea să vă gândiți la probator ca încercând să-l facă pe verificator să accepte. Deci tilda P este un doveditor strâmb. Nu cred că a mers prea bine cu toată lumea. Deci il am aici. Un alt mod de a- l privi, poate că seamănă puțin mai mult cu NP aici, unde IP este o colecție de limbi în care există un verificator, la fel ca noi. Vă puteți gândi la NP ca având un verificator care poate verifica certificatele. Aici dovezitorul va fi ca certificatul, astfel încât, pentru șirurile din limbă, există un demonstrator care poate interacționa cu verificatorul și îl poate face să accepte o probabilitate mare. Și nu sunteți în limbaj, nu există nici un doveditor, care poate interacționa cu verificatorul și îl poate face pe verificator să accepte cu o probabilitate chiar mai mare decât mică. Ceea ce este important este acest decalaj, la fel ca în cazul BPP, între acceptare sau respingere. Și acest decalaj există pentru că vrem să putem folosi lema de amplificare. Și dacă nu ar exista niciun decalaj, atunci nu ai putea să amplifici și să faci probabilitatea de acceptare extrem de mare atunci când vrei să fie în limbă, când ești în limbă și extrem de scăzută când nu ești. în limbaj. BINE. Așa că sper că vă împrospătează memoria cu privire la modul în care funcționează. Ne vom plimba prin... ei bine, prin ceea ce am făcut data trecută. Dar să pregătim scena pentru asta. Deci, teorema surprinzătoare, așa cum am menționat, este că IP este egal cu PSPACE. O direcție a acesteia este o simulare destul de standard. Cu PSPACE, vă puteți îndrepta practic prin arborele de posibilități pentru un protocol de demonstrare interactiv. Și puteți calcula probabilitatea pe care verificatorul ar ajunge să accepte dacă ați avea cel mai bun demonstrator posibil care ar încerca să-l facă pe verificator să accepte. Și poți doar să faci acel calcul. Este în carte. Nu vei fi responsabil să știi asta, de fapt. Nu am tratat-o în prelegere. Dar nu este foarte greu. Puțin tehnic, presupun. Cealaltă direcție este cea interesantă și aceasta este direcția spre care ne vom îndrepta astăzi. Nu vom ajunge acolo, dar modul în care funcționează este pentru a arăta că totul în PSPACE, care este oarecum uimitor, este conținut cu o IP. Deci, totul în PSPACE se poate face cu un sistem de dovezi interactiv . Și modul în care se face este prin utilizarea unei probleme complete PSPACE, TQBF, și arătând că problema în sine este un IP. Dar nu vom demonstra asta. Acesta ar fi un fel de următorul lucru pe care l-am demonstra dacă am avea puțin mai mult timp. Dar ne vom mulțumi doar cu afirmația oarecum mai slabă, dar foarte asemănătoare, că coNP este conținut în IP aici. Din nou, încă foarte surprinzător, pentru că trebuie să poți arăta, de exemplu, că o formulă nu este satisfăcătoare cu un doveditor. Cum poate un demonstrator să convingă un verificator că o formulă nu este satisfăcătoare? Arătând că este satisfăcător, doar dați certificatul, care este sarcina satisfăcătoare. Dar cum arăți că ceva nu este satisfăcător? Este neașteptat. Și dovada acestui lucru este destul de asemănătoare, puțin este un fel de punct tehnic în care nu trebuie să intrăm. Deci este puțin mai ușor, dar foarte mult în același spirit. Deci, amintiți-vă că această problemă a setului de numere este că vi se oferă o formulă și un număr, iar acel număr ar trebui să fie exact numărul de atribuiri satisfăcătoare ale formulei. Deci, în special, o formulă este nesatisfăcătoare, atunci ar fi asociată cu numărul 0. Și de aceea problema setului de numere este dificilă, deoarece puteți reduce cu ușurință nesatisfăcătorul la setul de numere. O nesatisfăcibilitate este conNP completă. OK, așa că nu uitați că am introdus această notație data trecută. Acest lucru va fi critic pentru înțelegerea acestei dovezi. Așa că hai să trecem prin asta încă o dată. Deci, dacă aveți o formulă, ceea ce aș dori să fac este să presetați unele dintre variabilele acelei formule. Deci aceasta va fi o formulă pentru m variabile x1 la xm. Și aș dori să preset primele variabile i la zerouri sau la unități după cum doresc. Deci, voi indica că prin phi cu 0 înseamnă că stabilesc x1 la 0 și restul variabilelor rămân variabile. Și mai general, phi din valorile i de la a1 la ai, cu care pentru început vor fi doar zerouri și unu, doar valori booleene. Aceasta va fi formula cu primele x1 de setat la a1 punct, punct, punct xi setat la ai pentru acele constante i, care au fost zerouri și unu. Voi apela acele presetări, pentru că presetăm unele dintre variabilele din formulă. Și restul variabilelor le vom lăsa ca variabile. Așadar, obținem o nouă formulă pentru mai puține variabile făcând acest proces de pre-setare. Și vom ajunge să facem același lucru în ceea ce privește numărarea numărului de sarcini satisfăcătoare. Deci, amintiți-vă că numărul de notație phi este numărul de sarcini satisfăcătoare. Numărul phi cu o presetare de 0 este numărul de atribuiri satisfăcătoare atunci când ați setat x1 la 0. Și niciun phi de a1 la ai este locul în care setați primele variabile i la acele valori i. Și apoi te vei uita la numărul de sarcini satisfăcătoare având în vedere acele presetări. Deci au fost două fapte. O să le numesc identități, pentru că ne vom baza pe acestea și le vom extinde efectiv la cazul non-boolean, așa cum vom vedea în curând. Deci, aceste două identități spun că, în primul rând, dacă presetez, cred că înțelegerea primei este clară doar gândindu-ne la asta în cazul în care i este egal cu 0. Deci, acesta este cazul în care numărul de sarcini satisfăcătoare este în totalitate numărul de sarcini satisfăcătoare când am setat x1 la 0 plus numărul de sarcini satisfăcătoare când am setat x1 la 1. Și acest lucru generalizează doar atunci când mă uit că am presetat deja primele i variabile. Deci, dacă am presetat primele variabile i la aceste valori i, numărul de atribuiri satisfăcătoare pe care le primesc acolo este numărul de sarcini satisfăcătoare pe care le primesc cu acele presetări plus următoarea variabilă fiind setată fie la 0, fie la 1. Și apoi le adaugi. sus. Aceeași idee. Și, în sfârșit, dacă setez toate variabilele la valori, deci nu mai am variabile și mă uit la numărul de sarcini satisfăcătoare în concordanță cu acele variabile complet setate, deci nu mai sunt variabile , totul este setat, totul este prestabilit, asta este doar dacă acele valori au satisfăcut sau nu formula deja sau nu. Deci, acesta va fi egal cu 0 sau 1, numărul de atribuiri satisfăcătoare consistente cu acele m presetări în care m este un număr de variabile este doar dacă acele m valori satisfac formula, caz în care, primesc 1 sau nu nu satisfac formula, caz în care, primesc un 0. Critic pentru a le înțelege în cazul boolean, pentru că vom generaliza acest lucru la cazul non boolean și va fi doar mai abstract. Formulele vor arăta la fel. Va trebui oarecum... vom pierde intuiția că acele lucruri corespund unor sarcini satisfăcătoare. Sau numărând numărul de sarcini satisfăcătoare. În regulă. Deci haideți să facem un check-in rapid aici. Așa că vom face doar un exemplu pentru a spera să găsim asta, această idee. Deci, iată o formulă specială phi. Și acum amintiți-vă, numărul phi este numărul de sarcini satisfăcătoare. Deci phi, numărul de sarcini satisfăcătoare în care am setat x1 la 0 și așa mai departe. Și aici chiar vă ofer două opțiuni în fiecare rând pentru valoare. Acum trebuie să verificați tot ce este adevărat. Deci va fi cu adevărat cel mult unul pe rând, probabil. În regulă. Să vedem dacă ești cu mine aici. Deci, numărul de sarcini satisfăcătoare pentru total, ei bine, există două moduri de a îndeplini această formulă. Acesta este într-adevăr ca exclusiv sau. Deci fie x1 este 1, x2 este 0, fie x1 este 0 și x2 este 1. Deci una dintre variabile trebuie să fie adevărată. Celălalt trebuie să fie fals. Și atunci vei ajunge să satisfaci ambele clauze, după cum poți vedea cu ușurință. Deci b este corect în prima linie. Acum, dacă o să mă angajez deja să spun că prima variabilă este setată la 0, acum câte sarcini satisfăcătoare pot fi? Ei bine, a doua variabilă trebuie doar setată la 1 pentru a fi satisfăcută. Așadar, acum va fi o singură atribuire satisfăcătoare în concordanță cu setarea primei variabile la 0. Acum, dacă setez ambele variabile la 0, acum câte sarcini satisfăcătoare pot fi în concordanță cu acea atribuire? Poate fi 0, deoarece pentru a satisface această formulă, una dintre variabile trebuie să fie 0. Cealaltă trebuie să fie 1. Dacă le prezint pe amândouă la 0, nu vor exista sarcini satisfăcătoare, deoarece 0, 0 nu satisfac formula. OK, scuze că am dat greșelii acelui check-in în ultima zi. Oh bine. În regulă. Să trecem mai întâi peste protocolul pe care l-am încercat pentru numărul SAT săptămâna trecută, joi. Deci ni se oferă intrarea, formula și un k. Și amintiți-vă ce vrem să se întâmple. Dorim ca verificatorul să ajungă să accepte cu probabilitate mare când k este valoarea corectă și cu probabilitate scăzută când k nu este valoarea corectă. Acum, acesta va fi, după cum vă amintiți de data trecută, acesta va ajunge să fie un protocol defectuos, pentru că este exponențial. Avem voie doar să avem un protocol de dimensiune polinomială. Dar doar privind înainte în acest protocol, verificatorul va ajunge să accepte cu probabilitatea 1 pentru un doveditor cinstit și cu probabilitatea 0 indiferent de ceea ce încearcă să facă probatorul. Deci, pentru orice doveditor, verificatorul nu poate fi făcut să accepte. Deci, acesta este un fel de caz extrem în care nu vor ajunge să existe probabilități. Dar este un protocol exponențial. Deci, în acest sens, nu face ceea ce avem nevoie. Deci, haideți să trecem prin asta, pentru că ne pregătește cu adevărat pentru protocolul polinom cu valori non-booleene. În regulă. Așa că mai întâi doveditorul trimite... să ne uităm la asta și să nu ne grăbim. Proverul trimite numărul de sarcini satisfăcătoare conform doveditorului. Verificatorul verifică că este egal cu k. Și cred că cel mai bine este să înțelegeți acest lucru mai întâi în cazul în care intrarea este în limbă. Deci k este corect și avem un doveditor sincer. Și apoi vom înțelege ce se întâmplă dacă k nu este în limbă. Și vom vedea că indiferent ce încearcă să facă probatorul, verificatorul va sfârși prin a nu accepta. Și din nou, aceasta este doar o configurare pentru protocolul real. Deci acesta este un fel de protocol prost. Te vei gândi, ce naiba , de ce fac asta? Se pare că fac ceva foarte simplu și complicat, dar este doar cadrul pe care îl pun împreună. Pentru că, ei bine, vei vedea. În regulă. Deci, dovada va trimite cererea pentru numărul de sarcini satisfăcătoare, care, în cazul sincer, va fi valoarea corectă. Verificatorul verifică dacă se potrivește cu intrarea. Acum verificatorul spune, ei bine, vreau să fiu convins că afirmația ta este corectă. Deci, probatorul va justifica acea afirmație spunând, ei bine, numărul total de sarcini satisfăcătoare este oricare ar fi el, 100, deoarece numărul când am x1 setat la 0 este 60. Și numărul când am x1 setat la 1 este 40. Și asta însumează 100, ceea ce ar fi trebuit să se întâmple. Deci verificatorul verifică dacă suma este corectă și apoi spune, ei bine, acum de unde știu că aceste două valori sunt corecte? Deci, probatorul îl despachetează un nivel mai departe. Deci, descompune cele două justificând că phi 0 a fost corect, că valoarea 60 a fost corectă, spunând, ei bine, acum, dacă setez următoarea variabilă, x2 la 0 și 1, va trebui să adunăm phi 0. Deci poate pentru a obține 60, am avut 50 și 10. Și pentru a obține 40 pentru numărul phi de unu, am avut 20 și 20. Deci trebuie să le adun. Deci fiecare nivel justifică nivelul precedent. O să se întâmple asta din nou. Acum, dovatorul spune, ei bine, vreau să spun, trebuie să fiu convins. Nu am încredere în tine. Trebuie să fiu convins că aceste valori sunt corecte. Deci, nivel cu nivel, probatorul va stabili din ce în ce mai multe variabile în toate modurile posibile, până când va ajunge până la capăt, unde va stabili variabilele în toate modurile posibile. Deci exponențial multe setări aici. Iar verificatorul verifică acum dacă runda anterioară a fost corectă. Așa că aici am stabilit doar primul m minus 1, ultima variabilă nu fusese încă setată. Deci verifică toate acele setări posibile de la 2 la n minus 1 în ceea ce privește noile setări pe care le-am obținut acolo unde am setat acele m minus 1 setări, dar am extins-o cu 0 și cu 1. Din nou, aceasta este aceeași identitate pe care o avem folosit de înainte. Și acum, când doveditorul a trimis toate aceste valori posibile, verificatorul trebuie să se asigure că acestea sunt încă corecte. Dar lucrul este că, în acest moment, acestea sunt toate zerouri și unu, deoarece toate spun dacă acea atribuire satisface formula sau nu satisface formula. Deci verificatorul le poate verifica direct. Verifică fiecare dintre acestea, fie doar prin conectarea la formulă și văzând dacă satisface formula sau nu. Deci, fiecare dintre acestea este o valoare 0, 1, care ar trebui să corespundă dacă formula a fost satisfăcută sau nu. Toate acestea sunt corecte și totul pe parcurs a fost corect. Verificatorul va accepta. În caz contrar, dacă la un moment dat una dintre aceste verificări a eșuat, verificatorul a respins deja sau în acest moment doar respinge. Deci acesta este protocolul, protocolul exponențial. Și nu sunt sigur dacă acest lucru vă este de ajutor sau nu, dar îmi place să mă gândesc la asta ca un arbore al posibilităților. Deci aceste valori galbene sunt cele pe care le trimite probatorul. Deci, probatorul trimite mai întâi numărul de sarcini satisfăcătoare toate împreună. Verificatorul în alb verifică... fac aceste verificări. Deci se verifică dacă este egal cu k. Și apoi probatorul trimite următorul nivel. Verificatorul verifică dacă adaosul funcționează. Apoi probatorul îl despachetează în continuare, atribuie valori primelor două variabile, iar verificatorul verifică dacă doar atribuirile, doar o singură variabilă sunt în concordanță cu asta și așa mai departe. Și pentru a atribui toate variabilele m și apoi verifică direct cu formula. Acum, ce se întâmplă... și aici este cazul. Va fi important de înțeles atât aici, cât și în cazul non-boolean. Ce se întâmplă dacă am avea o valoare incorectă pentru intrare? Și ceea ce vreau să vă arăt este că probatorul va... Vreau să vă arăt că verificatorul va sfârși prin a respinge în acest caz cu certitudine. Mai târziu va fi respins cu mare probabilitate. Dar pentru acest protocol, va accepta cu certitudine. De ce, mă rog? Pentru că în primul rând, dacă dovatorul, dacă k a greșit, deci indic valorile greșite cu roșu. Dacă k a greșit, deci nu a fost egal cu numărul de sarcini satisfăcătoare, dacă doveditorul trimite valoarea corectă, verificatorul va spune doar că nu se potrivește. Resping imediat. Deci, ce poate face probatorul pentru a împiedica verificatorul să accepte? Vei vedea că nu poți face nimic. Dar mai târziu, există șansa ca dovatorul să aibă noroc. Dar aici nu poți face nimic. Să încercăm să mă simțim cu umor și să vedem... să încerce probatorul să reușească să mențină verificatorul cât mai mult posibil. Deci, pentru a împiedica verificatorul să respingă la început, probatorul ar trebui să mintă cu privire la numărul de sarcini satisfăcătoare. Dar apoi dovatorul va spune, bine, bine, pretindeți că sunt doar 99 de sarcini satisfăcătoare. Prover nu știe care este răspunsul corect. Dar știm că a fost 100, să spunem. Dar să presupunem că k a fost egal cu 99. Dovatorul a susținut că acum este 99. Și astfel verificatorul spune, OK, ei bine, este 99. Convinge-mă de asta. Deci, acum probatorul va trebui să spună numărul de sarcini satisfăcătoare pentru 0 și numărul de sarcini satisfăcătoare pentru 1, trebuie să se adună. Cel puțin una dintre acestea trebuie să fie greșită, pentru că nu puteți avea cele două valori corecte să adună valoarea falsă. Deci o minciună aici trebuie să dea o minciună în cel puțin unul dintre acele două locuri. Și apoi o minciună acolo va trebui să dea o minciună într-unul din acele două locuri, așa cum fiecare minciună forțează mai multe minciuni. După cum știi, încerci să minți. Povestea devine din ce în ce mai complicată pentru a încerca să justifice toate acestea. Și astfel, în cele din urmă, vei obține o inegalitate. Și verificatorul va sfârși prin a respinge. Undeva de-a lungul liniei, va trebui să existe o inegalitate, dacă nu pe parcurs, atunci la sfârșit, când verificatorul efectuează singur verificarea. Pentru că una dintre ele, ai putea urmări asta în jos, vor fi minciuni și minciuni și minciuni și apoi va fi în partea de jos una dintre aceste valori va fi greșită. Și când verificatorul le verifică pe toate, va afla că există o inegalitate acolo. Și astfel, una dintre acele verificări va eșua. Deci primesc o întrebare aici. De ce este mai bine decât să verificăm toate sarcinile posibile fără un doveditor? Nu este. Singurul motiv pentru care fac acest lucru este să ne pregătim pentru protocolul aritmetizat în care apar valori non-booleene. Deci întrebări despre asta? Cred că este important să înțelegem asta. Nu pune întrebarea de ce. De ce va fi că ne pregătim pentru ceva mai târziu, ceea ce nu știți încă. Dar vreau să-l înțelegi așa cum este, chiar dacă pare inutil de complicat. OK, deci hai să continuăm. Deci, cum vom remedia acel protocol, astfel încât să nu fie exponențial? Deci, din nou, iată o imagine a acestui protocol exponențial. Și avem acea explozie exponențială, deoarece în fiecare etapă, fiecare valoare va fi justificată în termeni de două valori în etapa următoare. Deci, după un timp, vor fi exponențial multe valori . Deci, în schimb, vom încerca să justificăm fiecare valoare aici în termeni de o singură valoare în etapa următoare. Dar nu va fi suficient de bun doar pentru a alege fie 0, fie 1 la întâmplare. Pentru că s-ar putea să fie fiecare... s- ar putea să fie doar un singur curs de minciuni aici. Și singurul mod în care ai fi să înțelegi asta ar fi să ghicești corect în fiecare etapă care a fost minciuna. Și apoi l-ai prinde la sfârșit. Dacă doar vei alege la întâmplare zerouri și unu, nu vei avea o probabilitate mare de a prinde dovezitorul atunci când minte. Și așa că nu va fi suficient de bun. Intrarea ar putea fi o valoare greșită și s-ar putea să aveți un doveditor care are doar o cale de minciuni, iar apoi probabilitatea dvs., ați avea totuși o probabilitate mare de a accepta în acest caz, chiar dacă intrarea a fost greșită. Nu este ceea ce vrei tu. Când introducerea este greșită, trebuie să ai doar o șansă mică, o șansă foarte mică de a accepta. Deci, modul în care vom realiza acest lucru este să avem aceste -- în loc să alegem un 0 sau un 1 pentru aceste valori aleatorii, vom avea alocații non-booleene pentru variabile. Și trebuie să înțelegem asta. Și am văzut deja un exemplu în acest sens. Va fi cam la fel. În regulă. Suntem toți împreună aici? Deci, acesta este un loc în care am putea încerca, dacă aveți o întrebare, putem încerca să răspundem la aceasta. Suntem buni? Să continuăm să ne mișcăm. OK, deci cum vom aritmetica formulele booleene? Este, din nou, aceeași idee pe care am avut-o înainte. Simulând și și sau cu plus și timp. Deci am avut asta de înainte, aceeași imagine exactă. De fapt, este și mai simplu, pentru că acum vom folosi simularea adevărată a sau în locul unui fel de simulare de caz special a sau, pe care am avut-o în cazul programului de ramificare. Deci, aceștia fac cu fidelitate ce și și sau fac atunci când conectați 0 pentru fals și 1 pentru adevărat. Deci asta înseamnă că putem lua o formulă întreagă și o putem aritmetica. Formula construită din și și sau și negații. Și vei obține un polinom care iese. Și acel polinom, ceea ce va fi important pentru noi nu va fi de un grad extrem de ridicat. Gradul real va fi cel mult lungimea formulei în ceea ce privește numărul de simboluri pe care le are. Puteți verifica asta pe cont propriu. Dar deocamdată poți să ai încredere în mine. Gradul polinomului, pentru că nu crește decât în ​​timpul înmulțirilor, dar gradul nu devine prea mare. Și o să facem... și nu vreau să fie o problemă confuză aici. Vom face... dar trebuie să avem dreptate. Nu vreau să trișez aici. Deci toată aritmetica va fi făcută într-un câmp. Așa că trebuie să modificăm plus și ori un număr, care se dovedește a fi un număr prim din motive în care nu voi intra. Dar nu prea contează. Este doar aritmetică modulară. Și acesta este un lucru care ne permite să alegem valori aleatorii într-un mod natural, deoarece există doar un număr limitat de valori în domeniu. Și așa vei alege doar unul la întâmplare. Dar aici vrem să fim capabili să reprezentăm -- va fi mai important pentru noi să avem un câmp mai mare , pentru că vrem să putem reprezenta numărul de sarcini satisfăcătoare care poate fi un număr între 0 și 2 la m . Deci trebuie să avem un câmp care să aibă cel puțin 2 până la m elemente în el, astfel încât să putem nota într-un mod sensibil acele numere. Să nu fim prinși de asta. Dar putem încerca să răspundem la aceste întrebări offline dacă doriți. Dar gândește-te la asta pentru această primă trecere. Facem modul aritmetic sum prime. Deci acum avem aceeași noțiune de presetări ca și înainte. Deci, dacă avem o formulă și presetăm unele dintre valori, dar acum acele valori pot fi valori non-booleene. Este posibil să introducem valori pentru formulă. Nu doar zerouri și unu, dar s-ar putea să introducem șapte sau 23 sau orice altceva. Și formula va avea, pentru a avea o valoare, o semnificație, vom trata acea formulă ca polinom din aritmetizare. Și doar introduceți acele valori în polinom și vedeți ce face polinomul pentru dvs. Deci, aici vom preseta unele dintre valorile formulei așa cum am făcut înainte. Și acum va fi același lucru. Dar acum, în polinom, vom pre-atribui unele dintre valorile variabilelor acestor a din câmp. Iar variabilele rămase vor rămâne nesetate. Acum trebuie să dăm o interpretare. Deci noul polinom aici. Deci primesc o întrebare. Ei bine, poate mai bine iau asta. Permiteți-mi să rețin deocamdată care este gradul. Voi răspunde la întrebări într-o secundă. Așa că acum amintiți-vă de înainte, numărul phi a fost numărul de sarcini satisfăcătoare când am presetat primele valori i. Nu mai are sens să vorbim despre sarcini satisfăcătoare, deoarece aceste valori pot să nu mai fie booleene. Așa că va trebui să scriu acest lucru formal, deoarece voi introduce acele valori, acele valori i, pentru primele variabile i. Iar restul sunt variabile pe care nu le-am setat. Le voi aloca zerouri și unu în toate modurile posibile. Numai la zerouri și unu. Pentru că ceea ce vreau să am, ați putea crede, ei bine, de ce nu le atribuim altor valori din domeniu? Ei bine, pentru că ceea ce țintesc este că, dacă ar fi să introduc zerouri și unu în acest punct în polinom, ar trebui să obțin exact aceleași valori ca și înainte, pentru că simulez și și sau sau. . Deci doar extind definiția, evaluarea într-un domeniu nou. Dar nu ar trebui să schimb valorile din vechiul tărâm boolean. Așa că voi aduna variabilele nealocate, nesetate în toate modurile booleene posibile. Și primele valori i ar putea fi valori non-booleene. Așa că trebuie să accepți asta ca pe o noțiune abstractă. Nu mai are o interpretare ca sarcini satisfăcătoare. Deci, așa cum am spus, ceea ce este important este că, dacă se întâmplă să introduc valori booleene acum, atunci phi și numărul phi dau aceleași valori ca și înainte. Deoarece polinomul acționează identic cu formula asupra valorilor booleene. BINE. Deci asta repet ceea ce am spus. Și mai este și un alt punct pe care trebuie să îl verificați, și anume că identitățile pe care le-am avut mai devreme au conectat ceea ce se întâmplă când am stabilit primele valori i și am stabilit primele valori i plus 1, acestea rămân valabile. Așadar, dacă setez primele valori i acum la o eventuală atribuire non-booleană, asta primesc atunci când extind acele valori la încă o variabilă alocată. Dar trebuie doar să atribui acea variabilă la 0 și la 1 și să le adun din cauza modului în care am definit lucrurile aici. Așa că am atribuit acele variabile la zerouri - variabila nesetată la zerouri și la unități atunci când definesc funcția număr phi . Și apoi, în sfârșit, când voi atribui totul acum unor valori posibil non-booleene , asta va fi... nu mai este nimic de adăugat. Așa că voi obține exact la fel ca și înainte când am-- așa că alocarea numărului phi de intrare total presetată, este la fel ca phi cu o intrare total presetată. Pentru că, în acest caz, nu mai există variabile pe care să le adunăm. Deci, există doar unul. Primesc doar un single. O rezumam ca fiind doar un element din el. Așa că am o întrebare aici pentru mai devreme. Ce se întâmplă cu gradele polinoamelor? Ei bine, gradul de număr phi va fi cel mult gradul de phi, pentru că doar adun lucrurile. Și adăugarea nu schimbă gradele. Pe măsură ce am presetat valori, numărul de variabile scade, dar gradul poate să nu scadă neapărat. Deci întrebarea pe care am primit-o dacă noile polinoame au grade mai mici? Nu neaparat. Au mai puține variabile, dar nu un grad mai mic. Deci să facem această verificare. Să vedem dacă asta... acum din nou, asta e cred că am greșit asta. Ei bine, există unul dintre astea care... O voi da în parte. Oricum, doar unul dintre ei era adevărat. Deci îl puteți verifica pe cel care este adevărat conform modului în care am definit-o. Așadar, aceasta este o întrebare mică aici, așa cum voi explica. Dar există doar unul dintre ei care face cu fidelitate aritmetizarea așa cum am descris-o pe această pagină. Și acesta este cel pe care ar trebui să-l verifici. Așa că nu uitați, aici aceasta este formula. Aceasta este rețeta pentru cum fac aritmetizarea. Tot acest proces aici. Deci, una dintre aceste linii, una dintre acestea, a, b sau c, corespunde să facă asta. Am de gând să închid asta. Deci suntem cu toții înăuntru? Da. Deci a este răspunsul corect. A face aritmetizarea conform rețetei pe care tocmai am descris-o. Pentru că dacă te uiți la x1 sau x2, îl putem verifica doar în prima parte a polinomului. x1 sau x2. Ei bine, este x1 plus x2 minus produsul x1 x2. Deci o poți vedea chiar acolo. Ceilalți nu au asta. Și la fel pentru x1 bar și x2 bar. Devine 1 minus x1, 1 minus x2 și apoi produsul acestora. Deci a este destul de simplă ca aritmetizarea lui phi. Acum, de fapt, oricare dintre acestea ar funcționa. Nu vreau să te încurc aici. Dar oricare dintre aceștia ar fi funcționat, pentru că toți sunt de acord cu atribuirea booleană. Și asta este tot ce contează cu adevărat. Deci, dacă aveți vreun... tot ce îmi pasă este că ei sunt de acord. Formula este de acord cu polinomul și cazurile booleene, iar acestea se întâmplă să fie de acord cu zerouri și unu. Nu contează totuși. Le-am pus acolo doar în cazul în care ai încercat-o prin simpla înlocuire de zerouri și unități. S- ar putea să fi ales lucrul greșit. BINE. Așa că haideți să facem o pauză aici și apoi vom vedea cum să remediați protocolul după pauză. În regulă. Așa că, de asemenea, bucuros să accept orice întrebări. Nu am făcut prea multe. Practic, totul a fost o revizuire a ceea ce am făcut ultima dată. Dar lasă-mă să pornesc cronometrul. Dar nu ezitați să puneți întrebări. Îți spun unde mergem. Toată această dovadă se reduce într-adevăr la înțelegerea unei linii, care va fi în a doua jumătate. Așa că sunt într-adevăr un fel de-- toate acestea sunt o configurație mare aici pentru a vă pregăti să puteți înțelege asta. Îți spun când vine. Deci nu va trebui să vă faceți griji că o veți rata. Dar această linie nu este ușor de înțeles. Așa că cred că este important să se configureze întregul cadru și tot contextul pentru tine, astfel încât să poți înțelege acea linie și sper să vezi acea linie și să o înțelegi. OK, deci fapt important. Deci să ne întoarcem. Ai vrut să vezi faptul important. BINE. Deci asta spuneam înainte. Dacă conectez valori booleene la aritmetizare, obțin exact același lucru pe care l-aș avea dacă aș aplica operațiile booleene înainte de a face aritmetizarea. Deci plusul și timpii din aritmetizare oferă o simulare fidelă a și și sau conform acestor mici formule. Asta e tot ce spun cu asta. Și așadar, dacă introduc valori booleene pentru a, obțin exact același lucru pe care l-aș fi obținut înainte de a face aritmetizarea. Pentru că aritmetizarea este o simulare fidelă. Nu știu cum altfel să o spun. Să vedem. Ce înseamnă regula sau acum-- de ce regula sau conține acum termenul minus ab în timp ce instanța anterioară de aritmetizare nu a făcut-o? Amintiți-vă, în cazul programelor de ramificare, nu aveam nevoie de termenul minus ab aici. Și asta pentru că am putea argumenta că a fost o disjuncție sau în cazul programelor de ramificare. Nu vreau să devin confuz încercând să explic de ce a fost asta. Dar în acel caz anterior, nu am luat niciodată unul sau două. A fost un de 0, 0 sau posibil 0, 1 sau posibil 1, 0. Prin urmare, nu a trebuit niciodată să ne ocupăm de un caz când am avut un sau de 1, 1. Și aici putem avea asta. Deci trebuie să scădem acel termen ab, pentru că altfel am avea-- dacă am avea doar un plus b, atunci cazul 1, 1, am ajunge cu un 2. Și asta nu ar fi o simulare fidelă a operația sau, pentru că 1 sau 1 ar trebui să fie doar 1, nu 2. Deci aceasta este o întrebare bună aici. Toate numerele trebuie să fie zero și unu? Nu sunt sigur cum ar funcționa negația cu numere mai mari. Negația, o urmărești orbește. Chiar dacă vom introduce valori non-booleene, va fi 1 minus 7. Deci veți obține minus 6. Trebuie să faceți acel mod P, mod Q, indiferent de valoarea pe care o obțineți. Dar nu mai poți gândi la asta ca o negație în primul sens. Acum devine doar un lucru formal. Doar te îndepărtezi făcând ceea ce spune polinomul. Ies numerele. Crezi că asta este doar o prostie. Dar chestia este că va avea un sens care ne va fi de folos. Asta va arăta acest protocol. Deci nu mai poți să te gândești la asta ca la o negație. E doar negația devine 1 minus x în lumea aritmetică și trebuie doar să trăiești cu asta. Să vedem. O altă întrebare aici. Dacă toate phi-urile sunt echivalente pentru intrările booleene din check- in, deci aceasta este din nou în acest check-in aici, deci dacă toate-- da. Deci întrebarea este dacă toate sunt echivalente în cazul boolean, de ce este doar un corect? Pentru că am definit P sub phi într-un fel anume. Și deci aceasta a fost valoarea pe care o obțineți dacă urmați modul în care eu definesc P sub phi. Ceilalți ar funcționa, pur și simplu nu erau așa cum am definit-o. Alte întrebări aici? Probabil ar trebui să mergem mai departe. Poate fi folosită aritmetizarea în alte contexte? De la mână, nu știu. Există aceste două cazuri în care aritmetizarea funcționează. Dacă există și alte cazuri , de fapt nu sunt sigur. OK, deci hai să mergem mai departe. Deci cronometrul nostru este activat. Lumânarea a ars. BINE. Deci asta a fost... OK, iată-ne. Acesta este protocolul real. Așa că o să ți-l prezint așa cum am făcut-o înainte. Să ne gândim mai întâi cu cazul în care intrarea este în limbă și avem un doveditor sincer. Deci începem la fel. Dovatorul trimite phi, trimite numărul phi. Care în vechiul sens era numărul de sarcini satisfăcătoare. De fapt, încă mai este, pentru că, din moment ce nu presetăm nimic, încă nu există nicio valoare booleană în imagine . Deci aceasta va fi aceeași valoare ca înainte. Verificatorul verifică dacă k este egal cu numărul phi. Deci, de aceea trebuie să avem un câmp suficient de mare acolo, astfel încât să putem reprezenta numere până la numărul potențial de sarcini satisfăcătoare. Dar asta e o notă secundară. Dar oricum, asta este exact ceea ce am făcut înainte. Nicio schimbare. Numărul de sarcini satisfăcătoare, dacă doriți. Acum, să vedem. Să ne amintim. Și acesta este unul dintre acele cazuri în care nu avem o tablă mare ne împiedică. Așa că o să-ți amintesc ce am făcut ultima dată. Dar o să schimb asta. Așa că nu uitați înainte ca P să trimită... și să despacheteze la un singur nivel. A trimis numărul de atribuiri satisfăcătoare a spus numărul phi de 0 și numărul phi de 1. Și apoi am făcut această verificare pentru a justifica valoarea anterioară, în care verificatorul nu are neapărat încredere. BINE. Puneți-vă centurile de siguranță, toată lumea. Aceasta este toată dovada din rândul următor. Dar este un năuc. În regulă. P va trimite phi din z ca polinom în z. Va trimite doar un singur obiect. Dar acel obiect este un întreg polinom. Și modul în care va trimite asta este prin trimiterea coeficienților acelui polinom. Deci, să digerăm această afirmație. Deci, în primul rând, să înțelegem valoarea de a face asta. Deci, dacă pot trimite întregul polinom phi sub z reprezentat ca un polinom, pot conecta 0 și 1 în acel polinom și pot permite verificatorului să facă verificarea pe care trebuie să o facă pentru a demonstra că numărul phi este corect. Deci, va verifica că numărul phi este numărul phi de 0 plus numărul phi de 1. Dar, în loc să obțină acele valori direct de la doveditor, va lua acel polinom pe care l-a obținut și va evalua acel polinom la 0 și 1. Și doar pentru a amintiți-vă, să ne întoarcem și să ne amintim cum am definit-- definit numărul phi pentru a ne asigura că înțelegem ce înseamnă să ai un polinom aici. Așa că nu uitați, aici luăm doar prima valoare. Dar ești de acord să pui o constantă 0 sau 1 și apoi să adunăm peste toate extensiile posibile, toate extensiile booleene posibile la asta. Și poate că este în regulă să introduceți o valoare non-booleană aici, cum ar fi 7. Și apoi luați variabilele rămase și le atribuiți zerouri și unu în toate posibilitățile și le adunați. Acum o să fac ceva și mai sălbatic. Voi introduce o variabilă pentru a1. Unele valori simbolice, dacă vreți, simbolice. Deci voi pune o valoare z pentru a1. Deci acum conectez z pentru a1 aici. Și de la a2 la am vor fi zerouri și unu în toate modurile posibile. Deci obțin doar un polinom în z. Celelalte variabile sunt atribuite și adăugate peste diferitele atribuiri booleene. Și acum am niște polinom. Deci am o expresie în z. Acesta va fi doar un singur polinom variabil. Al cui grad va fi? Cel mult gradul de număr phi. Deci, gradul nu va fi prea mare. Deci trimite coeficienții, astfel încât gradul acestora să nu fie prea mare. Deci nu sunt prea mulți coeficienți de trimis. Deci coeficienții sunt în termeni de xi. Nu. Nu sunt sigur ce înseamnă-- coeficienții nu sunt în termeni-- xi au dispărut în acest moment. Xi-urile, am adunat xi-urile fiind alocate la zerouri și unu în toate modurile posibile. Deci nu au mai rămas alte variabile. Există doar z. Așa că voi face același protocol într-un mod mai pictural într-un minut. Deci o să vezi toată chestia asta de două ori. Dar încearcă să-l obții. Vei avea două șanse să obții asta. Încercați să o obțineți. Încercați din greu de fiecare dată. Deci, am să trimit phi din z ca polinom în z. Acum, asta va fi suficient pentru a-mi da seama ce număr este phi de 0 și numărul phi de 1 , pentru că îl conectez pentru 0 și 1 pentru z. Dar acum îmi pot da seama care este și numărul phi de 2 , pentru că pot conecta 2 pentru z sau numărul phi de 7. Conectez 7 pentru z. Deci haideți să ne oprim aici și să vedem dacă există alte întrebări. La fel și dimensiunea numărului phi... Nu înțeleg. Această întrebare despre dimensiunea no phi. Este 2 la m? Nu, nu este 2 la m, pentru că gradul acelui polinom, numărul phi al lui z, vreau să spun, este o expresie foarte mare dacă inițial vrei să-- da, va fi o sumă exponențial mare. Dar probatorul adună totul pentru tine și vei avea cel mult un număr mic de coeficienți, deoarece polinomul este doar într-un anumit grad. Și un polinom dintr-o variabilă de grad d are cel mult d sau d plus 1 coeficienți de care să vă faceți griji. Deci nu sunt atât de mulți coeficienți ca expresie. Deci însumarea nu ar trebui să dureze 2 la m timp? Nu-mi pasă de timpul doveditorului. Dovatorul are mult de lucru. Dar probatorul trimite phi de z. Deci da, dovatorul are o treabă exponențială. Nu-mi pasă. Verificatorul trebuie să-l poată verifica în timp polinomial. Și această verificare va fi, ei bine, va trebui să vedem. De unde știe verificatorul că acel polinom este corect? Asta e o întrebare pe care ar trebui să o pui. Da. Primesc o mulțime de întrebări despre cât timp trebuie să-i ia probatorul. Da, dovatorul va trebui să petreacă timp exponențial pentru a-și da seama de acel polinom. E bine. Nu ne pasă de timpul doveditorului. Da. Deci, însumarea aici va fi adunarea polinoamelor. Este corect. Mă bucur să-mi petrec timpul, pentru că într-adevăr aici aceasta este toată dovada. Trebuie să înțelegi. Ei bine, trebuie să înțelegem de ce funcționează. Dar înțelegem jumătate din el, pentru că știind că polinomul este suficient pentru a-- dacă ați putea certifica că acesta a fost polinomul corect pentru numărul phi al lui z, atunci putem folosi acel polinom pentru a confirma valoarea anterioară, ce număr phi a fost , pentru că doar introduceți zerouri și unu pentru z și le adunați. Dar acum cum vom justifica că polinomul este corect? Pentru că asta pare o muncă și mai proastă. Acum avem o grămadă de coeficienți și trebuie să ne asigurăm că toți acești coeficienți sunt corecti. Și astfel, în loc de doar două valori, acum avem d valori unde d este gradul acelui polinom, care ar putea fi cel mult lungimea formulei. Deci iată următoarea idee. Deci, dovezitorul trebuie să arate că phi-ul lui z este corect. Modul în care va face asta, deci chiar înainte de a face asta, deci phi din z va fi un polinom. Acum, probatorul poate minte, poate trimite polinomul greșit. Cum îl convinge probatorul pe verificator că polinomul este polinomul potrivit? Ei bine, asta pare o muncă grea. Deci, ceea ce va face este să vă amintiți că... deci există un polinom corect pe care l- ați obține prin conectarea la această expresie pentru valoarea corectă. Deci există un polinom corect. Dovatorul poate trimite un polinom incorect. Deci acum avem polinomul corect și polinomul posibil incorect. Și ideea este că cei doi pot fi de acord doar într-un număr mic de locuri prin faptul că am demonstrat câteva prelegeri în urmă cu privire la polinoame. Deci două polinoame diferite pot fi de acord doar rar. Deci, ceea ce vom face, modul în care demonstratorul va justifica că acest polinom a fost cel corect, este prin evaluarea lui într-un loc aleatoriu și apoi demonstrarea că acea valoare pe care o obțineți este o valoare corectă. Dacă polinomul a fost polinomul greșit, atunci evaluarea lui într-un loc aleatoriu va fi probabil în dezacord cu polinomul corect din acel loc, deoarece pot fi de acord doar rar. Deci, dovatorul va demonstra că, evaluând acel polinom într- un loc aleatoriu, acea valoare pe care o obțineți va fi valoarea corectă și va continua să facă asta în același fel, folosind același protocol, așa cum vom vedea. Deci acolo mergem. Deci, pentru a arăta că phi-ul lui z este corect, verificatorul poate alege acum o valoare aleatorie în câmp. Și demonstratorul va arăta că evaluarea acelui polinom la r1 este corectă. Amintiți-vă că acest lucru seamănă mult cu ceea ce aveam înainte, unde arătam că numărul phi al lui 0 este corect și numărul phi al 1 este corect. Acum încercăm să arătăm acel număr phi al lui r1, această valoare aleatorie din câmp este corectă. Așa că modul în care vom face asta este acum despachetarea cu un nivel mai jos. Și vom folosi acea identitate, deoarece această valoare aici va fi egală cu numărul phi din r1 virgula 0 plus numărul phi din r1 virgula 1. Dar nu vrem să le trimitem pe ambele. Deci le vom trimite combinate într-un polinom de număr phi al r1 din z ca polinom în z. Acesta este un nou polinom în z. Deci, acum, dacă ați înțeles linia anterioară, atunci sperăm că aceasta nu va fi prea greu de înghițit. Pentru că acum vom verifica identitatea, dar aici evaluând din nou polinomul, dar un nivel la nivelul următor. Deci, acesta este probabil un loc bun pentru a răspunde la întrebări, pentru că acesta este... asta este cu adevărat ceea ce am petrecut tot timpul pregătind lucrurile, astfel încât să fiți gata să obțineți acest lucru, sperăm, fără - și sper să puteți aprecia asta si intelege-o. Deci nu primesc întrebări. Să trecem puțin mai departe. Deci, acum, din nou, probatorul a trimis acest polinom în etapa a doua. Acum verificatorul trebuie să se asigure că acel polinom este corect. Deci, va evalua acel nou polinom într-o locație aleatorie. Deci prin alegerea unei valori aleatorii r2 în câmp. Și acum trebuie să arătăm că această valoare este corectă, pentru că dacă acel polinom ar fi fost polinomul greșit, aproape peste tot nu a fost de acord cu polinomul corect. Și prin alegerea unui loc la întâmplare, probabil că nu va fi valoarea potrivită și așa mai departe. Până când ajungem la sfârșit, unde avem aproape toate valorile au fost alese, și astfel avem o ultimă valoare pentru a selecta 0 și 1. Aceasta corespunde n-a. Ar fi grozav dacă aș putea pune ambele imagini pe ecran, dar nu pot. Deci, acest lucru corespunde foarte mult cu ceea ce sa întâmplat în protocolul exponențial, dar doar de-a lungul unui fel de cale unică de aritmetizare. Deci verifică dacă valoarea anterioară este corectă în ceea ce privește extinderea ei cu 0 și 1. Dar din nou, 0 și 1 provin din evaluarea polinomului. Și acum verificatorul trebuie să fie convins că acel polinom a fost corect. Deci alege o valoare aleatorie, dar acum nu se mai bazează pe doveditor. O să vedem dacă acea atribuire pe care o primește evaluând polinomul cu acea valoare aleatoare rn conectată este aceeași cu ceea ce obțin eu evaluând polinomul pentru formula în sine pe care verificatorul o poate face direct. Deoarece acesta este acum un polinom, acum doar conectați-vă la formulă și folosiți aritmetizarea pentru a obține o valoare. Deci aceasta a fost ultima linie a identității. Aveam acele două identități. Deci aceasta este a doua identitate. Și a trebuit să verificăm dacă acest lucru este corect. Așa că vă voi arăta asta într-o poză. Nu sunt sigur că te va ajuta dacă ești confuz. Dar de ce nu luăm câteva întrebări despre asta? Așa că, așa cum am spus, vă voi oferi două șanse să înțelegeți asta. Pentru că știu că e greu. În special cu constrângerile Zoom, aceasta este o idee deosebit de provocatoare de explicat. OK, deci să vedem. Deci, avantajul acestei abordări este că probatorul trimite doar un articol pentru fiecare nivel de adâncime în loc de mai multe articole. Asta e corect. Dar acel element este polinomul. Deci, acesta captează toate valorile pentru întregul câmp. Dar profitând de aritmetizare, acel polinom are o mulțime de informații în el. Și ce este frumos este că poți verifica acel polinom doar evaluându-l într-un loc aleatoriu. Puteți verifica dacă acel polinom este corect. Deci primesc o altă întrebare aici. De unde vine asta de aici? V verifică asta aici. Deci, de unde face asta... deci trebuie să te uiți... pentru a înțelege de unde vine asta, trebuie să... suntem la a n-a rundă acum. Așa că trebuie să te uiți înapoi ca în runda a doua. V trebuie să verifice acel phi al lui r1, care vine de la sfârșitul primei runde. Deci, aceasta verifică dacă acest phi al lui r1 este corect, deoarece așa am justificat polinomul cu o singură variabilă. Primul polinom a fost corect. Cam greu de spus. Dar asta vine din runda anterioară, tipul ăsta de aici. Deci acesta este polinomul pentru runda curentă. Aceasta este valoarea din runda precedentă. În regulă. Mai multe întrebări. Deci, de ce nu se execută acest lucru în timp exponențial? O altă întrebare pe care o primesc. V nu trebuie să verifice de două ori la fiecare strat? Da. Verificatorul trebuie să verifice-- primește două valori, dar acele două valori provin de la un singur polinom. Deci nu mai e nicio explozie. Acele două valori. Poate o vei vedea în poza pe care o voi arăta. Așa că poate ține la întrebarea asta. Poate că acest lucru va deveni mai clar în diagramă. Deci o altă întrebare. Funcționează acest lucru deoarece tipul polinom codifică împreună toate valorile posibile? Cred că este oarecum adevărat. Le amestecă pe toate într-un singur obiect. Apoi trebuie să verificați acel obiect, ceea ce se poate face cu acest tip de sondare aleatorie a acestuia. Deci aceasta este o altă întrebare bună pe care o vom vedea explicată în următorul diapozitiv. Așadar, în mod similar în prima încercare, probatorul poate continua să mintă prin alegerea polinoamelor continuând să aleagă polinoame, mințind despre polinoame. Dar în cele din urmă va fi prins, pentru că această valoare va fi o valoare greșită. Dacă polinomul din etapa anterioară și m minus-- dacă un polinom pe care demonstratorul l-a trimis în etapa m este polinomul greșit, atunci îl evaluezi, probabil că vei obține o valoare greșită. Și atunci acea valoare greșită nu se va potrivi cu valoarea corectă, adică vă puteți citi singur citind formula. Cred că trebuie să trecem la următorul diapozitiv. În regulă. Deci aceeași dovadă, versiunea a doua, dar arată diferit. Din nou, intrarea este aceea. Iată ce trimite probatorul. Iată ce trimite verificatorul. Voi proiecta asta într-un fel ca un chat telefonic în care își trimit reciproc mesaje prin mesagerie. Deci, probatorul trimite numărul phi pentru a începe cu. Și apoi, pe partea laterală, acestea sunt verificările pe care le va face verificatorul. Așadar, aici, în prima noastră rundă a chat-ului, probatorul va trimite phi of z. Amintiți-vă că acesta este doar un polinom cu nu prea mulți coeficienți. Deci este un polinom într-o variabilă. Gradul este mic. Deci nu sunt prea mulți coeficienți aici. Deci, aceasta este doar prefacerea că așa ar putea arăta. Deci, din acel polinom, verificatorul poate conecta 0 și 1 și poate vedea că se adună. Acum verificatorul, pentru a verifica dacă acest polinom este corect, alege o valoare aleatorie pentru a evalua acest polinom. Și acum va trebui să verifice dacă acest lucru este corect. Deci nu este nimic de verificat. Doar scrieți asta în așteptarea următoarei verificări. Acum, dovezitorul pentru a justifica faptul că această valoare este corectă, că acest polinom este corect, așa că evaluăm-- dovezitorul pentru a verifica dacă această valoare este corectă va trimite polinomul pentru următorul nivel. Acum, putem de la asta, putem conecta 0 și 1 pentru z. Vezi dacă asta se adună. Și acum, pentru a fi siguri că acest polinom este corect, îl evaluăm într-un loc aleatoriu, calculăm acea valoare și apoi trebuie să vedem că această valoare este corectă. Așa că acum ne extindem la un nivel mai departe. Luăm un polinom pentru următoarea variabilă. Și vedem că se adună. OK, nu sunt sigur dacă acest lucru ajută sau nu. Dar continuăm să facem asta până ajungem la ultima rundă cu un doveditor care trimite un polinom. Asigurați-vă că aceasta se adună corect. Iar verificatorul pentru a vedea că acest polinom este corect alege o valoare aleatorie și o evaluează și acum verifică dacă aceasta este în acord cu formula. Pentru că acum am atribuit toate variabilele. Și apoi putem verifica acest număr phi direct în ceea ce privește phi, pentru că trebuie să fie de acord. Și astfel verificatorul ar accepta dacă totul se verifică. Să vedem ce se întâmplă. Deci acest răspuns va răspunde la câteva întrebări. De ce nu parcurg ce se întâmplă dacă introducerea a fost greșită. Și vom vedea cum este probabil ca verificatorul să prindă probatorul, dar nu este garantat să prindă probatorul în acest caz. Deci, dacă k a fost corect, verificatorul va accepta împreună cu probatorul cinstit. Dar dacă k a greșit, așa că voi indica, din nou, valorile greșite în roșu. Vreau să vă arăt că verificatorul va accepta aproape sigur, dar nu va garanta. Deci am spus greșit? Deci, dacă k este greșit, verificatorul va respinge probabil, dar nu este garantat să respingă. Deci, în primul rând, dacă probatorul nu minte, nu trimite valoarea greșită pentru numărul phi, verificatorul va respinge cu siguranță, deoarece nu va obține nicio calitate acolo. Deci dovatorul trebuie să mintă. Spuneți dacă k a fost 99, dar valoarea reală a fost 100, probatorul dacă spune 100, verificatorul va respinge imediat. Deci, dovatorul va spune, ei bine, să vedem ce poate face probatorul pentru a-l face pe verificator să accepte din punctul de vedere al dovatorului. Deci, probatorul va trimite 99. Ei bine, verificatorul spune, OK, 99, bine. Convinge-ma. Deci, dovatorul... acum unul dintre acești doi se va înșela. Pentru că cele două valori corecte nu se pot adăuga la valoarea greșită. Deci una dintre acestea este greșită. Deci, asta înseamnă că probatorul a trebuit să trimită polinomul greșit. Pentru că polinomul corect ar evalua răspunsurile corecte aici. Deci probatorul a trebuit să trimită polinomul greșit. Deci, acum, când o evaluăm într-un loc aleatoriu, sunt șanse ca acesta să fie greșit - aceasta nu va fi aceeași valoare pe care ți- ar fi dat-o polinomul corect . Dovatorul ar putea avea noroc. Verificatorul s-ar fi putut întâmpla să aleagă un loc în care polinomul corect și polinomul incorect sunt de acord. În acel loc, dovatorul se va gândi, huh, eu sunt salvat. Acum pot să mă comport ca un doveditor cinstit din acest moment și verificatorul nu mă va prinde niciodată. Este un pic analog cu situația, poate... Încerc să văd dacă ai studiat cu adevărat întregul curs. Așa că vă dau un examen alegând un fel de locuri aleatorii acolo. Dar poate că tocmai ai studiat câteva fapte de la curs. S-ar putea să ai noroc. S- ar putea întâmpla să întreb doar despre acele fapte. Și apoi dai impresia că ai studiat totul, dar chiar nu ai făcut-o. Așadar, aici demonstratorul ar putea trimite polinomul greșit, dar verificatorul doar întreabă că în locul în care se întâmplă să fie de acord cu polinomul corect, iar probatorul are noroc. Și verificatorul va accepta, în acest caz. Dar sunt foarte puține dintre acestea. Deci, de aceea, cel care dovedește este aproape sigur de prins dacă încearcă să mintă. Dar nu este garantat. Așa că urmăresc asta în jos. Dacă aceasta a fost o minciună, atunci unul dintre cei doi trebuie să fie o minciună. Prin urmare, următorul polinom trebuie să fie o minciună. Și așa continuăm. Deci, următoarea valoare va fi aproape sigur o minciună. Nu este garantat. Și atunci una dintre aceste două valori trebuie să fie o minciună. Cel puțin una trebuie să fie o minciună. Prin urmare, polinomul trebuie să fie o minciună și așa mai departe până... cu excepția cazului în care probatorul a avut noroc pe drum undeva, ceea ce este foarte puțin probabil, deși are mai multe oportunități. Am aranjat-o astfel încât șansa de a avea noroc să fie mică la fiecare etapă. Așa că, deși are câteva șanse, tot va fi o șansă mică ca tu să ai noroc undeva. Și deci acest lucru este greșit, atunci sunt șanse să fie greșit. Prin urmare, acesta va fi un dezacord. Și verificatorul în acel moment în care nu este de acord va respinge. Cu excepția cazului în care dovatorul a avut noroc undeva pe parcurs, ceea ce este puțin probabil. Deci nu știu dacă ai avut... așa că asta e tot ce voiam să spun despre această dovadă. Nu știu dacă ați avut întrebări despre asta, dar să vedem. BINE. Deci avem întrebări la care pot răspunde? Cum obține dovatorul-- cum obține un demonstrator număr-- cum obține dovezitorul numărul phi al lui z? Deci, trebuie să-- de ce numărul phi al lui z nu are alte variabile? Trebuie să te întorci și să te uiți la definiția numărului phi al lui a. Pentru că adunați peste toate celelalte variabile. Deci acum, în loc de a, conectăm o variabilă pentru asta. Dar încă adunați peste celelalte variabile. Deci aceasta este o funcție într- o singură variabilă, pentru că... lucrul inițial a fost un polinom. Acesta va fi, de asemenea, polinom. Cred că începem să pierdem timpul. Deci, acesta este ultimul nostru check- in pentru semestru aici. Deci, desigur, există o întrebare firească pe care să vă puneți tuturor. Și pentru ultimul nostru check-in, întrucât ne aflăm în ultimele minute ale cursului sau cel puțin cursurile, P este egal cu NP? Ce crezi? Poate PB va fi egal cu NPB rezolvat printr-un algoritm de învățare profundă? Sau poate nu vom dovedi niciodată. Dă-mi cea mai bună ipoteză. Suntem cam fără timp. Deci, să nu ne gândim prea mult aici. Încă cinci secunde. În regulă. Încheierea sondajului. Îți voi împărtăși asta. Oh, am împărtășit. Deci ce am primit? D aici. O vom dovedi peste 20-100 de ani de acum înainte . Asta pare a fi opinia majoritara. Nu știu. Sper că va fi mai devreme , pentru că aș vrea să văd răspunsul. Dar nu știm. Da, dacă poți dovedi P diferit de NP, îți voi da un A+. Nu va trebui să luați finala. Dar mai bine fii sigur că ai dreptate. În regulă. Deci aceasta este recenzia noastră rapidă. Am terminat setul de numere în IP și, prin urmare, acel coNP este un subset al IP. Dacă sunteți interesat să urmăriți în continuare acest material, am câteva întrebări despre acesta. Acestea sunt câteva cursuri pe care poate doriți să le urmăriți. Știu că am verificat cu Ryan Williams. El plănuiește să predea Complexitatea avansată în toamna anului 2021. Așa că acesta va fi cel mai firesc subiect de continuare la acesta. Există, de asemenea, clasele cripto care folosesc unele dintre aceleași idei. Și există, desigur, și calculul aleatoriu pe care îl predă Ronitt Rubinfeld. Dacă n-am verificat cu ea. Nu sunt sigur data viitoare când va preda asta. Și mult succes în finală și cele mai bune urări. Și voi avea ore de birou. Deci, dacă aveți întrebări, vă rugăm să răspundeți la acestea. Dar în rest, ne vedem pe toți. Noroc. Multumesc pentru comentarii. Da, mi-a plăcut să vă am pe toți studenți. A fost un timp distractiv. Multă muncă, dar a fost o perioadă distractivă. Am fost întotdeauna intrigat de problema P versus NP și am demonstrat un fel de a-- Am demonstrat complexitatea exponențială a calculării funcției de paritate într-un anumit model slab de calcul. Deci, funcția de paritate este, evident, o funcție foarte trivială. Dar pentru funcția de paritate, dacă nu poți număra, orice înseamnă asta, dar există un model pe care îl poți cam configura unde nu poți număra. Atunci paritatea necesită complexitate exponențială. Și, în mod surprinzător, nu este ușor de dovedit. Dar aceasta este probabil teorema pentru care sunt cel mai cunoscut. Oricum. Dar acesta ar fi un subiect pentru altă zi. Alta intrebare. De ce să nu includeți teorema Myhill-Nerode. Nu știu. Aceasta este o teoremă despre automatele finite și toate acele moduri de a caracteriza limbajele obișnuite. Pare un fel de teoremă tehnică. Nu văd prea mult rost să-l acoper. Și o altă întrebare pe care mi-o pun unii dintre colegii mei este de ce nu am teorema lui Rice, care oferă un fel de mașină pentru a demonstra indecizia. Și nu știu. Cred că poți folosi teorema lui Rice fără să înțelegi cum să dovedești indecizia. Este ca și cum ai bifa o casetă. Bifând niște căsuțe și apoi ai concluzionat că ceva e nehotărât. Aș prefera ca cineva să înțeleagă, decât să pot folosi un instrument puternic. Putem înțelege acea dovadă despre funcția de paritate la care tocmai am făcut aluzie? E super greu. Cu cunoștințele din această clasă, cred că poți. Acea teoremă se bazează pe o anumită tehnică pe care nu am acoperit-o, numită metoda probabilistică, care este un fel de metodă uimitoare. Nu este greu de explicat, dar practic arăți că ceva există arătând că probabilitatea ca un obiect aleatoriu să aibă proprietatea pe care o cauți este mai mare de 0. Și, prin urmare, lucrul pe care îl cauți și care are această proprietate trebuie să existe. Există o mulțime de exemple în acest sens în zilele noastre. Dar este o metodă uimitoare. Așa că folosim această metodă. Cred că calculul cuantic poate rezolva probleme utile dincolo de capacitatea computerelor? Habar n-am dacă se poate construi cu adevărat un computer cuantic. Se pare că sunt întotdeauna 20 de ani liber, cel puțin pentru a face unul care factor. Și am fost, literalmente, îmi amintesc că oamenii în urmă cu 20 de ani spuneau că sunt 20 de ani liber. Deci nu cred că converge. Sunt sceptic că vor construi vreodată un computer cuantic care poate factor. Voi ieși pe o parte și voi spune asta. Dar asta e controversat. Și dacă poate rezolva alte probleme utile, nu sunt sigur ce alte probleme utile există. Ei bine, cred că simulează sisteme cuantice. Deci poate asta ar fi posibil. În regulă. Cred că o să termin asta acum. Dar vă mulțumesc, tuturor. Ai grijă. Pa! Pa.