Bună tuturor, mă bucur să vă avem pe toți înapoi pentru ultima parte a teoriei calculului astăzi. Ne vom angaja pe ultimul subiect important pentru semestru și acesta va urma, în anumite privințe, ceea ce am început. câteva prelegeri când ne-am uitat la mașinile de turnare probabilistice și la calculul probabilistic și la clasa asociată bpp acum ceea ce vom discuta este, într-un anumit sens, o versiune probabilistică a np și aceasta va fi o clasă de complexitate numită ip, care înseamnă interactiv. sisteme de dovezi um și așa că vom prezenta acel model și vom analiza câteva exemple, uh, aș dori doar să spun la început că acest model este unul foarte important, într-adevăr a fost punctul de plecare pentru un mare o mare cercetare în teoria complexității, așa că o vom atinge cu adevărat, dar oamenii au urmărit mult mai multe cu acest model și este, de asemenea, o conexiune cu domeniul criptografiei, care folosește și modelul sistemului de dovezi interactive. de fapt, o parte din geneza acelui model provine din criptografie, în care mai multe părți fie comunică, fie interacționează într-un fel pentru a atinge anumite obiective de comunicare sau semnare sau parole sau sau sau ce ai, așa că asta este atât o zonă aplicată, cât și una care are o mulțime de teorii foarte interesante asociate, așa că, cu aceasta, vom intra și începem prin a mă micșora și facem doar o introducere. Voi introduce modelul sau conceptul unei demonstrații interactive cu un exemplu și acel exemplu implică problema izomorfismului grafic, care este problema testării dacă două grafice sunt izomorfe, ceea ce înțelegem prin două grafice izomorfe este că sunt izomorfe. într-adevăr același grafic, unul dintre ele poate fi reetichetat sau permutat, astfel încât să arate superficial diferit, pot apărea cu o secvență diferită de etichete sau nodurile apar într-o ordine diferită, dar cu excepția faptului că este într-adevăr la fel grafic, așa că ilustrez că aici, dacă puteți vedea acele două grafice aici care arată diferit unul de celălalt, ambele pe opt note, sunt de fapt același grafic pe care îl pot ilustra printr-o mică animație care îl va transforma pe acesta în acela. unul deci um [Muzică] deci cele două grafice um aceste grafice fiind aceleași um ele sunt noi le numim izomorfe, deci acestea sunt graficele g și h și sunt într-adevăr același grafic, așa că le numim grafice izomorfe și avem o problemă de calcul asociată numită iso căreia i se oferă o pereche de grafice pe care am dori să știm dacă sunt izomorfe sau nu, așa că iso este o colecție de perechi de grafice care sunt izomorfe și este ușor de observat că această problemă este un problema np pentru că tot ce trebuie să faceți pentru a vedea sau pentru a da un certificat că cele două grafice sunt izomorfe unul față de celălalt este să vă spuneți că este doar să spuneți care noduri dintr-un graf corespund cărora celelalte noduri din celălalt grafic um și atunci tot ce trebuie să verificați este că relațiile de margine sunt în concordanță cu acea mapare sau cu acel izomorfism, așa cum se numește um, așa că este ușor să vedeți că problema iso este un np și, dacă nu obțineți asta, asigurați- vă că înțelegeți, deoarece aceasta este întreaga primă parte a prelegerii se va pierde dacă nu înțelegeți această problemă iso acum, întrebarea dacă puteți testa două grafice care sunt izomorfe în timp polinomial nu este clară și, de fapt, aceasta este o problemă nerezolvată până în ziua de azi. și este o problemă care a generat o literatură enormă, uh, există sute de lucrări despre problema izomorfismului grafic, așa cum se numește um pentru a încerca să rezolvăm um, știți, uh, pentru a încerca să vedeți dacă se poate găsi un algoritm de timp polinomial și, de fapt, acesta a fost un rezultat foarte mare doar în ultimii 10 ani, când a fost dat un algoritm sub-exponențial, astfel încât a fost mai mult decât mai rapid decât abordarea de căutare cu forță brută, dar nu a ajuns până la polinom acum de ce există atât de multe atenție doar la această problemă specială np, deoarece nu se știe dacă problema izomorfismului grafic este np-complet. iso nu este cunoscut a fi o problemă np-complet și asta o plasează într-o clasă foarte mică de probleme în np care nu sunt nu se știe că fie în p sau np-complet este un fel de curiozitate că, pentru problemele np, aproape toate au ajuns să fie într-o parte sau alta și, de fapt, um, este un uh um, de fapt, um, cred că este singura problemă care implică doar grafice despre care se știe că nu sunt nici în p, nici în np um, așa că am o întrebare aici care ar fi între exponențial și polinom, de exemplu, nu-mi amintesc care este limita, dar este ceva în intervalul de la n până la log n uh complexitatea timpului pentru grafit mai mult, s-ar putea să mă înțeleg așa greșit, um, nu-mi amintesc exact care este limita, dar asta este semnificativ mai bun decât doi la n sau ceva cantitate exponențială de timp, dar este mai mult decât introduceți orice constantă, deci este mai mult decât orice timp polinomial, deci o altă întrebare de același fel este dacă problema complementară este în np sau dacă iso este în co-np sau hai să vorbim despre în ceea ce privește complementul, dacă complementul iso la care mă voi referi ca fiind problema non-iso dacă se știe că este în np, deci nu se știe, cu alte cuvinte, dacă vă dau două grafice și vă cer să faceți arătați că nu sunt izomorfi să presupunem că nu sunt izomorfi și că treceți prin efortul de a determina că printr-o căutare cu forță brută și acum doriți să demonstrați că nu sunt izomorfi bine, asta nu, nu se știe că sunt un np fie, deci nu există un certificat de certificat scurt cunoscut pentru două grafice care nu sunt izomorfe, nici nu știm cum să facem asta, dar există ceva care este foarte interesant, totuși și are legătură cu capacitatea de a o parte să dovedească alteia că graficele sunt fie izomorfe, fie nu izomorfe, așa că, dacă aveți doar un doveditor, nu am formulat neapărat acest lucru atât de mult în această clasă, dar acesta este un mod complet echivalent de a formula noțiunea de np dacă aveți o verificator de timp polinomial un aprobator care poate produce certificate spune că este un doveditor puternic, așa că dacă aveți o problemă care este în aprobare np, poate convinge un verificator de timp polinomial că uh șirurile sunt în limbă dacă de fapt sunt așa în cazul iso problemă un doveditor poate convinge un verificator de timp polinomial că graficele sunt izomorfe doar prezentând izomorfismul acum pentru cazul non-izomorfismului, nu știm că acea problemă este în np, dar este totuși posibil ca aprobatorul să convingă un verificator că graficele nu sunt izomorfe dacă schimbați ușor regulile jocului um, deci, deși problema non-iso nu este cunoscută ca fiind un aprobator np, poate convinge totuși un verificator de timp polinomial că graficele nu sunt izomorfe presupunând că de fapt nu sunt izomorfe um cu condiția ca um probatorul și verificatorul pot interacționa unul cu celălalt, astfel încât verificatorul să poată pune întrebări demonstratorului și verificatorul ajunge să fie probabilist, așa că asta este în sensul în care vreau să spun că această noțiune este un fel de versiune probabilistică a np bine, deci hai să- ți arăt cum se procedează înainte de a trece la metoda pentru aprobare pentru a arăta unui verificator că graficele nu sunt izomorfe, hai să încercăm să fim mai clari despre model, așa că i' O să ți- l arăt mai întâi informal și apoi îl vom analiza formal, bine, așa că în dovezile interactive sunt două părți și mă voi gândi la ele, deoarece unul dintre ei va fi profesorul, bine, așa că profesorul va juca rolul verificatorului într-un anumit sens, dar este așa, cel care verifică și profesorul fiind cam bătrân și obosit, a predat de prea mult timp poate poate funcționa doar în timp polinom probabil, așa că profesorul dacă vrea să spună dacă două grafice sunt izomorfe sau nu, timpul polinomial probabilistic nu pare să fie suficient pentru a spune dacă două grafice sunt izomorfe sau nu, deoarece pare a fi o problemă mai mult decât polinomială, dar profesorul are ajutor, are o armată de studenții absolvenți și studenții absolvenți nu sunt limitați, uh, în același mod, profesorul este studenții absolvenți sunt tineri, sunt energici, pot sta treji toată noaptea, știu cum să codifice, astfel încât studenții absolvenți să aibă o capacitate de calcul nelimitată, astfel încât noi" Ne vom gândi la studenții absolvenți care joacă rolul de aprobator pentru că nu sunt, nu sunt limitati în capacități, vom presupune că profesorul, pe de altă parte, este limitat, așa că profesorul vrea să știe dacă cele două grafice sunt izomorfe, să spunem orice ar fi ei, nu poate face singur, așa că le va cere studenților să-și dea răspunsul și să raporteze acum, există o singură problemă, profesorul știe că studenții și-ar plăcea pe vremuri să o facă. Petrecerea cred că în zilele noastre le place să se joace mult pe calculator și așa că nu sunt chiar atât de dornici să-și petreacă tot timpul să descopere dacă graficele sunt izomorfe, așa că este îngrijorat că elevii vor veni doar cu un răspuns. și gândiți-vă că el nu va putea face diferența, așa că profesorul nu are încredere în studenți, nu este suficient pentru el ca profesorul să le dea problema studenților și să ia orice răspuns pe care ei îl vor da profesorului vrea să fie convins de bine, deci acum cum ar putea studenții să-l convingă pe profesor de răspuns că au făcut cu adevărat treaba și și-au dat seama dacă graficele sunt izomorfe sau nu bine dacă graficele sunt izomorfe dacă se dovedește că graficele au fost izomorfi și studenții își dau seama că atunci viața este bună pentru că ce vor face ei pentru a-l convinge pe profesor că vor preda izomorfismul și vor arăta că da, vreau să spun că sunt, știi că acele grafice sunt într-adevăr izomorfe și iată cum corespondența lucrează profesorul poate verifica oh, da, acum nu sunt convins, dar să presupunem că graficele nu au fost izomorfe, ce vom face atunci studenții și-au dat seama unde după noapte, altfel vrea profesorul, vrea să fie convins oh, nu, ce sunt vom face bine, de fapt, vom angaja profesorul și studenții se vor angaja în următorul dialog de protocol, ceea ce se va întâmpla este acum, trebuie să vă asigurați că sunteți, acest lucru este esențial de urmat să înțelegem această mică parte a poveștii de aici, pentru că într- adevăr va stabili modelul pentru tot în ziua de azi și mâine și pentru prelegerea de astăzi și următoarea prelegere, bine, așa că ne vom angaja într-o următoare interacțiune între studenți și profesor, ceea ce le va permite studenților să-l convingă pe profesor că cele două grafice într-adevăr nu sunt izomorfe, deci cum va funcționa, apropo, acesta este un lucru mic și frumos, așa că profesorul va lua cele două grafice și va alege unul dintre ele la întâmplare pentru că cele două grafice g și h um să spunem că nu sunt, chiar nu sunt izomorfe, profesorul nu știe cu siguranță că asta susțin studenții profesorul chiar vrea să nu fie convins că studenții au dreptate um, deci profesorul va alege unul dintre cele două la întâmplare, va permuta acea alegere pe care a ales-o și o va preda elevilor să spună bine, aici este unul dintre acele două grafice amestecate aleatoriu, apoi o să îi întreb pe studenți. pe care l-am ales bine acum, dacă graficele nu erau într-adevăr izomorfe, elevii pot verifica dacă acel grafic amestecat aleatoriu este izomorf fie cu g, fie cu h, va fi izomorf cu unul sau cu celălalt și apoi elevii își pot da seama și ei spun oh, ai ales g sau nu, ai ales h, după caz, studenții își pot da seama, dar dacă graficele ar fi izomorfe, atunci acea versiune amestecată a lui g sau h ar fi putut proveni la fel de bine de la oricare dintre ei și elevii ar fi avut nicio modalitate de a ști pe care a ales profesorul, astfel încât să nu poată face nimic, ceea ce ar fi mai bine decât să ghicească, așa că, dacă facem asta de multe ori, profesorul alege la întâmplare, uneori în secret, desigur, alegerile, mânerul alege fie g, fie h iar studenții fac bine de fiecare dată când fie studenții fac treaba cu adevărat, iar graficele nu sunt izomorfe, fie studenții sunt incredibil de norocoși că reușesc să ghicească corect, să spunem de o sută de ori, așa că cum profesorul la întâmplare și alege în secret grh folosește asta își folosește probabilismul aruncă o monedă doar o monedă cu două fețe și spune bine, uneori, dacă o să facem g, uneori, o să facă h doar la întâmplare, alege una sau alta și apoi cu niște mai multă aleatorie devine găsește o permutare aleatorie a celei pe care a ales-o și apoi o trimite studenților și spun de la care a venit, nu sunt sigur de bine, așa că hai să facem o pauză aici, să ne asigurăm că înțelegem cu toții asta, deoarece asta este foarte important, așa că primesc o întrebare aici, cum facem, nu sunt sigur care este întrebarea ta, bine, așa că lasă-mă să spun că da, profesorul va juca rolul verificatorului pe care îl joacă studenții absolvenți, toți sunt aprobatori asta urmează, dar chiar vreau să înțeleg acest protocol aici, bine, așa că cum alege profesorul pielea graficului dacă ești bine, nu știu că aleg graficele la întâmplare, ai doar două grafice, acestea fac parte din intrare Atât studenții, cât și profesorul pot vedea graficele, iar profesorii aleg unul dintre ele la întâmplare folosind o monedă, așa că nu sunt sigur că înțeleg întrebarea acolo unde ar putea p și v să se angajeze într-un protocol în care secretara este activată. partea doveditorului, în schimb, întrebarea dezvăluirii izomorfismului, nu există de ce, așa că nu sunt sigur că înțeleg această întrebare, um, poate vom clarifica acest lucru, știți dacă pentru această mică ilustrație profesorul nu cunoaște graficele ar putea fi izomorfe sau nu ar putea fi izomorfe și, deci, profesorul vrea să fie convins în orice caz, indiferent de răspunsul pe care elevii vor găsi elevii, vom transforma asta într-o problemă legată de un um care decide o limbă în continuare, dar chiar acum Încerc doar să dau o idee a modului în care funcționează modelul. Vreau să trec de la acest model informal și acum o voi oficializa în ceea ce privește modelul care va decide o limbă în regulă, deci modelul sistemului de demonstrare interactivă avem două părți care interacționează, un verificator care este jocul în timp polinomial probabil jucat de profesor în diapozitivul anterior și dovatorul care este puterea de calcul nelimitată jucat de studenți în diapozitivul anterior, ambii ajung să vadă intrarea care în cazul anterior Ei bine, ar putea fi, de exemplu, perechea de grafice pe care le schimbă un număr polinomial de mesaje de dimensiune polinomială, astfel încât întregul schimb, inclusiv calculul propriu al verificatorului, va fi polinom. Singurul lucru care nu este inclus în costul de calcul este munca doveditorului, care este nelimitat, după aceea, verificatorul după interacțiune, verificatorul va accepta sau va respinge și vom defini probabilitatea ca verificatorul împreună cu un anume autorizator să ajungă să accepte în timp ce examinați diferitele posibile aruncări de monede ale verificatorului care ar putea conduce la un comportament diferit din partea verificatorului și, prin urmare, un comportament diferit din partea aprobatorului, astfel încât, peste toate posibilitățile diferite de calcul al verificatorilor, vom analiza probabilitatea ca verificatorul cu acest autorizator special să ajungă să accepte și l-am scris în acest fel, aceasta este probabilitatea ca verificatorul să interacționeze cu probatorul să accepte intrarea este pur și simplu că um, așa că vom lucra printr-un exemplu, vom lucra cu exemplul anterior mai precis într-o secundă, clasa ip pentru dovezi interactive reprezintă clasa de limbi, astfel încât pentru un verificator și aprobator um pentru șiruri în limba doveditor face verificatorul să accepte cu mare probabilitate și iată partea interesantă pentru șiruri care nu sunt în limba probatorul face cu excepția cu probabilitate scăzută, dar fiecare nu există nici un doveditor care poate face decât cu probabilitate mare, așa că nu există nicio modalitate de a înșela dacă te gândești la asta, în cazul non-izomorfismului grafic, nu știi nimic dacă graficele ar fi cu adevărat izomorfi, iar studenții încercau să demonstreze într-un mod amăgitor prin acel protocol că nu sunt izomorfi, ar eșua pentru că nu ar putea face nimic dacă graficele ar fi izomorfe, atunci când verificatorul, profesorul alege unul sau altul la întâmplare. um și se amestecă, studenții nu ar avea de unde să spună care dintre ele a făcut profesorul, așa că indiferent de ce tip de schemă încearcă să vină, nu vor avea noroc, așa că nu este un suport pentru orice strategie pentru coarde care sunt nu în limbajul pentru orice s, orice doveditor care numește p cu o tildă pentru a reprezenta un probator ochi sau strâmb pentru orice doveditor posibil strâmb, chiar dacă lucrând cu verificatorul va ajunge să accepte cu probabilitate scăzută, așa că șirurile în limbaj va fi un doveditor cinstit care urmează protocolul în mod corect, ceea ce face ca verificatorul să accepte cu mare probabilitate șiruri care nu sunt în limba, fiecare doveditor nu va reuși să-l accepte cu mare probabilitate, bine, așa că vreau să spun modul în care îmi place să mă gândesc la asta este că p tilde este un proverb posibil strâmb care încearcă să-l facă pe verificator să accepte când nu ar trebui, deoarece șirul nu este în limba, parcă știi că chiar și tu te poți gândi la asta în cazul um satisfiability um știi că un probator strâmb ar putea încerca să convingă verificatorul că formula este satisfăcătoare atunci când nu este, încercând cumva să producă o sarcină satisfăcătoare, dar asta va fi imposibil, nicio strategie nu poate posibil să funcționeze atunci când formula nu este satisfăcătoare, dacă asta va verifica verificatorul, va căuta acea sarcină satisfăcătoare în regulă și, apropo, nu vom demonstra acest lucru, dar se va dovedi într-adevăr în în același mod, puteți face a treia eroare care ar putea să apară aici ceva foarte mic prin același tip de argument de repetare, bine, deci să vedem de ce nu poate doveditorul din primul caz să fie strâmb, dacă demonstratorul din primul caz ar ar putea fi strâmb, dar asta nu va servi scopului um știi ce vrem să arătăm um crezi despre asta așa cum ne gândim noi despre np pentru șiruri în limbă există un certificat există o dovadă că ești în limbă deci, dacă cineva nu va produce dovada care este irelevantă, întrebarea este dacă te uiți la cel mai bun caz posibil, cel mai bun dovad posibil, știi cine va putea, întrebăm dacă există o modalitate de a convinge verificatorul că um șirul este în limbă, așa că nu contează că ar putea exista un alt mod prostesc care nu funcționează, ne uităm doar la cel mai bun mod posibil, așa că cel mai bun mod posibil când ești în limbă este să mergem pentru a ajunge cu un verificator cu o probabilitate mare atunci când nu sunteți în limba, cel mai bun mod posibil va ajunge cu o probabilitate scăzută când, când vorbesc despre cel mai bun posibil, încerc să maximizez probabilitatea ca verificatorul să meargă pentru a ajunge să acceptăm, să continuăm, nu sunt sigur atât de clar pe cât mi-aș dori, dar poate din nou vom rămâne cu acel exemplu, deoarece acesta este un exemplu foarte util și pentru a încerca să înțelegem configurația și uh. deci vom revedea acel exemplu anterior despre non-izomorfism, dar acum, în contextul acestei gândiri ca limbaj, vom lua acest non-izomorfism um uh da, vom lua problemă de non-izomorfism și arătați că este un ip, așa că va exista un verificator împreună cu un aprobator, care vor face verificatorul să accepte cu mare probabilitate șiruri în limbaj și anume graficele nu sunt izomorfe și nimic nu va fi nicio cale pentru a face verificatorul, cu excepția unei probabilități mari pentru șiruri din limbaj, prin urmare, atunci graficele sunt izomorfe. de ori doar pentru a ne ajuta să ne gândim la asta, dar de fapt de două ori va fi suficient pentru a obține legătura de care avem nevoie, astfel încât verificatorul va funcționa așa, în ceea ce privește verificatorii care comunică pentru prima dată, trimit mesaje către aprobatorul pe care îl va alege aleatoriu grh la fel ca ceea ce a făcut profesorul data trecută, permută rezultatul aleatoriu pentru a obține un nou grafic k care urma să fie care este izomorf, fie la grh, în funcție de alegerea făcută de verificator și apoi trimite acel grafic k acum este rândul doveditorilor. va răspunde prin demonstrație va compara k cu cele două dintre cele două grafice originale, trebuie să fie izomorf la unul sau altul și va raporta care dintre ele va spune bine că alegeți g nu sau ai ales h pentru că probatorul cu capacitățile sale nelimitate poate determina că um și apoi v acceptă dacă aprobarea a fost corectă de ambele ori și dacă aprobarea nu a fost vreodată corectă, verificarea spune oh, ceva e neplăcut aici pentru că știm că probatorul are capacitate nelimitată deci s-ar putea face corect dacă știi dacă a existat dacă acesta a fost un aprobator cinstit și deci dacă nu se înțelege corect, atunci verificarea va fi respinsă, așa că dacă graficele nu sunt izomorfe, probatorul poate spune care dintre ele s-a ales aleatoriu, deci, dacă graficele nu sunt izomorfe, verificatorul cu ceea ce demonstratorul onest îl va accepta cu probabilitatea unu, deoarece acea dovadă sinceră va obține întotdeauna răspunsul corect, care este de cel puțin două treimi este limita de care avem nevoie. nu-ți pasă de spațiul folosit ca răspuns la o întrebare, um, dacă nu eram în limbă, așa că g și i h nu sunt izomorfe, atunci nu există nimic pe care un pervers strâmb ar putea face, deoarece obține un grafic care nu poate spune că nu există nicio modalitate de a face. spune dacă a venit de la g sau a venit de la h um, astfel încât prooferul strâmb să aibă tot ce s-a putut, cel mai bun lucru pe care l-ai putea face este să ghicești un fel de 50 de șanse să avanseze corect de fiecare dată și doar 25 de șanse să o faci de două ori și de aceea am a făcut-o de două ori pentru ca acea eroare să fie mică, așa că există doar 25 de șanse ca aprobatorul să aibă noroc, așa că ar fi un caz de eroare dacă dovada din întâmplare ar alege răspunsul corect de două ori, chiar dacă graficele erau izomorfe deci, pentru cazul izomorf, verificatorul care interacționează cu orice doveditor va accepta acea intrare cu cel mult un sfert 25 din timp, care este mai puțin de o treime, așa că acestea sunt doar pentru a atinge această limită, bine, așa că haideți să răspundem mai întâi la câteva întrebări și apoi voi încerca să umh, te voi întreba că înțelegi asta, așa că asta cred că merită să încerci să înțelegi acest model al acestui sistem interactiv de dovezi este puțin alunecos. Îmi dau seama, dar dacă ții doar ține la intuiția dvs. a doveditorului care încearcă să convingă știți despre uh, cunoașteți un probator puternic care încearcă să convingă un verificator limitat, um, că un șir este într-o limbă uh, doriți ca doveditul să poată reuși atunci când șirul este în limba dar eșuează atunci când șirul nu este în limbaj, da, mergem la cineva să întrebe dacă probatorul identifică grh prin forță brută, da, probatorul își va folosi capacitățile nelimitate pentru a determina dat k dacă provine de la g sau h, um the costul de calcul al aprobatorului este irelevant pentru asta, este exact ca atunci când ne gândim la un certificat, știi pentru satisfacție, nu vorbim despre costul găsirii acelui certificat uh pentru np pentru ip din nou, nu vorbim despre costul probatorul rulează, așa că cineva întreabă dacă răspunsul strâmb pentru fiecare doveditor răspunde aleatoriu sau poate aprobatorul rapid cr să aibă o strategie perimetrul strâmb poate avea o strategie acum noi nu suntem noi presupunem că aprobatorul strâmb este înșelat, dar este totuși va eșua, bine, hai să facem verificarea să presupunem că schimbăm modelul, astfel încât probatorul să poată urmări verificatorul alegând alegerile aleatorii, așa că verificatorul nu mai poate acționa în secret, dar probatorul poate urmări verificatorul acum să presupunem că am avut Același protocol în care tocmai am descris în ce limbă ajungem este aceeași limbă, altă limbă și care este acea limbă, bine, așa că vreau să sper că, um, haideți să- mi dea o idee despre cât de bine mă urmăriți cât de bine merge, da, cineva întreabă despre cum se conectează, de exemplu, cu np, așa că ne vom uita la asta într-o secundă, bine așa că este liniștitor că majoritatea dintre voi cred că sunteți pe drumul cel bun cel puțin pentru acest check-in, presupunem că p folosește acest acces pentru a ghici corect ce acces p nu ghicesc cu adevărat că p este tr este de fapt, nu cred că un p este nedeterminist sau ceva de genul acesta p încearcă de fapt să obțină Răspunsul corect și folosind capacitatea sa de calcul pentru a face asta, dacă este posibil, s- ar putea să nu fie posibil, atunci nu poți face nimic bine, așa că hai să terminăm cu asta sunteți toți în două secunde rămase, vă rugăm să votați, votați acum sau niciodată bine, terminând um, da, deci c este Răspunsul corect aici, dacă probatorul poate urmări ce face verificatorul, probatorul poate vedea ce grafic a ales verificatorul chiar de la început și, astfel, probatorul, fără a fi nevoit să lucreze, poate spune că știi că dovedește, privește peste umărul verificatorului și spune oh ai ales g și acum o permiți la întâmplare, dar nu-mi pasă de asta, doar știu că ai ales g uh, așa că dovada va răspunde înapoi uh g chiar dacă graficele au fost izomorfe, dovada va fi capabil să obțină răspunsul corect, într-un fel interesant, um uh, puteți face o puteți schimba oarecum protocolul um, pentru a face uh că, chiar dacă probatorul are acces la aleatorietatea verificatorului, puteți totuși să realizați acest lucru, dar nu cu același protocol um, deci asta e o întrebare separată, bine, deci să mergem mai departe, vreau să mă încurcă prea mult, bine, aici este un alt check-in, bine, așa că trebuie să-mi spui care dintre următoarele afirmații sunt adevărate, din câte știi acum, că ai să te gândești puțin la cum se leagă astea, uh, cum se leagă np și ip sau bpp și ip unul cu celălalt, bine cum ne descurcăm cu asta, bine așa că va trebui să închidem asta destul de curând, fă tot ce poți. interesant, bine, închiderea magazinului ultimul vot, bine unu doi trei, mai este o persoană care nu a votat, care a votat ultima oară, bine, de fapt, toate sunt adevărate, hai să vedem de ce este np conținut cu ip. ip uh ei bine, mulți dintre voi ați văzut asta deja, așa că haideți să o analizăm rapid um [Muzică] dacă am avea doar un determinist v um știți uh puteți uh poate este doar că poate fi suficient de determinist v cred că este doar va fi echivalent, dar de fapt doar pentru a fi dublu sigur că v-ul determinist și aprobatorul trimit un mesaj verificatorului și apoi verifică că așa ne gândim în mod normal la un certificat pentru np uh, nu cred că va schimba nimic dar ar trebui să verifice din nou că, dacă verificatorul poate pune întrebări, dar cred că atâta timp cât verificatorul este determinist, vei obține exact np aici și acum ce zici de bpp acolo nici măcar nu ai nevoie de aviz pentru că verificatorul este deja probabilistic, așa că verificatorul poate ignora autorizatorul, iar acesta este puțin complicat, uh i p, conține p spațiu, deoarece nu am acoperit asta, așa că nu ai cum să știi asta decât dacă se întâmplă să citești înainte în carte, dar este de fapt adevărat um, în anumite privințe, este puțin ca și cum dovada că uh np este conținut în p space ip este un fel de versiune îmbunătățită a np și tu și există doar un algoritm de forță brută bazat pe un uh o bucată care trece prin întregul arbore de posibilități um verificatorul schimbă verificatorul cu schimburi cu aprobatorul și poate determina că um verificatorul fie va accepta pentru un aprobator, fie va ajunge să proiecteze pentru fiecare autorizator um, așa că nu vom demonstra această afirmație, dar ceva bun să știi, oricum, sunt doar un fapt, dar vom face ceea ce lucru surprinzător cu referire la partea c este că izolarea merge și în sens invers, acesta este uimitor um uh a fost este un rezultat uimitor că totul în spațiul p cu care poți face în ip, deci acesta este ip este de fapt, se dovedește a fi incredibil de puternic, îți oferă totul în spațiul p, obții i p este egal cu spațiul, astfel încât orice problemă pe care o poți rezolva în spațiul p, cum ar fi vreun joc, de exemplu, um, dacă vă puteți imagina că știți formulând dame sau șah ca o problemă bazată pe piese, pe care o știți în funcție de unele detalii ale regulilor pe care le puteți face, deoarece știți că trebuie să o generalizați până la capăt prin Sfârșiți placa, dar bine, să nu ne chibzuim um uh, uh um [ Muzică] nu știm care parte are o victorie forțată la șah și chiar dacă cineva trece prin efortul de a trece prin arborele jocului și determină că să spunem alb are o victorie forțată, uh, nu există nicio cale pentru ei, nu există un certificat scurt, nu știm că acea problemă nu este un np, dar trecând printr-o dovadă interactivă, un doveditor atotputernic ar putea convinge pe cineva că albul are o forță pe care o știi convinge pe cineva în timp polinomial că un alb are un vânt forțat, hai să spunem din nou în șah, puține lucruri întinzându-se pentru că știi că trebuie să vorbești despre asta ca un n cu n nu un opt pe opt, dar cred că în asta spiritul este corect, deci um ok, deci haideți să continuăm, așa că, atunci când nu vom dovedi că acea bază p este conținută în ip, vom demonstra o afirmație oarecum mai slabă, dar foarte asemănătoare um este că uh și din punct de vedere istoric, a fost primul că co-np este conținut în ip, deci nu numai că np este conținut în ip, dar vom demonstra că co np este conținut în ip și asta de fapt are cea mai mare parte din ideea pentru spațiul p fiind conținută în ip și în sine, este doar o dovadă uimitoare, un pic mai ușoară, bine și asta a fost făcut dacă îmi amintesc că cineva mă întreabă când câți ani are asta, e ceva în anii 19, cred că la sfârșitul anilor 90, dar nu sunt. Nu-mi amintesc, dar poate la începutul anilor 90, cred că este sfârșitul anilor 90 când s-a arătat asta, așa că a trecut ceva vreme, bine, așa că, în ceea ce privește relația cu criptografie, au existat două fire paralele, care ambele au venit în mod independent cu noțiunea de sistem interactiv de epurare uh, am fost puțin implicat personal cu asta într-un fel, dar mai ales că era un grup în criptografie care lucra la asta și era un alt grup care de fapt ieșea din lumea izomorfismului grafic. lucrând la asta și au venit cu două modele separate, unul care implică aleatorietatea privată și unul care implică aleatorietatea publică și s-a dovedit că de fapt sunt echivalente și este o poveste interesantă, dar, din păcate, nu o facem. am timp pentru asta, așa că de ce nu mergem mai departe și voi începe să vă arăt cum merge dovada că co-np este conținut în ip și ceea ce vom face este să lucrăm cu o problemă care este aproape ca co p complet, dar um va fi uh bine, va fi această problemă cu numărul, vom vedea conexiunea cu co-np într-o secundă, uh, deci cohen p, deci ar trebui să fie exact k sarcini satisfăcătoare taxă virgula k este setul de perechi în care taxa de formulă are exact k sarcini satisfăcătoare, așa că într-adevăr, aceasta este o problemă de a număra câte sarcini satisfăcătoare aveți într-o formulă um, așa că știți că pentru np aveți cel puțin o um, dar vreau să știu exact câte uh deci numerele acea problemă sunt formula perechilor și numărul deci um și uh, deci dacă definim numărul de număr taxa este numărul de atribuiri satisfăcătoare ale unei taxe, atunci o altă modalitate de a scrie această problemă statistică uh număr este uh perechile phi k unde k este numărul de atribuiri satisfăcătoare ale taxei, așa că vom folosi foarte mult această taxă pentru numărul de notație, așa că asigurați- vă că ați primit notația respectivă, acesta este numărul de atribuiri satisfăcătoare ale acelei formule, bine și iată o definiție, probabil că ar fi trebuit să vă dau mai devreme în termen, dar mai bine mai târziu decât niciodată um uh, așa că ideea că o limbă este np hard este ca np complet, cu excepția faptului că nu este neapărat în np, deci aceasta este doar partea de reducere a unei limbi este np-hard sau co -np-hard sau p-space hard sau oricare dintre acele clase pe care le-am analizat dacă fiecare problemă din clasă este reductibilă la acea limbă, dar nu știi dacă aceasta limbă este în clasă, așa că o numim doar np hard în loc de mp complete, așa că ați putea spune că limbajul este np complet dacă este greu și este în np ok și vom arăta că această problemă a setului de numere este co np grea, așa că totul în cohen p este redus la timp polinomial. set de numere este ușor pentru că ceea ce vom face este să luăm o problemă completă a co np care este problema de nesatisfăcibilitate complementul de satisfacție și sigur că reduce la numere acea problemă și asta este ușor pentru că o formulă este nesatisfăcătoare exact atunci când are zero sarcini satisfăcătoare, deci dacă poți spune câte sarcini satisfăcătoare are ceva exact sau poți răspunde la întrebarea pe care o știi dacă o formulă are exact o mie de sarcini satisfăcătoare dacă poți face asta în general, atunci poți rezolva co și p uh poți rezolva problema Problemă de nesatisfăcutare, întrebând cu zero sarcini satisfăcătoare și care vă permite să rezolvați orice în cohen, bine, așa că vom lucra doar cu această problemă, problema setului de numere și să arătăm că acea problemă este în ip, bine să facem o pauză rapidă. liber să mă trimiți, permiteți-mi să văd dacă pot ajunge din urmă cu unele dintre întrebările care au apărut aici, așa că, dacă aprobatorul cunoaște alegerile aleatorii ale verificatorului, poate răsturna răspunsul pentru a face verificatorul să respingă, nu sunt sigur ce ați înseamnă doar în contextul problemei izomorfismului grafic sau ceva în general, nu sunt sigur că va trebui să explicați. Îmi pare rău, voi răspunde cu un semn de întrebare ce mai pot răspunde pentru voi, așa că am o întrebare dacă i p este egal cu p spațiu înseamnă asta înseamnă că iso sau non-iso ar putea fi um în ar putea fi p spațiu complet, dar nu, asta nu se știe, așa că nu avem timp, bine hai să continuăm aici [muzică] bine, deci aici este locul unde o să începem să intrăm în miezul lucrurilor um [muzică] și dacă nu ai înțeles totul până acum, poate încearcă doar să-ți păstrezi intuiția despre cum știi cum funcționează o petrecere puternică convinge a um un polinomial probabilistic polinom partid de timp a numărului de sarcini satisfăcătoare număr exact nu cel puțin, dar nu vei ști exact numărul de sarcini satisfăcătoare um, deci ar putea fi zero, de exemplu, cum convingi că cum poți convinge pe cineva că au fost zero sarcini și și și știi că poți avea o interacțiune care face asta și asta nu este deloc evident cum vei face asta, umh, în regulă, așa că bine, așa că va trebui să introducem o notație ceea ce nu sper că acest lucru nu provoacă arsuri la stomac aici, așa că să spunem din nou, aici este limbajul de calcul cu care lucrăm setul de numere și avem o taxă unde are m variabile x1 la xm, acum iată notația noastră i Mă duc dacă scriu phi cu acest phi liber de 0, ceea ce înseamnă doar formula pe care o obțin introducând 0 pentru x unu și lăsând toate restul variabilelor singure, bine, așa că înlocuiesc zero cu x unu, unde zero înseamnă fals și unul înseamnă adevărat ca de obicei și, dar așa se întâmplă, va fi o altă formulă, dar doar cu acea înlocuire dacă scriu taxă 0 1 înseamnă că am presetat primele două variabile la 0 și 1. um dacă scriu taxa cu o grămadă de valori prestabilite, doar setez primele i variabile x1 la xi la unele valori și las celelalte variabile ca nesetate, așa că le numesc pe cele pe care le pun în cuie acolo, deoarece spun deja că acestea sunt presetări bine, deci este doar convertirea unor formule în alte formule care au ceva mai puține variabile, acum să ne amintim acea notație numerică, notația semnului numeric, taxa de număr este numărul de sarcini satisfăcătoare acum, dacă spun taxa de număr de 0, acesta este numărul de sarcini satisfăcătoare. atribuiri atunci când am presetat x1 la 0. în mod similar, dacă am presetat primele variabile i la unele valori și apoi iau, vreau să mă gândesc câte câte sarcini satisfăcătoare supuse acelor presetări de prefix le scriu în acest fel, așa că voi merge pentru a folosi foarte mult această notație, trebuie să înțelegeți această notație, întrebați dacă nu o înțelegeți dacă nu o înțelegeți, așa că un alt mod de a o scrie, nu știu dacă este util, dar un alt mod de a scrie numărul de taxă de a1 Îmi amintesc că avem m variabile împreună, ceea ce înseamnă că iau variabilele pe care nu le-am presetat încă și le permit să se încadreze peste toate zerourile și unurile posibile și adun valorile formulelor pentru toate acestea, așa că există una de fiecare dată când mulțumesc și un zero de fiecare dată când nu mulțumesc, așa că adun toate sarcinile satisfăcătoare care fac obiectul acestor presetări i, bine, așa că iată două fapte esențiale despre această notație a semnului numeric, în primul rând, dacă presetez primul i valorile la ceva acum pot, în plus, să setez următoarea variabilă fie la zero, fie la unu și obțin această relație care este doar o generalizare a faptului că numărul total de sarcini satisfăcătoare ale formulei este egal cu numărul de sarcini satisfăcătoare. când x1 este 0 plus numărul de sarcini satisfăcătoare când x1 este 1. corect, împreună trebuie să adună numărul total, deoarece x1 va fi fie zero, fie unul, deci acesta este numărul unu. toate variabilele, deci nu mai sunt variabile, atunci numărul de sarcini satisfăcătoare supuse acelei presetări a tuturor este doar dacă am satisfăcut sau nu formula care este valoarea formulei pe care acele presetări sunt în regulă ambele două fapte simple dar va fi esențial în protocol. Sunt pe cale să descriu întrebări despre asta, cred că de fapt am o întrebare pentru tine, așa că hai să vedem ce crezi pentru a-ți verifica înțelegerea. Nu sunt sigur că e bine, dar în regulă aproape gata de închidere, bine, deci uh da a este răspunsul corect, știi dacă dacă sunt nouă sarcini satisfăcătoare la un loc și există șase sarcini satisfăcătoare în care prima variabilă este setată la zero, atunci există doar trei sarcini satisfăcătoare cu prima variabilă setată la unu, pentru că nouă trebuie să fie egal cu șase plus trei, acesta este de fapt acest fapt numărul unu, nici nu va fi 15, nici asta nu este adevărat, deci este doar bine, bine, așa că hai să încercăm cu Cu aceste cunoștințe, să încercăm să vedem cum putem pune numărul sat în ip, așa că acest lucru nu va funcționa foarte bine, dar chiar ne va face să facem asta pentru a termina asta data viitoare, um, așa că ați putea vedea imediat unde merge greșit. dar va trebui să suportați asta pentru că configurația este importantă, bine, așa că înțelegeți acum, aici este configurația pe care o avem, introducerea este o formulă și un număr în care se presupune că acel număr este Numărul de sarcini satisfăcătoare, știți că ar putea fi greșit și, caz în care nu suntem în limba, um, dar dacă este corect, sunteți în limba, așa că aprobatorul ar trebui să convingă verificatorul că este corect dacă este corect și este nu va eșua, indiferent ce încearcă să facă, dacă nu este corect, deci acesta este aprobatorul va trimite în primul rând, așa că dovada va trimite o cerere despre numărul de sarcini satisfăcătoare care vor fi trimise atunci când Eu spun că această valoare aici este ceea ce doveditorul, dacă este onest, va trimite valoarea corectă, desigur, verificatorul nu știe dacă aprobatorul este onest, dar descriu cum va funcționa aprobatorul onest și vom avea să înțeleagă ce se întâmplă dacă probatorul încearcă să trișeze, astfel încât dovada va trimite dovada sinceră va trimite numărul de sarcini satisfăcătoare toate împreună, iar verificatorul demonstratorului se asigură că aceasta se potrivește cu intrarea dacă nu se întâmplă se potrivește cu intrarea, uh, verificatorul doar o să știi că știi că verificatorul nu va fi convins că intrarea este în limbă, așa că va respinge în acel moment. a fost foarte bine că mi-ați trimis asta. Cum știu că este corect, așa că ceea ce va face verificatorul pentru a încerca să-l convingă pe verificator că această valoare a fost corectă este să dezvăluie asta cu un nivel, să spunem că știi că au fost nouă satisfăcătoare sarcinile toate la un loc, șase dintre ele au fost atunci când x unu este zero și trei dintre ele au fost când x unu este unul pentru a verifica ce are verificarea pentru a verifica dacă acestea se adună corect atunci când am presetat x1 la zero și la una a avut mai bine se adună la numărul total de sarcini satisfăcătoare dacă asta funcționează, verificatorul este mulțumit este încă este în concordanță cu a fi convins că acest k a fost valoarea corectă, um, deci, următorul pas este bine, verificatorul spune bine de unde știu eu acele două valori sunt corecte, doveditorul spune că este bine, voi dovedi că trimit, dezlegați-le un nivel mai departe, atunci iată o serie de sarcini satisfăcătoare când următoarea variabilă este setată la ambele posibilități pentru fiecare dintre posibilitățile primei variabile acum dacă mă înțelegi despre ceea ce trimite probatorul ar trebui să începi să fii puțin nervos pentru că ceva este, vreau să spun că asta va fi corect, dar va începe, se pare că începe să explodeze în ceea ce privește numărul de cantitatea de muncă care este implicată și aceasta este de fapt o problemă, dar să suportăm asta pentru moment, să ne îngrijorăm doar de corectitudine, nu de complexitate pentru moment, așa că dovada va trimite acum numărul de sarcini satisfăcătoare pentru fiecare dintre aceste patru moduri posibile de presetarea primelor două variabile și verificatorul va verifica dacă aceasta a fost în concordanță cu informațiile trimise de probator în runda anterioară, verificând din nou această identitate aici, astfel încât dovada va continua să facă asta până când se va face asta. prin m runde unde m este numărul de variabile, astfel încât în ​​acest moment dovada va trimite toate modalitățile posibile de presetare a tuturor variabilelor, astfel încât acum să fie două la cele m posibilități aici din nou, acest lucru nu este permis fără speranță, dar bine ignorând faptul că proofer trebuie să folosească acest lucru la a n-a rundă pentru a verifica ce se întâmplă la runda anterioară, așa că atunci au fost trimise m minus una, deoarece fiecare are încă una uh uh, extindeți presetările cu una, așa că folosind aceasta pentru a verificați dacă în runda anterioară valorile au fost corecte, așa că caută um, știți că presetările m minus una trebuie să se adună corect um știți în ceea ce privește m presetările m uh valori uh pentru fiecare dintre acele moduri de a face uh acele presetări uh m minus unu și așa că acum cei care dovedesc le trimit pe toate cele două la m numărători care sunt apropo unu și zero, deoarece în acest moment avem presetate toate valorile variabilelor și deci există o singură atribuire posibilă la cele mai multe dintre ele pot exista și acum verificatorul care aproba aprobarea a terminat, verificatorul va verifica de la sine dacă aceste valori au sens că aceste valori sunt corecte, așa că va face asta uitându-se înapoi la formula de până acum, în acest moment, verificatorul nu s-a uitat la formula, ci doar a verificat coerența internă a mesajelor doveditorilor unul cu celălalt, dar acum, la sfârșit, verificatorul va prelua mesajele aceste valori pe care aprobatorul le-a trimis pentru fiecare dintre cele două către m. presetări și vedeți dacă se potrivește cu ceea ce ar face formula. Amintiți-vă că a fost celălalt fel de caz de bază al sfârșitului faptul numărul doi um din glisorul uh până acum asigurați-vă că acestea sunt de acord în regulă și acum verificatorul spune bine bine, dacă totul s-a verificat și toate acestea sunt în acord, atunci verificatorul va fi convins că umh, uh, taxa a avut k sarcini satisfăcătoare, dar dacă oriunde pe parcurs una dintre aceste verificări eșuează, aprobatorul nu este verificatorul nu este. o să fiu convins și o să respingă bine, așa că într-un fel este o prostie, știi că știi că am doar că îți ofer un mod complicat de a număra una câte una fiecare dintre sarcinile satisfăcătoare. a formulei și să vedem dacă se potrivește cu k, dar totuși acest mod de a-l privi ne va ajuta să înțelegem cum să rezolvăm asta, așa că răbdați cu mine încă un minut în privința asta, deci un alt mod de a privi acest lucru. Cred că este deosebit de util este să ne gândim bine la ce se întâmplă bine, vom ajunge acolo într-o secundă. Vreau să mă uit la ce se întâmplă dacă k a greșit, dar înainte de a face asta, hai să ne uităm la ce am de gând să dau un fel a unui grafic o vizualizare grafică a informațiilor pe care le trimite probatorul și acțiunile verificatorilor din acest protocol, deci valorile pe care le trimite probatorul vor fi în galben, deci și informațiile pe care verificatorul le are sau le verifică să fie în alb, astfel încât verificatorul are k valoarea de intrare care ar trebui să fie numărul de atribuiri satisfăcătoare, iar probatorul trimite o valoare și verificatorul verifică dacă această valoare care se presupune a fi numărul de atribuiri satisfăcătoare corespunde cu k, deci aceasta este una dintre verificările pe care le face, atunci aprobatorul va trimite un fel de luare pentru a justifica această valoare, um trimite numărul de sarcini satisfăcătoare când ai x1 setat la zero sau setat la unul, verificarea le adună pentru a-ți oferi și ar trebui să fie egal cu numărul total de sarcini satisfăcătoare și deci, dacă ați înțeles acest protocol, acesta este doar că îl scriu într-un fel simplificat, poate în regulă, și deci continuă să verifice dacă aceste lucruri se adună corect până când te apuci de a seta toate m valorile în toate cele două moduri imposibile și acum verificatorul va verifica apoi pentru a se asigura că este egal cu ceea ce ar spune formula um ok bine, așa că acum haideți ce se întâmplă dacă k a fost valoarea greșită nu a fost de acord cu numărul de sarcini satisfăcătoare și ce se întâmplă acum um ar putea demonstratorul ce se întâmplă dacă aprobatorul încearcă să-l facă pe verificator să accepte oricum, așa că singurul lucru pe care îl poate face probatorul la primul pas ar fi pentru a minți despre faptul că știi dacă aprobatorul trimite dacă k este greșit și aprobatorul de dovadă trimite valoarea corectă pentru numărul total pe care verificatorul îl va respinge, așa că încerc să văd dacă ar putea încerca să o facă aprobatorul verificatorul acceptă ceea ce se întâmplă, așa că probatorul trebuie să stea aici și voi indica că spunând că aprobatorul trimite o valoare greșită pentru um uh, numărul total este bine dacă dovada va fi aici um, atunci doar cum știi dacă știi că ai un copil care spune o minciună și apoi începi să știi, ca părinte, începi să pui întrebări pentru a încerca să vezi dacă povestea este consecventă, o minciună va duce la o altă minciună și asta e ce se întâmplă aici dacă pentru a justifica această minciună, dovada va avea o minciună în una sau poate ambele, dar cel puțin una dintre aceste două valori, deoarece nu puteți avea cele două valori corecte însumând cele incorecte valoare pentru că trebuie să te gândești la ce se întâmplă aici, așa că, dacă aceasta este o minciună, va forța o minciună la una din laturile celeilalte, la un nivel mai jos, ceea ce va forța apoi o minciună să se propage în jos și deci există o minciună. în fiecare etapă va forța o minciună cel puțin într- un loc sau altul să se propagă până în jos și apoi în partea de jos verificatorul va vedea că verificarea nu funcționează ca atunci când se întoarce când încearcă să conectați-l cu formula în sine și verificatorul de formulare va respinge bine, deci doar un mod de a privi acest lucru um dacă forma dacă valoarea dacă intrarea nu a fost în limba um deci uh, dar problema este că așa cum am spus că asta este exponențial, deci cum o să rezolvăm asta, așa că uitându-ne la ceea ce vom face marți, bine haideți să vedem dacă există întrebări aici, în primul rând uh ok da, am o întrebare dacă aceasta ar fi, uh ar trebui să fie un minus i am făcut intenționat acest parantez să nu includă ultimul zero, da, sunt un total de m zerouri aici, toate împreună, dar am omis ultimul zero, de aceea am spus n minus unu, poate ar fi fost mai bine să spun m bine, deci și aveți o altă întrebare interesantă aici, de ce nu putem respinge imediat dacă k este greșit, umh, ei bine, verificatorul este un timp polinomial probabilistic. Cum știe verificatorul dacă k este greșit um, deci înseamnă sau sau sau corect, deci ceea ce suntem? Încercarea de a face este ceva de genul știi, cum ar fi np, unde avem un certificat, dar acum avem acest tip de certificat interactiv sub formă de respingător, poate că acesta este un alt mod de a te uita la asta, unde dacă ești în limba ar trebui să existe ceva modalitate prin care probatorul să convingă să te facă să accepți, dar dacă nu ești în limba, nu ar trebui să existe nicio modalitate ca proverbul să te facă să accepți um uh, așa că verificatorul pur și simplu nu poate respinge imediat pentru că nu există nicio modalitate de a te convinge. spuneți de unde știe verificatorul că va începe să respingă lucrurile când nu ar trebui, dacă doar va respinge vrând-nevrând aici, bine, cum trebuie verificatorul să stabilească dacă probatorul este consecvent intern în loc să întrebe, așa că de ce nu verificatorul trebuie să determine dacă aprobatorul este consecvent intern în loc să pună doar întrebările de la pasul n plus unu, da, deci poate că asta se datorează faptului că se pare că toată munca se întâmplă la sfârșit, dar chiar îți prezint asta ca o pregătire pentru ceea ce vom face marți, deci este important să ne gândim la conexiunea de la fiecare pas la următorul, fiecare pas va fi justificat de ceea ce se întâmplă la pasul următor până ajungem la final, așa că trebuie doar să înțelegeți ceea ce este, nu încercați să îl faceți mai eficient, da, îmi dau seama că acesta este un lucru prost, um bun, nu folosim probabilismul aici și, în plus, nici măcar nu folosim interacțiunea aici dovatorul face tot ceea ce trimite verificatorul doar acceptă la sfârșit, da, asta este că nu folosim puterea și obținem un rezultat mai slab, așa că hai să mergem mai departe înainte să epuizăm timpul aici, așa că cum vom face remediați acest lucru, astfel încât problema este să arunce în aer fiecare pentru a justifica fiecare etapă în care fiecare valoare de care avem nevoie să prezentăm două valori care se adună la ea și asta e bine, ducând la o explozie acum, ar fi bine dacă putem face ceva în care fiecare valoare a fost susținută de o singură valoare la nivelul următor, așa că știm că aici este o idee pe care o știi bine pentru a înțelege pentru a vedea că acest număr total este corect de ce nu alegem la întâmplare fie zero sau unul și urmărește-l bine, problema în a face asta este pentru că secvența minciunilor ar putea fi doar o singură cale prin acest copac și șansele să găsești acea cale până la o contradicție la partea de jos este foarte scăzută dacă o faci doar la întâmplare um, așa că alegerea aleatorie a zerourilor și a unora, precum cea pe care o vei justifica, folosită pentru a justifica valoarea anterioară, nu va fi suficient de bună, deci ce, dar asta este ceea ce vom face, totuși, valorile pe care le vom alege pentru um pentru aceste intrări aleatorii um nu vor fi valori booleene, vom alege atribuiri non-booleene variabilelor care, din nou, la fel ca și în cazul cazul programului de ramificare nu a avut niciun sens la suprafață, va trebui să facem sens și va trebui să vedem cum să facem asta marți, în prelegerea de marți, bine, așa că este un fel de configurare ok. um da, deci, într-o întrebare similară, de ce este diferit de doar ghicirea nedeterministă a sarcinilor, din cauza asta, chiar pregătim scena în regulă, așa că ceea ce am făcut astăzi a fost că le-am prezentat modelul și am definit clasa de complexitate pe care o avem Îl putem arăta pe acesta în toată gloria. Am arătat că non-iso este un IP care merită să înțelegem acest protocol aici, asigurându-ne că vă simțiți confortabil cu asta și, de asemenea, cu modelul în sine și așa că pentru prelegerea de marți suntem Vom termina asta, ei bine, am început să arătăm acel număr setat ca un ip, ceea ce trebuie să facem pentru a dovedi că co-np este un ip și îl vom termina data viitoare, care va fi ultima dată în regulă, așa că asta e tot pentru azi voi rămâne pentru întrebări, așa că o întrebare bună aici de ce nu pot um v resping doar dacă unele dintre verificări sunt incorecte da v ar putea de îndată ce există o verificare care eșuează, putem respinge în acel stadiu, sunt încercând doar să argumentez că la un moment dat de-a lungul drumului, dacă intrarea nu este în limbă, va fi o verificare care eșuează, așa că vreau să spun că am spus respinge la sfârșit, dar da, vreau să spun că ai fi putut respinge în orice moment de-a lungul drumului um ok um um întreabă cineva ce rol am jucat, așa că mi-am făcut propriul meu rol personal în acest lucru, care a fost dublu în primul rând, mi-a venit ideea, ei bine, nu ideea pe care mi-am venit cu numele dovada interactiva uh imi amintesc cand Sylvia mccauley mi-a explicat asta in apartamentul meu cu multi multi ani in urma, el avea un pic cam complicat si nici nu-mi amintesc pentru ce era protocolul, nu era pentru ceva simplu era ceva ce implica uh numere prime și am spus oh, asta este un fel de dovadă interactivă și este și sa blocat din acel moment, deci asta a fost un lucru, dar celălalt lucru din punct de vedere mai matematic, rolul meu a fost atât de uh Shafi Goldwater și am aprobat echivalența celor două modele, versiunea monedă publică și versiunea privată, așa că acesta a fost rolul meu în acest spate și când totul a fost aprobat pentru prima dată, l- a aprobat într-un avion în drum spre o conferință undeva, așa că Cred că vom observa orice alte întrebări. Cred că vom pleca. Ai grijă toți să ne vedem marți la revedere.