bine, salut tuturor, vom începe, deci recapitulând ceea ce am făcut [Muzică] a în ultima prelegere de marți, am avut un fel de două este a doua parte a unei secvențe de două prelegeri despre teorema ierarhiei mai sus teoreme de ierarhie pentru timp și spațiu și utilizarea teoremelor de ierarhie pentru a arăta că există o problemă care este insolubilă care se poate dovedi în afara timpului polinomial și aceasta a fost această problemă de echivalență pentru expresiile regulate cu exponențiere și apoi am avut o scurtă discuție despre oracole. și posibilitatea ca metode similare să poată fi folosite pentru a arăta că satisfacabilitatea este în afara lui p, ceea ce ar rezolva, desigur, problema p versus mp și a susținut că pare puțin probabil ca acest tip de meta-teoremă să nu fie bine, uh bine. -noțiune definită, dar pare puțin probabil ca metodele care au fost folosite pentru a demonstra um uh insolubilitatea um echivalenței expresiilor regulate cu exponențiere ar putea fi utilizate pentru a rezolva p versus np cel puțin um um metoda de diagonalizare într-o formă pură, indiferent de asta înseamnă că nu va fi suficient, așa că astăzi vom schimba treptele din nou să începem un subiect oarecum diferit, care este într-adevăr un fel de a fi din nou câteva prelegeri despre calculul probabilistic, care vor încheia semestru pentru noi și vom începe prin a vorbi despre un model diferit de calcul care permite uh probabilism probabilism în măsurarea cantității de probabilism sau măsurarea probabilității permițând probabilism în calcul definiți o clasă de complexitate asociată uh această clasă bpp și apoi începem să începem discuția unui exemplu despre ceva numit programe de ramificare, bine um, ținând cont de asta, um uh um a uh, așa că vom începe prin a defini noțiunea de mașină de turing probabilistică sau ptm um a Mașina de turnare probabilistică seamănă foarte mult cu modul în care ne-am gândit la mașinile de turneu nedeterministe, prin aceea că este un fel de mașină care poate avea opțiuni multiple, mai multe moduri de parcurs în calculul său, astfel încât nu va fi doar o cale deterministă fixă. um din calculul său, dar va exista un arbore de posibilități um și pentru scopurile noastre vom limita ramificarea în acel arbore pentru a fi fie o etapă a calculului în care nu există ramificare în cazul în care este un pas determinist, uh, așa cum se arată aici, așa că fiecare pas duce în mod unic la pasul următor sau ar putea exista niște pași care au de ales și vom permite doar în aceste scopuri să păstrăm viața simplă, având doar o alegere între două posibilități și vom asocia cu asta noțiunea de probabilitate ca fiecare alegere să aibă o șansă de 50-50 de a fi luată, iar acest tip corespunde cu modul în care unii dintre noi sau unii dintre voi gândiți despre non-determinism, care nu este exact de sus și până în acest punct este că mașina ia un fel de ramură aleatorie, într-adevăr nu ne gândim la asta la întâmplare, până acum, ne vom gândi la mașină ca într-un fel de alegere aleatorie. dintre toate ramurile diferite pe care le-ar putea face și alegerea în mod uniform, aruncând o monedă de fiecare dată când are opțiunea spre ce drum să meargă, acum puteți defini, primesc o întrebare aici, uh, o mașinărie care are mai multe căi diferite până la mai mult de două căi de parcurs și atunci ar trebui să ai o monedă cu trei căi, o monedă cu patru căi și așa mai departe și le-ai putea defini tot așa, dar nu se termină. oferindu-ți ceva diferit sau ceva interesant sau nou pentru genul de lucruri pe care le vom discuta și va fi mai simplu să menținem discuția limitată la cazul în care mașina poate avea doar două posibilități, dacă va avea de ales sau doar o posibilitate când nu există nicio opțiune, bine, așa că acum va trebui să vorbim despre probabilitatea ca o mașină să ia o ramură sumară a calculului său, așa că vă imaginați aici aici este același arbore de calcul pe care l-am văzut anterior în cazul mașinilor obișnuite nedeterministe în care aveți m on w ar putea exista mai multe căi diferite de parcurs și ar putea exista o anumită ramură, dar acum vrem să vorbim despre probabilitate că mașina ajunge de fapt să aleagă acea ramură și va fi uh, știi, când vorbim despre mașina care are o alegere, o vom asocia cu o monedă, așa că vom suna că un pas de răsturnare a monedei atunci când aparatul are posibilitatea de a parcurge și așa mai departe o anumită ramură, probabilitatea ca acea ramură să se producă va fi unul peste doi la numărul de stări de răsturnare a monedei pe acea ramură și motivul pentru care Adică, aceasta este un fel de definiție care are sens, în sensul că, dacă vă imaginați că vă uitați la arborele de calcul aici și iată ramura pe care ne concentrăm pe care ne interesează de fiecare dată când este o monedă răsturnată pe acea ramură, există un 50 50 șansa de a lua o altă ramură sau de a rămâne pe acea ramură, astfel încât cu cât sunt mai multe aruncări de monede pe o anumită ramură, cu atât este mai puțin probabil ca ramura respectivă să fie cea pe care mașina de fapt ajunge să o ia și deci va fi una peste doi la numărul de aruncări de monede și așa o definim acum, odată ce avem această noțiune, putem vorbi și despre probabilitatea ca mașina să ajungă să accepte, deoarece fiecare, ca înainte, fiecare dintre aceste ramuri va ajunge la un starea de acceptare sau starea de respingere Mă gândesc la asta doar în termeni de decidenți și probabilitatea ca mașina să accepte aici va fi doar suma tuturor probabilităților ramurilor care ajung să accepte, așa că doar adună toate acele probabilități de o ramură care duce la o acceptare și vom numi că probabilitatea ca mașina să-și accepte intrarea [Muzică] și probabilitatea ca mașina să o respingă va fi de unu minus probabilitatea ca ea să accepte pentru că va merge la mașină um la fiecare ramură fie va face una, fie alta, bine acum, dacă vă gândiți la un anumit limbaj pe care mașina încearcă să decidă, această mașină probabilistică acum încearcă să decidă, știți despre fiecare intrare, unele dintre ramuri ale Este posibil ca mașina să nu dea răspunsul corect pe care îl vor accepta atunci când intrarea este în limbă, alte ramuri pot da răspunsul greșit, pot respinge atunci când intrarea este în limbă și invers, așa că va exista posibilitatea de a eroare acum în mașină într-o anumită ramură ar putea de fapt să dea un răspuns greșit și ceea ce vom spune este legată de eroarea la toate intrările posibile um și așa și uh vom spune că mașina pentru orice epsilon mai mare decât sau egal cu zero um vom spune că mașina decide limba cu probabilitate de eroare epsilon dacă acesta este cel mai rău care se poate întâmpla, știți dacă fiecare um pentru fiecare intrare mașina dă răspunsul greșit cu probabilitate de cel mult epsilon um echivalent dacă doriți să scrieți-l puțin mai mult, știți puțin diferit pentru șirurile care sunt în limbă, probabilitatea ca mașina să respingă acea intrare va fi de cel mult epsilon și pentru șirurile din limbă probabilitatea pentru șirurile care nu sunt în limba probabilitatea care acceptă este cea mai mare epsilon, așa că, din nou, aceasta este mașina care face lucrul pe care nu ar trebui să îl facă pentru lucruri în limba pe care ar trebui să le respingă foarte rar pentru lucruri care nu sunt în limba pe care ar trebui să le accepte foarte rar și asta este ceea ce această legătură este bine pentru tine, um [Muzică], așa că hai să vedem uh, așa că vom vorbi, așa că primesc câteva întrebări aici despre um um, așa că lasă-mă să mă uit la astea o secundă aici, da, deci probabilitatea zero, deci există o posibilitate pe care o are mașina ar putea avea o probabilitate zero de a accepta, ceea ce înseamnă că nu există ramuri care ajung să accepte sau probabilitate zero de a respinge nu au existat ramuri care resping, um, dar cred că vom vorbi într-un minut despre conexiune între asta și și noțiunea standard de np um, așa că așteaptă o secundă și despre ce se întâmplă cu știi um posibilitatea ca mașina să fie, știi că poți decide sau rula într-o anumită perioadă de timp um deci ne vom uita la mașinile delimitate în timp într-o secundă um pe următorul diapozitiv sau două um vorbind despre mașini care rulează în timp polinomial, așa că înseamnă că toate ramurile trebuie să se oprească într-un număr polinomial de pași um, așa că acolo mergem dar deocamdată ne uităm doar la părțile laterale în care mașina trebuie să țină pe fiecare ramură, dar unele ramuri ar putea funcționa mult timp, dar deocamdată nu ne vom gândi la mașinile care au ramuri care rulează um pentru totdeauna, unde toate mașinile noastre sunt decidenți, astfel încât să țină pe fiecare ramură, vezi că există altceva aici, nu, deci de ce nu merg mai departe, așa că hai să definim acum clasa bpp folosind această noțiune de mașină de turing probabilistică care va fi acum rulează în timp polinomial, deci bpp va fi o altă dintre aceste clase de complexitate, o colecție de limbaje precum p și np și p spațiu și așa mai departe și um, dar va fi acum asociat cu capacitățile acestor mașini probabilistice, tipurile de limbaje că ei pot face, vom spune că clasa bpp este setul de limbaje a, astfel încât există un timp polinom probabil în timpul mașinilor, astfel încât toate ramurile trebuie să se oprească în interiorul dvs., știți la k pentru niște k, deci un timp polinomial timp polinom probabilistic mașina decide o posibilitate de eroare de cel mult o treime, deci, cu alte cuvinte, atunci când acceptă pentru unii șiruri în limba pe care mașina trebuie să le respingă cu cel mult o treime, deci spunând echivalent pentru șiruri în limba cu care trebuie să accepte probabilitatea de două treimi și pentru șirurile care nu sunt în limbaj, trebuie să respingă ce probabilitate de două treimi, cel puțin în ambele cazuri, um, bine, cumva, nu mi-a verificat animația aici, dar bine, este bine, așa că există un um uh acum dacă te uiți la o treime aici în definiție, uh, știi, pare ciudat să definești o clasă de complexitate în termeni de o constantă arbitrară, cum ar fi o treime, de ce nu am folosit un sfert, știi, sau știi, o zecime în definiția bpp și spunem că mașina trebuie să obțină o eroare cu cel mult o zecime sau o sutime, ei bine, nu contează și acesta este scopul acestei afirmații următoare numită lema de amplificare care spune că poți oricând dacă aveți o mașină care rulează într-un anumit timp polinom care rulează în acest interval cu o anumită eroare, care este cel mai mult de jumătate, dacă aveți o eroare de jumătate, nu este interesant pentru că mașina ar putea arunca doar o monedă pentru fiecare uh intrare și ar putea obține uh răspunsul corect cu o probabilitate de jumătate, așa că probabilitatea de jumătate nu este interesantă, trebuie să aveți probabilitatea strict mai mică de jumătate pentru ca mașina să facă de fapt ceva semnificativ în ceea ce privește limbajul respectiv. um, dacă aveți o mașină de turnat probabilistică care are o eroare, să spunem epsilon unul care este cel mult o jumătate care este mai mică de jumătate, atunci puteți converti asta în orice probabilitate de eroare doriți pentru o altă mașină de turnare probabilistică în timp polinomial, astfel încât să puteți face acea eroare, care poate începe ca o treime și puteți reduce eroarea la una dintr- una sau căutați pe Google și, serios, puteți face eroarea extrem de mică folosind o procedură foarte simplă și asta este, așa că dacă Începeți cu o mașină care are o posibilitate de eroare de o treime, așa că înseamnă că două treimi din timp va primi răspunsul corect și cel mult o treime din timp cel puțin două treimi din timp răspunsul corect de cele mai multe ori într-o treime din cazuri este răspunsul incorect, indiferent dacă este acceptarea sau respingerea, și acum vrei să reducă răspunsul să fie ceva mult, acea eroare, la ceva mult mai mic, ideea este că doar ești o să iei acea mașină și o vei rula de mai multe ori, este un fel de rulări independente, dacă eu, dacă vrei să te gândești la asta, mai formal vorbind, dar este un fel de intuitiv, vei rula doar mașina îți aruncă monedele um uh în loc să-l pornești doar odată ce vei rula mașina de 100 de ori sau de un milion de ori, dar poți face asta, așa că este un factor constant și chiar și de o mie de ori va fi suficient pentru a crește încrederea ta în rezultat enorm, pentru că dacă rulezi mașina de o mie de ori și de 600 de ori mașina pe care o acceptă și de 400 de ori mașina o respinge este o dovadă foarte puternică că această mașină este părtinitoare să accepte că acceptă majoritatea din timp um deci este um a fost uh dacă a avut o probabilitate de eroare de cel mai mult o treime um uh, probabilitatea ca tu să o vezi, cu excepția de 600 de ori când într-adevăr de două treimi din timpul respinge este extrem de puțin probabilă um și poți calcula acel lucru pe care nu ne vom deranja să-l facem, dar este un calcul al probabilității de rutină pentru a arăta că este probabilitatea ca, dacă îl rulezi de mai multe ori și vezi că vine majoritatea, care nu este nu este răspunsul corect, probabil că este extrem de mică, așa că nu spun asta foarte clar, dar metoda aici este că vei lua mașina ta originală, care are probabilitatea de eroare de o treime sau oricare ar fi, orice ar fi, unii știi că știi că poate are o probabilitate de eroare 49 și îl rulezi de un număr mare de ori și apoi iei votul majoritar și cam eșantionezi rezultatele acestei mașini și dacă luați suficiente mostre, este foarte probabil că, deoarece doar le faceți uniform, luați acele mostre în mod uniform, este foarte probabil să o vedeți pe cea predominantă să apară mai des și exact care este valoarea corectă. Nu mă voi deranja să calculez, dar asta e ceva ce știi, dacă vrei, te voi trimite la manual sau știi că acesta este genul de lucru care apare în orice carte de probabilitate elementară și este un fel foarte intuitiv, așa că nu Nu vreau să-mi petrec timpul și să fac acel calcul, care nu este chiar atât de interesant, umh, bine, așa că doar o întrebare rapidă aici că am înțeles ce se întâmplă dacă legați dacă eroarea este mai mare de jumătate, nu cred că pentru că limităm eroarea, așa că nu spunem că eroarea este de fapt una pe care o cunoașteți ca șaizeci la sută din toate, deoarece atunci, dacă știați că eroarea este garantată, puteți întotdeauna să răsturnați răspunsul și să obțineți eroarea dvs. să ai 40 de ani, dar știi că eu spun că eroarea este că orice ar fi epsilonul și deci dacă spui că eroarea este de cel mult 60 la sută, nu-ți spune nimic, ok, um [Muzică] uh, altă întrebare lema de amplificare justifică, de asemenea, că alegerea modelului cu opțiuni binare de ramificare este echivalentă cu oricare altul. Poate ați putea spune că um, pentru că le puteți schimba pe cele pe care le cunoașteți dacă le-ați avut printr-o ramificare în trei căi um le puteți simula cu două - mod de ramificare la orice precizie pe care o vrei, știi că nu o vei coborî la zero, dar o vei ajunge foarte aproape, deci poate că este nivelul de amplificare, poate că este ceva legat de toate, bine, hai să mergem mai departe um, deci modul în care este util să ne gândim la această clasă, haideți să o contrastăm cu celălalt model de calcul nedeterminist pe care îl avem este non-determinism este np uh atât de nedeterminist, atunci modelul de calcul al timpului polinomial nedeterminist a fost np um cealaltă clasă și um, așa că, așa cum cred eu, o modalitate de a te gândi la non-determinism în cazul np este pentru șiruri în limbajul pentru mașina ta np turing, există cel puțin o ramură de acceptare, așa că sunt indicând cele care acceptă în verde și pe cea care nu acceptă ramurile care resping în roșu, așa că ați putea avea aproape toate ramurile să respingă ramuri um pentru șiruri în limba, atâta timp cât există cel puțin o ramură care acceptă, așa cum nu -determinismul funcționează, ramura care acceptă anulează toate celelalte, doar atunci când nu ești în limba în care se dovedește că toate ramurile trebuie să respingă, atunci cel care respinge știe că nu acceptă. ramură pentru a o anula, um, dar situația pentru bpp este puțin diferită, este diferită, um, există un fel de reguli majoritare, deci în cazul șirurilor în limba, trebuie să ai un mare sau știi că majoritatea covârșitoare dintre ramuri trebuie să accepte și pentru șiruri care nu sunt în limbaj, majoritatea covârșitoare trebuie să respingă ceea ce nu vei permite în cazul bpp este un fel de a cunoaște o stare intermediară în care este un fel de 50 -50 um sau foarte aproape de 50-50 um aceste tipuri de mașini nu sunt calificate ca uh hotărând o limbă în bpp, ele trebuie întotdeauna să se încline într-un fel sau să se încline în altul pentru fiecare intrare, altfel veți fi nu pot face amplificarea, așa că trebuie să am o anumită părtinire de la jumătate în acceptarea sau respingerea um, așa că lasă-mă, așa că aveam de gând să cer un check-in, cred că în acest moment da, să ne gândim doar la bpp i Sper că am fost clar, așa că dacă există întrebări despre asta, cred că nu am făcut-o cumva, nu sunt sigur că am descris-o foarte bine aici, așa că voi pune câteva întrebări despre ppp, dar dacă aveți întrebări pentru Mai întâi mergi înainte, um de ce nu facem doar check-in-ul, lasă-mă să lansez asta și apoi pot să răspund la întrebările pe care le întrebi dacă am început, da, bine, așa că trebuie să verifici toate astea pe care le ai cred că sunt adevărate um te poți gândi la mașini de turnare nedeterministe ca să încerci toate ramurile simultan și să obții răspunsul corect um și bp este ghici doar una sau ăă cred că doar o ramură nu știu um știi că aș spune a Puțin diferit, aș spune că m-aș gândi la non-determinism, deoarece puteți încerca doar o ramură, dar întotdeauna o ghiciți pe cea potrivită, um, așa că există un fel de putere magică pe care o cunoașteți, care vă permite să ghiciți întotdeauna răspunsul corect dacă există un corect ghici, uh, dacă sunteți în limba uh, în cazul bpp, veți alege o ramură aleatorie indiferent de ce și știți că ramura aleatoare este probabil să dea răspunsul corect, dar nu este garantat și implicația limita de amplificare vă spune că puteți aranja lucrurile astfel încât este extrem de probabil ca ramura aleatorie să vă dea răspunsul corect, bine, să vedem cum ne descurcăm la check-in-ul nostru, am primit o mulțime de voturi, avem un mult sprijin pentru toți candidații și vă voi acorda încă un pic de timp aici, deoarece există o grămadă de întrebări aproape de genul patru înregistrări simultan, dar mai avem două verificări reale care urmează. mai târziu, bine, de ce nu venim și hai să mai dăm încă 10 secunde și apoi o să încetez să închid unul, doi, trei, bine, deci avem mult sprijin aici și, de fapt, e bine pentru că toate sunt adevărate, unele dintre ele sunt mai ușor de văzut decât altele, așa că, în primul rând, este foarte ușor de văzut, pentru că asta va fi o mașină care are răspunsul corect tot timpul, așa că asta este probabilitatea de eroare zero um atât pentru acceptarea cât și pentru respingerea um, acest lucru este puțin mai greu d este puțin mai greu de văzut că este în spațiul p, dar știi că ai putea calcula pentru fiecare ramură um care este probabilitatea ei și poți doar să treci prin toate ramurile și adună toate acele probabilități într-o mașină cu spațiu p, așa că trebuie să te gândești puțin, dar d nu este prea greu să vezi nici închiderea sub complement dacă iei mașina ta bpp și răsturnești răspunsul pe fiecare ramură. um, asta de obicei nu funcționează în non-determinismul obișnuit nedeterminat, dar funcționează aici pentru că va schimba prejudecățile către acceptare într-o părtinire către respingere și invers, așa că bpp este închis sub compliment și închidere sub uniune. de la nivelul de amplificare, atâta timp cât puteți face probabilitatea extrem de mică, atunci puteți pur și simplu să rulați cele două mașini diferite și chiar dacă fiecare ar putea greși cumulativ, probabilitatea totală ca fiecare dintre ele să facă oricare dintre ele. a face o greșeală este încă mică și deci poți doar să alergi la cele două mașini și să iei sau din răspunsurile pe care le primesc și este încă foarte probabil să dea răspunsul corect pentru sindicat. O voi face acum pentru restul prelegerii și de fapt se va revărsa în prelegere după Ziua Recunoștinței, deoarece aceasta va introduce o metodă importantă pentru noi este să ne uităm la un exemplu de problemă care este în bpp um Îmi place să învăț lucruri folosind exemple și deci acesta este un exemplu foarte bun pentru că are multă carne și este un exemplu foarte interesant, în general, care demonstrează lucruri în bpp care nu sunt trivial acolo pentru că sunt deja în p ei tind să fie ceva mai implicați decât unii dintre ceilalți algoritmi pe care i-am văzut, așa că nu există exemple simple de probleme în bpp care nu sunt deja în p um, așa că acesta este un exemplu pe care îl vom merge printr-o problemă în bpp care nu este cunoscută de bnp, desigur, lucrurile s-ar putea prăbuși um, uh uh, ca stea, din câte știm, aceasta este um, această limbă nu este în p, așa că hai să vedem cu ce are de-a face limbajul aceste lucruri numite programe de ramificare programul de ramificare este o structură care arată astfel, așa că hai să înțelegem care sunt piesele, în primul rând, este un grafic direcționat pe grafic și nu suntem, nu vom permite și nu sunt permise cicluri în acest grafic este un grafic aciclic direcționat um, așa că nu puteți bucle permise, iar nodurile sunt în două categorii, există noduri de interogare care sunt etichetate cu o literă variabilă și noduri de ieșire care sunt etichetate fie zero, fie unul și, în sfârșit, există unul dintre nodurile de interogare vor fi sau unul dintre nodurile va fi desemnat ca un început bine și, deci, ceea ce faceți este modul în care acesta este un model de calcul și modul în care folosim de fapt un program de ramificare este că avem câteva alocarea variabilelor care va fi intrarea, astfel încât să luați toate variabilele, există trei variabile în acest caz um x1 x2 și x3 pe care le atribuiți le dați o atribuire de adevăr um deci x să spunem zerouri și una, deci x1 este zero x1 este unul sau orice altceva și odată ce ai atribuirea adevărului, începi cu variabila de pornire și tu și te uiți la eticheta acesteia și vezi ce valoare i-a atribuit intrarea acelei variabile, așa că dacă x1 a atribuit una, vei avea de gând să o urmați o ramură, dar atribuită la zero, urmați, mergeți în jos pe ramura zero și apoi, când ajungeți la următorul nod, aceasta este o altă variabilă pe care va trebui să o întrebați în funcție de ce este atribuirea de intrare și sunteți Voi continua acel proces pentru că nu există cicluri, veți ajunge la unul dintre nodurile de ieșire, deoarece toate nodurile variabile, toate nodurile de interogare au două margini de ieșire, una etichetată cu zero, una etichetată cu una, așa că sunteți va ajunge în cele din urmă la un nod de ieșire și asta va fi rezultatul programului de ramificare, așa că vom face, hai să facem un exemplu rapid, așa că dacă x1 este 1 x2 este 0 și x3 este 1. deci din nou începem de la început variabilă nodul de pornire care are indicat cu săgeata care vine de nicăieri, așa că veți începe de la x1 uh nodul etichetat x1, așa că trebuie să vă uitați și să vedeți ce este x1 în intrare este un 1. deci sunteți Vom urma o ramură acum vezi următorul nod oh, acesta este un x3 vezi ce este x3 în intrarea x3 este un 1. deci cobori din nou la o ramură, acum ai un nod x2, aruncă o privire la intrarea x2 este un zero, urmați ramura zero, acum vă aflați la un nod de ieșire a unei ramuri de ieșire, deci este un zero și acesta este rezultatul acestui calcul, deci scrieți-l în acest fel și gândindu-vă la ea ca o funcție booleană pe care o hărțiți. șiruri de zerouri și unu, avem f de unu zero unu reprezentând cei care atribuie acea atribuire care este egală cu zero, care a fost rezultatul și uh, acesta este rezultatul acestui calcul, bine, atât de important de înțeles că vom petrece mult timp. Știu că vorbim despre programe de ramificare, așa că este esențial să înțelegeți acest model, cred că este destul de simplu, dar dacă nu l-ați primit, vă rugăm să întrebați că putem corecta cu ușurință orice neînțelegere în acest moment, nu este exact la fel ca un DFA DFA pentru un singur lucru. luați intrări de orice lungime, asta are intrări de o anumită lungime, unde programul de ramificare are un număr fix de variabile, acesta are trei, deci acesta ia doar intrări de lungime trei, deci poate există o legătură cu gândirea acestor proprietăți și așa mai departe, dar este un model diferit, așa că acum vom spune că două programe de ramificare, bine, permiteți-mi să pun încă o întrebare, nu toate nodurile trebuie folosite corect, da, nu există nicio cerință ca toate nodurile să fie folosite și că chiar ar putea fi noduri inaccesibile. Nu împiedic asta, uh, asta ar putea fi în regulă, așa că, pe o anumită ramură, cu siguranță, nu vei ști când executați acest program de ramificare pe o intrare, evident că trebuie să aveți o cale care va folosi doar o parte din arborele din grafic, dar ar putea exista unele căi care nu pot apărea niciodată, știi, așa că dacă ai coborât x egal cu unu aici și apoi x trei a fost zero, acum recitești x unu, așa că Niciodată nu ai putea să nu mergi în această ramură decât dacă cred că toate ramurile din acest program de ramificare s-ar putea folosi, dar nu am verificat asta, așa că poate că greșesc, bine, așa că hai să continuăm două programe de ramificare. pot să calculeze sau nu aceeași funcție, um vom spune că sunt echivalente dacă fac acum două programe de ramificare pot fi echivalente chiar dacă superficial arată diferit unul de celălalt și suntem interesați de problema de calcul a două dintre acestea. programele de ramificare calculează aceeași funcție, cu alte cuvinte, dau întotdeauna același răspuns um la setarea intrării uh, așa că vom defini problema de echivalență a limbii asociată pentru programele de ramificare spune că vi se oferă două dintre acestea programe de ramificare și sunt echivalente să fie în limba pe care o vom scrie uneori echivalență folosind notația matematică a celor trei rânduri semnul egal semnul echivalenței bine, asta înseamnă că calculează la fel, dau întotdeauna același răspuns acum acea problemă se dovedește a fi cohen p complet, ți-am cerut să arăți în temei, cred că aceasta nu este o reducere foarte grea, este vorba de comp complet, apropo, este complementul unei probleme mp complete sau, echivalent, este o problemă să care toate problemele de conexiune sunt reductibile în timp polinomial și sunt în moneda [Muzică], așa că acesta este moneda p completă și asta trebuie să arătați, dar asta are o semnificație importantă pentru noi chiar acum, pentru că, dacă știți, uitați-vă la întrebarea dacă această problemă este în bpp, faptul că este coin co np complete sugerează că răspunsul este nu, deoarece dacă o problemă co np complete sau np complete mai mult în bpp, deoarece totul în np sau cmp este reductibil la acea problemă, atunci toate acele probleme np sau co-np ar fi în bpp din exact același motiv pe care l-am văzut înainte și nu se știe că este cazul și nu se crede că este cazul, deci nu ne așteptăm la un co -mp problema completă va fi în bpp um, asta ar fi, știți un rezultat uimitor uh și surprinzător uh uh, deci um, pentru că sper că am spus clar în um anterior, știți în discuția anterioară că cunoașteți bpp-ul din punct de vedere practic punctul de vedere este foarte aproape de a fi ca p um, deoarece puteți face ca probabilitatea de eroare a mașinii să fie atât de incredibil de scăzută încât să știți că este un comparabil uh, știți dacă rulați mașina și probabilitatea de eroare este ca una pe google um, atunci este sortare este chiar mai mare decât probabilitatea ca o particulă alfa să intre și să inverseze valoarea unei celule de memorie internă din dvs. în calculul dvs., așa că dacă aveți o probabilitate de eroare extrem de scăzută, este destul de bine din punct de vedere practic, așa că ar fi uimitor dacă problemele np au fost rezolvabile în bpp um, deci acesta nu este limbajul pe care îl vom folosi ca exemplu, ne vom uita la o versiune restrânsă a acestei probleme despre echivalența pentru programele de ramificare și pe care o voi introduce chiar acum bine orice întrebări aici nu văd nicio întrebare, um dispare uh ok um, deci hai să trecem mai departe, așa că vom vorbi despre programe de ramificare care sunt ceea ce se numesc programe de ramificare citite odată citite o dată și acestea sunt pur și simplu programe de ramificare care nu au voie să recitească o intrare pe care au citit-o anterior, deci, de exemplu, acest program de ramificare este un program de ramificare citit o dată nu, acest program de ramificare nu este un program de ramificare citită o dată, deoarece puteți găsi o cale care vă va provoca pentru a citi aceeași variabilă de mai multe ori, așa că nu va fi o citire o dată um, aici, să nu citim o dată pentru că există două apariții ale unui x1 pe aceeași ramură, acum ați putea să vă întrebați de ce ar vrea cineva să facă asta pentru că dvs." Am citit deja valoarea lui x1 bine, vreau să spun că în cazul acestui anumit program de ramificare ar putea exista o valoare, deoarece ați fi putut ajunge la această ramură x x1 mergând în acest fel sau în acela, um, dar aceasta este o întrebare separată dacă ne limităm. atenție să citiți o dată programele de ramificare, atunci problema testării echivalenței devine foarte diferită în caracter și, de fapt, vom oferi un algoritm probabilist uh un algoritm bpp pentru a rezolva problema respectivă, astfel încât problema echivalenței pentru programele de ramificare citite o dată care nu sunt permis să recitesc variabile pe orice cale, care va fi interesant de rezolvat cu un algoritm de timp polinomial probabilistic, pe care îl știi, cu o mică probabilitate de eroare, așa că o să fac o verificare acum, dar hai să ne asigurăm că suntem cu toții Împreună despre asta, așa că am o întrebare bună aici, dacă fiecare funcție booleană poate fi descrisă de un program de ramificare? Nu e greu să-ți arăt alte întrebări, suntem cu toții împreună pentru a înțelege ce înseamnă citit o dată și a ramifica programele și toate chestiile astea, acesta este un moment bun pentru a te întreba dacă nu ești bine, așa că hai să facem check-in-ul așa cum am subliniat vom arăta că echivalența pentru programele de ramificare citire o dată este rezolvabilă în bpp. Putem folosi asta pentru a rezolva cazul general al programelor de ramificare prin conversia programelor de ramificare generală a ramurilor în programele de ramificare a ramurilor citite o dată și apoi rulați testul de citire o dată, deci ce faceți? cred că bine, văd o mulțime de răspunsuri corecte aici, așa că haideți să-l încheiem pe acesta rapid încă 10 secunde, vă rog bine, gata suntem toți gata unul doi trei închidem bine da majoritatea dintre voi ați răspuns corect, bine răspunsul a nu este un răspuns foarte bun, deoarece am comentat deja la slide-ul anterior că nu știm cum să facem cazul general în bpp, așa că ar fi oarecum surprinzător dacă chiar aici spun că da, am putea face acest lucru prin folosind cazul restricționat, astfel încât să știți, cred că un răspuns mai bun ar fi la unul dintre nu, dar așa cum am comentat, puteți oricând converti puteți face oricând orice funcție booleană uh cu un puț, poate nu am spus-o pentru a citi o dată programe de ramificare, dar citești chiar și o dată, programele de ramificare pot face orice calculă orice funcție booleană um, așa că conversia este posibilă, dar în general nu va fi timp polinomial și poți, dacă îți imaginezi că ai încercat să faci conversia aici, ai putea convertiți acest program de ramificare pentru a citi o dată um, dar va trebui practic să separați cele două uh um, pe care le știți, în loc să recitiți x1, vă puteți aminti acea valoare x1, dar atunci nu ați fi, nu ați putea reconverge aici. d trebuie să păstreze acele două acele două fire ale acelor două ramuri ale calculului depărtate acele două căi unul de celălalt și deja programul de ramificare ar începe să crească în dimensiune făcând asta um și um, astfel încât în ​​general conversia este posibilă, dar necesită o extindere mare, o creștere mare a dimensiunii și atunci nu vom mai permite un algoritm de timp polinomial nici măcar în cazul probabilistic în cazul probabilistic um ok um așa că acum să începem să ne uităm la posibilitatea de a arăta că această problemă de echivalență este rezolvabilă în bpp și ne va duce într- o direcție ciudată, dar haideți să încercăm să ne pornim mai întâi intuiția făcând ceva care pare a fi cea mai evidentă abordare evidentă, așa că aici, așa că vom da un algoritm acum. care va fi o încercare, nu va funcționa, dar cu toate acestea va avea germenul ideii corecte sau germenul sau nu, dar începutul modului corect de a gândi la asta, așa că iată cele două ramificații citite o dată programele de ramificare sunt b1 și b2 și vreau să văd dacă calculează aceeași funcție sau nu, așa că un lucru pe care ați putea încerca este să le rulați pe o grămadă de sarcini sau intrări selectate aleatoriu, așa că veți putea um luați două atribuții de intrare aleatorii, doar luați x1 aruncați o monedă pentru a spune că este una dintre zero x faceți același lucru pentru x doi și așa mai departe um, apoi obțineți o atribuire de intrare, rulați cele două programe de ramificare pentru acea sarcină și poate că nu. să știi, chiar dacă sunt de acord, nu îți oferă prea multă încredere că ai răspunsul corect, că sunt cu adevărat echivalenti, așa că o faci de o sută de ori, de câteva ori, și bineînțeles, dacă ei uh nu sunteți de acord vreodată cu privire la o anumită misiune pe una dintre aceste sarcini, atunci știți că nu sunt echivalente și puteți respinge imediat, dar ceea ce aș vrea să spun este că dacă sunt de acord cu cele pe care le cunoașteți o sută de încercări acele sute de sarcini acolo, atunci acolo ele sunt umh, cel puțin, nu am găsit un loc în care să nu fie de acord, așa că voi spune că sunt echivalente este că un lucru rezonabil să faci bine ar putea fi uh, depinde de k um, deci lucru critic este ce valoare a lui k ar trebui să alegeți, care va fi suficient de mare pentru a ne permite să tragem concluzia că, dacă o rulați de k ori și nu vedeți niciodată o diferență, atunci puteți concluziona cu încredere că cele două programe de ramificare sunt echivalente pentru că ați încercat să căutați o diferență și nu ați găsit niciodată una bine, lucrul este că um k va trebui să fie destul de mare uh, așa că uitându-vă în acest fel, dacă cele două programe de ramificare erau echivalente, atunci cu siguranță ele Vom da întotdeauna aceeași valoare, um, așa că probabilitatea ca mașina să accepte va fi una și asta este bine pentru că vrem că acesta este un caz în care suntem în limba în care vrem ca probabilitatea de acceptare să fie mare și aici probabilitatea de acceptare este de fapt una, așa că va accepta întotdeauna când cele două programe de ramificare au fost echivalente, dar ce se întâmplă când programele de ramificare nu sunt echivalente acum dorim ca probabilitatea de respingere să fie mare, probabilitatea de acceptare ar trebui să fie foarte mică bine, deci dacă nu sunt echivalente, vrem că probabilitatea ca mașina să respingă va fi mare dacă nu sunt echivalente, deoarece asta este răspunsul corect, singurul mod în care mașina va respinge dacă găsește um, un loc în care cele două programe de ramificare nu sunt de acord, dar acele două programe de ramificare, deși nu sunt echivalente, s- ar putea să nu fie de acord rar, s-ar putea să nu fie de acord doar cu o atribuire de intrare din cele două posibilități finale, astfel încât aceste două programe de ramificare inechivalente ar putea fi de acord aproape peste tot, cu excepția într-un singur loc și atunci este suficient pentru ca ei să nu fie echivalenti, dar problema este că, dacă veți face doar eșantionare aleatorie, probabilitatea de a găsi acel loc excepțional în care cei doi nu sunt de acord este foarte scăzută, veți avea să faci un număr enorm de eșantioane înainte de a fi probabil să găsești acel punct de diferență și așa, pentru a fi încrezător că vei găsi acea diferență dacă există una la care mergi pentru a trebui să faceți exponențial multe mostre și nu aveți timp să faceți asta cu un algoritm de timp polinomial, um, va trebui doar să aruncați prea multe monede, trebuie să rulați prea multe mostre diferite, atribuiri diferite prin aceste două mașini și pentru că aproape că sunt diferiți, dar sunt aproape la fel, așa că va trebui să găsim o metodă diferită și ideea este că vom rula aceste două programe de ramificare într-un mod nebun. în loc să le rulăm pe zerouri și pe cele pe care le-am fost, am făcut-o până acum, vom introduce valori pentru variabilele care nu sunt booleene, pe care le vor seta x1 la 2 x3 la 7 x 4 la 15. bineînțeles că nu pare să aibă niciun sens, dar totuși se va dovedi a fi util un lucru util de făcut și ne va oferi o perspectivă asupra echivalenței sau echivalenței acestor programe de ramificare. bine, deci haideți să cred că suntem la sfârșit, da, suntem la pauză aici, așa că de ce nu primesc câteva întrebări, ceea ce este grozav, voi răspunde la acele întrebări, dar de ce nu încep la pauza noastră și apoi um ok bine, așa că există o întrebare despre dacă aceste mașini rulează determinist sau nu, deci despre ce mașină vorbim, așa că programele de ramificare în sine pe care le-ar rula determinist le dați o misiune um la variabilele de intrare care vor determina o cale prin fiecare program de ramificare, care în cele din urmă va scoate un zero sau unul și doriți să știți dacă acele două programe de ramificare dau întotdeauna aceeași valoare, indiferent de intrarea, dar programele de ramificare în sine au fost determinist, acum, mașina care încearcă să determine dacă acele două programe de ramificare sunt echivalente, acea mașină pe care o vom argumenta va fi o mașină probabilistă, deci este un fel de mașină nedeterministă care va avea diferite modalități posibile de urmat, în funcție de rezultat, dacă este vorba de aruncarea de monede, așa că te poți gândi ca non-determinist, cunoști non-determinismul în sensul obișnuit despre cum are un arbore de posibilități, dar acum știi calea Ne gândim că acceptarea este diferită, știi că, în loc să acceptăm, dacă există o singură ramură acceptă, mașina pentru ca aceasta să accepte trebuie să aibă ca majoritatea ramurilor să accepte și știi, așa că există unele asemănări, dar unele diferențe cu modul obișnuit în care ne gândim la non-determinism, deci care este motivația din spatele introducerii acestui tip de mașină de tors bine, vreau să spun că sunt multe, cred că există două motivații, algoritmi probabilistici numiți uneori algoritmi monte carlo um uh se dovedesc a fi folositori în practică, pentru o varietate de lucruri și asta i-a determinat pe oameni să se gândească la ele în contextul complexității, sunt legate în anumite moduri de computerele cuantice, care sunt, de asemenea, probabilistice într-un mod oarecum diferit, dar au și o formulare foarte frumoasă um uh um uh în teoria complexității, așa că teoreticienilor complexității le place să se gândească la calculul probabilistic, deoarece vreau să spun că poți face lucruri interesante cu mașinile probabilistice și clasele de complexitate asociate sunt de asemenea interesante, așa că, după cum vei vedea, ne conduce într-un direcție interesantă, uh, să luăm în considerare cum să rezolvăm această problemă. Echivalența problemei programului de ramificare odată citită o dată cu o mașină probabilistă este doar un algoritm um interesant pe care îl vom găsi, um, așa că în încercarea noastră de demonstrație, unde am folosit natura probabilistică pentru bpp, deoarece rulăm cele două programe de ramificare pe o intrare aleatorie, um, vreau să spun, așa că știi că aveți cele două programe de ramificare, alegeți o intrare aleatorie pentru a rula acele două programe de ramificare și vedeți ce fac ele acolo este acolo unde este de ce este probabilist atunci când te gândești la comportamentul aleatoriu al mașinii, este o mașină probabilistică, așa că fiecare ramură a mașinii va fi așa cum ne gândim în mod normal la non-determinism, cineva întreabă dacă ne gândim la complexitatea mașina în ceea ce privește toate ramurile mașinii sau fiecare ramură separat, la care ne gândim întotdeauna pentru mașinile nedeterministe, fiecare ramură separat um, nu sunt complet sigur că înțeleg întrebarea de acolo, deci toate intrările sunt încorporate și alegem la întâmplare una prin răsturnări de monede, nu sunt sigur că înțeleg această întrebare, fie ni se dau ca intrare cele două programe de ramificare și apoi răsturnăm monede, știți cum folosind non-determinismul nostru, vă puteți gândi la echivalent în termeni de răsturnări de monede. alegeți valorile variabilelor, așa că acum avem un set de intrări variabile la valorile variabilelor și le folosim ca intrare în programele de ramificare pentru a vedea ce dacă ei să vedem ce răspunsuri dau și noi, în special, dacă acestea dați același răspuns la acea intrare aleasă aleatoriu, hai să mergem mai departe, bine, așa că acum ne mutăm spre algoritmul bpp real pentru uh, citiți odată testarea echivalenței programului de ramificare, trebuie să ne gândim la un mod diferit de a avea nevoie. un mod alternativ de a gândi despre calcularea unui program de ramificare va arăta foarte asemănător, dar ne va conduce într-o direcție care ne va permite să vorbim despre asta, aceste intrări non-booleene la care mă refer, doar un fel de unde mergem, vom simula programele de ramificare cu polinoame, dacă asta vă ajută într-un fel ca un plan general, dar vom ajunge acolo puțin încet, așa că bine iată un program de ramificare citit o dată programul de ramificare um noi Nu o să folosim funcția de citire o dată, uh, încă, dar asta va veni mai târziu, dar oricum aici este un program de ramificare um și um uh oh, aici este ramura mea și am pus blocat aici, începem din nou, bine, așa că luăm un introduceți um orice ar fi um și gândindu-vă la calculul procesului de ramificare, așa că nu ne gândim la algoritm chiar acum, ci doar ne gândim la programele de ramificare pentru momentul în care vom reveni la algoritm mai târziu, așa că programul de ramificare urmează o cale așa cum am indicat atunci când aveți o anumită intrare, x1 dvs. este 0 x2 este 1 x3 este 1, așa că rezultatul va fi 1 în acest caz, bine, așa că modul în care vreau să mă gândesc la asta puțin diferit este eu vreau să etichetez toate nodurile și toate marginile cu o valoare care să-mi spună dacă această cale galbenă a trecut sau nu prin acel nod sau margine, va fi doar o procedură similară, dar s- ar putea să crezi că nu este deloc diferență dar vreau să etichetez toate lucrurile de pe calea galbenă pe care le voi eticheta sau pe unul și toate lucrurile care nu sunt pe calea galbenă pe care le voi eticheta cu un zero, așa că sunt menținându-i pe cei care încearcă să păstreze acele etichete în afara programului de ramificare original, care sunt scrise în alb, aceste etichete sunt scrise galben, dar aceste etichete au legătură cu execuția programului de ramificare pe o intrare, așa că odată ce am o intrare care va determina o una sau o etichetă zero pentru fiecare nod și margine acum, dacă vrem să ne uităm la ieșirea din acest program de ramificare după ce avem acea etichetare, trebuie să ne uităm doar la eticheta unui singur nod de ieșire, deoarece asta este dacă acesta are o etichetă. asta înseamnă că calea a trecut prin aceea și, prin urmare, ar trebui să ieșim de ieșire uh, ieșirea este una um uh, așa că vă voi oferi o altă modalitate de a-l atribui, în loc să găsim calea mai întâi și apoi să vină în sus cu etichetarea după aceea, vă voi oferi o modalitate diferită de a veni cu acel tip de etichetare, construindu-l inductiv începând de la nodul de pornire și construind acea etichetare, veți vedea ce vreau să spun prin exemplul meu, așa că dacă am o etichetă pe acest nod, așa că știu deja dacă calea a trecut sau nu prin acel nod, știți eticheta 1 înseamnă că calea a trecut prin ea eticheta 0 înseamnă calea nu trece, nu trece prin ea [Muzică] care îmi va spune cum să etichetez cele două margini de ieșire, așa că dacă sunt dacă am etichetat deja acest lucru cu un unde a este un zero sau unu, atunci ce expresie ar trebui să folosesc um la cum fac în ce circumstanțe voi eticheta ce este ceea ce este corect etichetați pentru această margine de ieșire bine aici, dacă a este zero, înseamnă că perechea pe care știm că calea nu a trecut prin acest nod, deci nu există nicio modalitate de a trece prin acea margine în mod similar, dacă x i este un zero, ceea ce înseamnă că chiar dacă am trecut prin această margine. acel nod, calea ar trece prin cealaltă margine, cealaltă margine de ieșire și nu către aceasta, astfel încât aceasta ne spune că expresia booleană care descrie valoarea etichetei acestui nod uh în execuție va fi și a valorii de pe nodul și um variabila de interogare a acelui nod acum gândiți-vă care este modalitatea corectă de a eticheta cealaltă margine, valoarea de execuție a celeilalte margini din nou, trebuie să treceți prin acest nod, așa că trebuie să fie unul, dar acum doriți x i să fie 0 pentru a trece prin acea margine, așa că înseamnă că va fi a și complementul lui x i bine, așa că asta îmi va spune doar că scriu o formulă pentru cum etichetăm aceste margini. pe baza etichetei nodului părinte, în mod similar, dacă am o grămadă de margini în care știu deja valorile etichetele uh nivelurile de execuție acolo să spunem că am a1 a2 și a3 care este eticheta potrivită pentru a pune acest nod ei bine, dacă oricare dintre acestea este unul, înseamnă că calea a trecut prin acea margine și, prin urmare, va trece prin acel nod, astfel încât să ne spună că eticheta de pus pe acel nod este sau a etichetelor de pe marginile de intrare bine întrebări despre asta, așa că acum, acesta este un fel de a pregăti scena pentru a începe să te gândești la asta, um, mai mult la polinoame, în loc să folosești o algebră booleană, așa că mă întreb cum știm care este calea de execuție care noduri să etichetați vom eticheta toate nodurile, așa că începem cu etichetarea uh am spus că aici ar trebui să pornim nu am spus, dar ar trebui să etichetăm nodul de pornire cu unul care, deoarece calea trece întotdeauna prin nodul de pornire, așa că fără să vorbim măcar despre o cale, etichetăm doar nodul de pornire 1. Poate vom face și un exemplu în acest sens, dar acum, odată ce etichetăm această stea, acest nod 1, avem o expresie care ne spune cum pentru a eticheta cele două de ieșire um cele două margini de ieșire această margine și acea margine um și o fac fără să știu valorile variabilelor o fac cam eu fac doar o expresie uh care va descrie ce acele etichete ar fi odată ce îmi spuneți care este alocarea de intrare în regulă, așa că sunt cam ca o execuție simbolică aici, doar scriu diferitele expresii pentru cum să calculez care ar trebui să fie aceste lucruri, hai să mă lăsați um, poate că acest lucru va deveni mai clar pe măsură ce continuăm, așa că sondajul acum, aceasta este ideea mare a acestei dovezi, um, vom folosi ceva numit aritmetizare pe care o vom transforma de la gândirea la lucruri din lumea booleană la a gândi la lucruri în lumea aritmetică în care avem aritmetică peste numere întregi să spunem deocamdată um, așa că în loc de ands și ors vom vorbi despre plusuri și timpi um și uh vom merge la felul în care vom face puntea este episcop, arătând cum să simuleze ands și ors mâna și sau operațiile cu operațiunile plus și times um deci um presupunând că unul înseamnă adevărat și zero înseamnă fals dacă aveți expresia a și b ca expresie booleană, putem reprezenta asta ca a ori b folosind aritmetica pentru că um are, calculează exact aceeași valoare atunci când avem um reprezentarea booleană a adevăratului și a falsului uh fiind unu și zero, așa că știi că unu și unu este unu și o dată unu este unul și orice altceva știi unu și zero zero și unul zero și zero dacă dacă ați aplicat operatorul timpi, veți obține aceeași valoare, așa că timpii seamănă foarte mult și, în acest sens, bine, o vom scrie ca doar un b, de obicei, fără simbol de timp, deci dacă avem un complement, cum l-am simula din nou cu aritmetica bine, aici doar răsturnăm unu și zero folosind operația de complement, care va fi la fel cu scăderea valorii dintr-una care o inversează și de la uh între unu și zero um ce zici sau dacă ai a sau b ei bine, este puțin mai complicat pentru că folosești un plus b um, dar trebuie să scazi din produs pentru că ceea ce vrei este că această simulare ar trebui să- ți dea exact aceeași valoare Deci, dacă ai unul sau unul, vrei să fie un răspuns unu la unu, nu vrei să fie un doi, așa că trebuie să scazi din produs, um uh, iar scopul este să ai o simulare fidelă a și și sau folosind plus și ori, astfel încât să obțineți exact aceleași răspunsuri atunci când introduceți valori booleene aici, bine, așa că doar pentru a spune unde mergem, ce va ajunge asta, știți că sună că nu am făcut-o superficial. am făcut ceva, dar ceea ce ne va permite să facem este să conectăm valori care nu sunt booleene pentru că știi că nu are sens să vorbești despre asta, are sens să vorbim despre unu și zero, dar nu are sens. nu are sens să vorbesc despre doi și trei, dar vorbește, are sens să vorbesc despre două ori trei și asta va fi un lucru util, bine, așa că hai să vedem, să ne amintim că procedura de etichetare inductivă pe care am descris-o înainte. unde am etichetat a dat etichetele de execuție pe margini, în funcție de eticheta nodului părinte și de ce nod care variabilă este interogată, um, așa că dacă știu că această valoare este un a, dar acum e bine, așa că o să scriu doar acest lucru în jos folosind uh aritmetică în loc de a folosi operații booleene uh uh, așa că înainte de a avea acest lucru a fost un a și x i dacă vă amintiți din diapozitivul anterior, acum ce vom folosi în schimb, deoarece vom folosi această conversie aici. de și vom folosi înmulțirea care este doar o dată x i, ceea ce despre această parte aici a fost a și complementul lui x i acum complementul lui x i este unu minus x i în uh aritmetic, deci acesta devine ori unul minus x i bine um în mod similar, aici am făcut sau pentru a obține eticheta pe nod de la etichetele marginilor sale de intrare, acum vom face ceva puțin ciudat, um, pentru că avem o formulă aici pentru sau, dar din motive tehnice care vor apărea mai târziu aceasta nu este o reprezentare convenabilă pentru noi, ceea ce voi folosi în loc de aceasta, voi spune pur și simplu doar luați suma de ce este suficient de bună în acest caz, aceasta va fi încă o reprezentare fidelă și va oferi răspunsul corect tot timpul și asta pentru că pentru programele noastre de ramificare citite o dată sau citite o dată nu vine încă pentru programele noastre de ramificare sunt ciclice, așa că nu pot intra niciodată într-un nod pe două căi diferite, există cel mult o singură cale. a intra într-un nod uh um pe o cale printr-o cale de execuție prin programul de ramificare dacă intră prin uh până la această margine um, nu există nicio modalitate ca această margine să aibă și o cale, deoarece asta înseamnă că aveți să ieși și să te întorci și să ai un ciclu în programul de ramificare care este interzis, astfel încât cel mult una dintre aceste margini poate avea calea să treacă prin ea, astfel încât cel mult unul dintre acești a poate fi unul, celelalte vor fi zero și, prin urmare, doar luarea sumei ne va da o valoare fie 0, fie 1, dar nu va da niciodată o valoare mai mare și, prin urmare, nu trebuie să scădeți din acești termeni de produs, bine, puțin complicat aici dacă ați făcut-o. nu înțeleg pe deplin, nu-ți face griji deocamdată, știi că suntem mai îngrijorați că ai o imagine de ansamblu a ceea ce se întâmplă, bine, așa că cred că suntem aproape, lasă-mă să văd cât de departe suntem da, așa că voi lucra doar printr-un exemplu și cred că asta ne va aduce uh, hai să vedem orice întrebări aici, fără să văd niciuna, înseamnă că fie sunteți pe deplin înțelegătoare, fie că sunteți total pierdut, nu pot niciodată spune- mi, așa că nu ezita să pui o întrebare dacă ești chiar dacă ești confuz, știi că voi face tot posibilul, bine, poate acest exemplu ar putea ajuta, așa că acum ceea ce vom face este să folosim acest tip de aritmetică vedere a modului în care calculul programului de ramificare, știi că este executat atunci când îl rulăm, știi o intrare prin el, asta ne va permite acum să dăm un sens rulării programului de ramificare pe intrări non-booleene deci poate că acest exemplu va ilustra acest lucru, um, deci să luăm acest program de ramificare special, bine um, acest program de ramificare este doar pe două variabile x1 și x2 și calculează de fapt o funcție familiară, aceasta este exclusivitatea sau funcția dacă te uiți la el pentru un minut. veți vedea că acest lucru vă va oferi x1 exclusiv sau x2, așa că va fi unul dacă oricare dintre x1 sau x2 sunt unul, dar va fi zero dacă ambele sunt una, asta este ceea ce acest program de ramificare calculează acum, dar să aruncăm o privire la rularea acestui program de ramificare în loc de valorile booleene obișnuite să-l rulăm pe x1 egal cu 2 și x2 egal cu 3. faceți interogarea x1 pe care o căutați pentru o altă margine de ieșire care este etichetată cu două nu, nu asta fac ceea ce fac aici este că sunt cumva prin această execuție prin alocarea acestor alte valori pe care le cam amestec împreună, calculul lui x x uh 1 egal cu 0 și x1 egal cu 1 împreună, nu știu dacă are vreun sens, dar hai să ne uităm prin exemplu, așa că în primul rând acestea sunt regulile de etichetare pe care le-am avut din diapozitivul anterior când am folosit plus și ori în loc de și sau bine, acum o să vă arăt cum să le folosiți pentru a eticheta nodurile și marginile acestui grafic pe baza acestei intrări și asta va determina o ieșire ar fi valoarea pe uh un singur nod este bine, așa că începem întotdeauna prin a eticheta nodul de pornire cu unul care este doar regula um și uh, bine, îmi pare rău, hai să ne gândim împreună înainte de a scoate răspunsul care va fi eticheta de pe această margine, așa că aceasta este una a muchiilor de ieșire uh de la un nod care are deja o etichetă, așa că acesta va fi cazul aici și ceea ce facem este dacă luăm eticheta acelui nod și, deoarece este o singură margine care iese, înmulțim acea etichetă cu um valoarea uh acea uh variabilă a atribuirii acelei variabile, deci x1 este două, deci luăm la este bine aceasta a aici este unul x1 este alocat la doi, deci va fi de o ori două va fi valorează valoarea de execuție pe care o punem pe această margine, deci va fi 2. care va fi valoarea pe care o punem pe cealaltă margine, cealaltă margine, marginea de ieșire 0 de la x1, așa că odată te gândești la asta pentru o secundă, așa că acum vom" Vom folosi această expresie este un ori 1 minus x i și deci x i din nou este doi, deci unul minus x i este unul minus doi um asta înseamnă că așa este complementar, dar bine să spunem asta, deci este un minus 2, deci este minus 1 ori eticheta 1 aici, astfel încât să obțineți minus 1 ca etichetă de pe această margine, acum rețineți că dacă m-aș fi conectat și acest lucru este foarte important dacă aș fi introdus valori booleene aici, aș obține aceleași valori booleene pe care le-ați obține doar urmând calea, știi că lucrurile de pe cale ar fi unul, lucrurile de pe cale ar fi zero, dar uh, dar cu ce fel de uh, ceea ce se întâmplă aici este că există încă o semnificație când intrările nu sunt booleene, așa că hai să continuăm iată ce va fi valoarea pe acest nod, așa că gândește-te cu mine, cred că te va ajuta, așa că acum folosim această regulă aici adunăm toate valorile de pe marginile de intrare, există doar o margine de intrare care este valoarea doi deci asta înseamnă că acest tip va primi un doi și similar pe acesta, acest tip va primi un minus unul acum, să aruncăm o privire la această margine, deci aceasta este o margine de ieșire zero dintr- o etichetă de nod doi cu eticheta x2, deci aceasta este marginea de ieșire zero nodul eticheta este două, deci va fi de două ori una minus valoarea x2 x2 este 3, deci 1 minus 3 este minus 2. va fi de 2 ori -2 care este minus 4. pot obține valoarea de aici valoarea de pe marginea de ieșire va fi de 2 ori x valoarea x2, care este 3, deci va fi 6. și acestea două aici uh um, așa că știți că acum avem un minus unu și ieșire este a este a este o margine zero, deci este unu minus trei și aici va fi o dată minus trei nu de 1 ori 3 îmi pare rău de 1 ori 3. um, așa că ați scos răspunsul este minus 3. deci acum care este eticheta de pe marginea de ieșire zero, așa că trebuie să adăugați și să adăugați cele două margini de intrare aici, așa că avem uh, această margine aici a fost două, această margine care vine aici este șase, deci va fi două plus șase, este opt și ce zici de această margine, acest nod aici, acesta este un nod important, deoarece acesta va fi ieșirea, așa că are um uh, știi că vin minus trei și vin minus patru, așa că le aduni împreună, obții minus șapte, adică s-ar putea să vă întrebați ce se întâmplă lumea aici, doar o mulțime de mumbo jumbo uh, dar vom înțelege toate astea nu astăzi, uh, va trebui să ne certăm de ce acesta este sensul pe care îl vom avea scăpați de asta va fi um, dar ideea este că acest lucru va duce la un nou algoritm pentru testarea, ceea ce înseamnă a reveni din nou la ceea ce făceam, aceasta este problema echivalenței pentru programele de ramificare citite o dată, deci acum ce este nou algoritmul pe care îl va face va alege o atribuire aleatorie non-booleană, așa că va atribui aleatoriu valori pentru x și pentru unele valori non-booleene în loc de zerouri și cele pe care le vom introduce valori întregi aleatoare. clarificați data viitoare care este ceea ce va fi domeniul um [Muzică] și apoi, odată ce avem acea atribuire non-booleană, vom evalua b1 și b2 și dacă nu sunt de acord acolo în acel domeniu extins, atunci vom trebuie să arătăm că nu sunt echivalente și vor respinge și vom arăta, de asemenea, că, dacă au fost echivalente, atunci chiar și atunci când le evaluăm, trebuie să arătăm că, dacă nu sunt echivalente, este foarte probabil să o facă. au o diferență în domeniul non-boolean uh și deci dacă sunt de acord, vă oferă dovezi că cele două sunt într-adevăr echivalente, um, așa că dovada completității va veni după Ziua Recunoștinței, așa că, um, vă urez tuturor un frumos uh break um oh avem un check-in aici. Îmi pare rău, oh, da, acesta este unul bun, nu știu cum dacă mă urmărești, uh, dar dacă conectez unul pentru x1 și y pentru x2 face intrările atribuirea trebuie să fie distinctă, nu ar putea fi aceeași valoare, aș putea fi două și două aici, care este perfect valid, dar aici voi conecta 1 pentru x1, voi introduce o variabilă pentru x2 y și i Voi face tot calculul pe care tocmai l-am făcut și acum care va fi rezultatul și vreau să spun că asta arată ca o durere să-mi dau seama că ai putea să-l faci, arată ca o durere, dar permiteți-mă să vă dau un indiciu important, amintește-ți că acest lucru ar trebui să calculeze programul de ramificare original calculează exclusivitatea sau funcția și asta înseamnă că atunci când conectez o valoare booleană ar trebui să iasă exclusiv sau valoarea, așa că dacă știu deja că x1 este unul dintre acestea. în concordanță cu obținerea unei valori pe care exclusivitatea sau funcția ar fi calculată, așa că permiteți-mi să lansez sondajul, astfel încât să fim la un moment dat, așa că să lăsăm asta să ruleze încă 10 secunde, bine, o voi închide gata, da, într-adevăr a este răspunsul corect, deoarece acesta este unul dacă știu că o variabilă este una, atunci exclusivă sau va fi complementul celeilalte variabile, care este unul minus y, așa că asta ați obține dacă ați calcula acest lucru um, deoarece acesta este ceea ce am făcut-o astăzi și nu ezitați să puneți întrebări, așa că permiteți-mă doar ca să cheltuim o bucată bună, voi revizui ceea ce am făcut până acum, dar apoi o vom continua și vom cheltui o bună parte. o bucată din prelegerea de marți după pauza de Ziua Recunoștinței, demonstrând că această procedură la care tocmai m-am abonat a funcționat și funcționează și este o dovadă interesantă, dar oarecum știi că nu este o dovadă atât de ușoară, așa că vom încerca să o facem încet și clar și apoi um, dar această noțiune de aritmetizare va fi aceasta este aceasta a fost știi că este o noțiune importantă în complexitate și, deci, o vom vedea din nou venind într-o altă demonstrație după aceea în despre dovezile interactive sisteme bine, deci vă rugăm să puneți întrebări, astfel încât rezultatul să fie valoarea unei stări de ieșire, da, asta a fost o întrebare, am primit alte întrebări pe care cineva le spune minus șapte nu este xor-ul doi și trei care este xor-ul doi și trei, deci prin în felul în care ar trebui să spun că am cam scurtat timp, nu spun că am descoperit un adevăr fundamental nou despre xor aici, pentru că ar fi bizar, depinde cu adevărat de decizia arbitrară pe care am luat-o să spunem că adevărat este unul. și fals este zero, am fi putut veni cu o reprezentare diferită pentru adevărat și fals și atunci ai obține o valoare diferită pentru xor care rezultă din ceea ce știi din aritmetizarea pe care tocmai am descris-o, dar pentru acest mod special de a reprezenta adevăratul și fals, așa este xor și acest program de ramificare, așa cum evaluează xor restul dovezii, așa că cineva întreabă care este adevărata teorema fundamentală a algebrei care vorbește despre polinoame și numărul de rădăcini pe care le poți avea asta va fi, va fi critic, um uh, deci asta este teorema fundamentală a algebrei acolo unde mergem. Bună întrebare bună, știi bine, așa că cineva se plânge că știi că nu luăm reprezentarea binară cu cifre a două și trei și luând puțin câte puțin um xor, ei bine, nu sunt, știi că reprezentarea binară nu face parte din asta, ne gândim la acestea ca la două elemente ale unui câmp um unui câmp finit despre care vom vorbi mai târziu reprezintă reprezentarea binară este nu este nu este nu intră în această discuție, um, așa că vorbiți despre de ce doar a face suma este suficient um cred că a fost așadar de ce este, vreau să spun aici, de ce face doar suma atunci când eu" Mă uit la um, cum să descriem valoarea acestui nod pe baza valorilor tuturor nodurilor de intrare și să ne amintim că punctul de plecare al acestuia este că trebuie să reprezentăm fidel logica booleană cu aritmetica și apoi vom Vom folosi asta și o vom extinde la valori non-booleene, dar ca punct de plecare trebuie să reprezentăm cu fidelitate valorile booleene acum, valorile booleene de pe marginile de intrare, cel mult una dintre ele poate fi una, deoarece cele corespund la marginile căii de execuție și nu puteți face o cale de execuție, um, care va avea două ramuri care vor trece printr-un nod de două ori pentru că atunci aveți o buclă și nu avem, nu sunt cicluri permise, bine, așa că eu Gândește-te unde este la patru, vreau să-mi iau rămas bun de la toți. Să aveți o săptămână minunată și ne vedem când vă întoarceți