bine bun venit la toți, așa că suntem aici astăzi, cursul numărul 21, uh, venim în partea de start a cursului, uh, aș spune că, probabil, ultimul trimestru al cursului este puțin mai tehnic, uh, poate deci puțin mai abstract unele dintre teoreme vor fi mai dificile, așa că voi încerca să le rezolv încet și voi răspunde la întrebările dvs., dar știți că cred că vă puteți aștepta să găsească materialul ceva mai provocator pe măsură ce noi a început uh um [Muzică] uh așa cum am început um um știi cu uh această teoremă data trecută uh uh uh spațiul log nedeterminist fiind închis sub complement, așa că nl este egal cu colonel, am cam ajuns doar o parte, poate o treime din drum Deci, o să o iau de la capăt și o să petrec cam prima jumătate a prelegerii de astăzi vorbind despre asta și apoi vom vorbi despre teoremele ierarhiei, care sunt foarte importante, umh, aspectul complexității peisajului, practic ele. să vă spun că, dacă vă permiteți să cunoașteți modelul dvs. preferat, să spunem că mașinile de transformare au mai multe resurse, atunci pot face mai multe lucruri, dar vom ajunge la asta în timp util, așa că hai să revenim la memento-ul pentru mine înapoi la immerman celeb cheney uh, adică nl este egal cu conl um, așa cum am menționat, acestea vor fi aceleași diapozitive ca data trecută și voi încerca doar să le parcurg încet, sper că sper că sper Sper că ai înțeles, dar dacă nu știi, întreabă-mă la întrebările ta, așa că mai întâi o să mă refer la i, lucrul pe care îl vom arăta este că complementul de cale este rezolvabil în spațiul de jurnal nedeterminist, știm deja că calea poate fi rezolvată în nl, ceea ce este ușor de făcut, practic, începeți de la nodul de pornire și ghiciți secvența de noduri care stochează doar nodul curent în memoria de lucru din spațiul dvs. de jurnal în memoria dvs. banda de lucru bazată pe jurnalele dvs. ghiciți secvența de noduri pe diferite ramuri ale non-determinismului și dacă ajungeți vreodată la nodul țintă t, atunci puteți accepta um, dar cum poate o mașină de spațiu de jurnal nedeterministă să cunoască sau să accepte complementul de cale, așa că ar trebui să accepte atunci când nu există cale și asta este mult mai greu, dar este o mare surpriză pentru comunitatea de complexitate că este adevărat, așa cum am discutat ultima dată despre care vom vorbi calcularea funcțiilor cu o mașină nedeterministă și care se dovedește a fi un mod convenabil de a privi acest lucru, așa că vom avea mașini nedeterministe care au diferite ramuri ale non-determinismului lor, știți pe o anumită intrare și sunt ar trebui să calculeze o valoare a funcției pe care o știți că rămâne pe bandă, dar din cauza non-determinismului, nu vă puteți imagina că diferite ramuri ar putea avea funcții diferite, ceea ce nu este permis, toate ramurile trebuie fie să raporteze valoarea funcției um pe care o avem. Încerc să calculeze sau pot, practic, pot să respingă și să spună bine, știi uh i i știi că este un practic nu știu, așa că toate filialele trebuie fie să raporteze răspunsul corect, fie pot spune că nu știu și unele ramura trebuie să raporteze cel puțin o ramură un răspuns trebuie să raporteze răspunsul pentru um și asta înseamnă să calculezi o funcție cu o mașină nedeterministă și vom arăta că anumite funcții pot fi calculate cu un log nedeterminist mașinile spațiale, în special această funcție de cale care încorporează atât pozitivul, cât și negativul perechii, atât atunci când există o cale, cât și când există o cale, nu este o cale în funcție, deoarece funcția trebuie să răspundă da atunci când există o cale. cale de la s la t și nu atunci când nu există o cale de la s la t bine, așa că dacă ai putea face asta, ai terminat pentru că poți face un non-determinist, ai putea face o mașină nl, așa că dacă ai putea calcula funcția cale ai putea face o mașină nl care ar accepta ori de câte ori funcția spune nu um și celelalte cazuri pe care le cunoști și dacă mașina um care calculează funcția uh respinge, atunci vei respinge și tu, dar accepți dacă funcția spune nu și deci, veți face o mașină nl care face complementul problemei căii, așa că știți dacă puteți calcula funcția căii care ar fi grozavă, așa că asta am dori să putem face ca Am menționat că vom avea alte două valori care vor fi relevante pentru calcularea funcției cale, ceea ce vom face în cele din urmă și acesta va fi numărul de noduri pe care le puteți ajunge de la început. de la nodul de pornire din graficul dvs. și apoi pentru r este colecția de noduri și c este numărul de noduri accesibile um așa se arată în această imagine și aici sunt dacă vă este util să o vedeți într-un mod mai forma este că te poți gândi la r ca o funcție a graficului și a nodului de pornire, desigur, dar uneori îl vom numi doar r, știi când este clar despre care grafic și nod de pornire vorbim r este setul de noduri accesibile deci este colecția u astfel încât răspunsul este da și c este dimensiunea r ok, așa că modul în care vom începe este o teoremă ușor, deși aceasta va fi încă relevantă la sfârșit, dar pentru acum este mai mult o practică cu conceptul pe care l-am venit, știți acest concept de funcție pe care tocmai l-am introdus, așa că vreau să spun că funcția cale cu o mașină nl, apoi pot calcula numărul uh cu o mașină nl bine deci înțelegeți ce înseamnă calcularea funcției cale că aveți mașina dvs. nl și fiecare ramură trebuie să spună fie că nu știu care este respingere, fie trebuie să aibă răspunsul care va fi da dacă există o cale și știu dacă nu există o cale și dacă pot să pot număra numărul de noduri care au o cale numărul de note pentru care răspunsul este da și asta cred că dacă ești confortabil cu definiția aceasta este [Muzică ] mai mult sau mai puțin evident pentru că ceea ce ați face este să treceți prin nodurile lui g unul câte unul și să testați uh folosind funcția de cale uh care este răspunsul da sau nu și de fiecare dată când este un da, adăugați unul la numărare până ați trecut prin toate nodurile și apoi aveți răspunsul dvs. care sunt noduri care sunt c acum, dacă mașina care încearcă să calculeze funcția de cale pe non-determinism respinge că este în regulă, veți calcula c acea ramură va respinge de asemenea, dar atunci când ești, o ramură trebuie să obțină răspunsul corect pe uh, știi că trebuie să obțină răspunsul corect și apoi obții știi că știi ce se întâmplă cu acel nod și atunci tu um poate fie să crească numărul, fie să treci la următorul nod. Cred că încerc să spun că nu sunt sigur dacă clarific ceva repetându-mă, dar bine aici, așa că vei începe cu vi se oferă graficul și nodul de pornire, încercăm să calculăm această valoare c care este numărul reîncărcabil de la nodul de pornire cu care începeți aveți un contor pe care îl veți seta inițial la zero și treci prin fiecare nod al graficului și dacă calculul funcției cale spune da, poți să ajungi la tine, atunci adaugi unul la numărătoare, spune că nu, nu poți ajunge la tine, atunci continui și poate ar trebui să adaug o altă linie aici dacă știi dacă lucrul care calculează uh respinge, atunci respingi și tu și apoi, la sfârșit, scoți um, așa că ceea ce o să dovedim este cealaltă direcție, dacă îți dau numărul, atunci pot răspunde întrebarea pentru fiecare nod dacă este accesibil sau nu și acesta este lucrul pentru că ceea ce spune este că vă pot da numărătoarea am terminat dacă putem obține acea numărătoare care va fi suficientă, bine, deci poate chiar înainte de verificare - Poate ar trebui să răspundem la orice întrebare pentru că știi dacă dacă ești blocat aici, atunci ești condamnat, așa că cred că tu ești, are sens să încerci să înțelegi ce se întâmplă la asta, pentru că cred că Adevăratul curaj al acestei dovezi apare pe următorul diapozitiv, sunt un fel de idee principală, așa că sunt bucuros să accept dacă există întrebări despre asta, voi aștepta doar o secundă pentru a vedea dacă ești tastând acolo bine, de ce nu mergem la check-in, poate că asta ne va ajuta la un check-in foarte dificil, um, va veni bine, doar puțină practică cu conceptul, așa că voi da tu un grafic are nouă noduri um și vreau să știu valoarea numărului um, așa că vom presupune că este nodul de pornire aici este accesibil de la sine și acum care este valoarea lui c bine, bine o să închidem aceasta jos vă oferă încă două secunde, vă rugăm să primiți răspunsul în bine, uh, gata setat, da, răspunsul corect este de fapt uh e, adică șase, există șase noduri accesibile în acest grafic și asta ar trebui să vă spună valoarea c este cum La multe noduri pot ajunge de la e bine și ceea ce spun este că dacă pot calcula asta în acest sens de funcție nedeterministă, așa că, dacă este așa, unele ramuri pot obține acel răspuns, um, atunci pot folosi asta pentru a testa fiecare nod, indiferent dacă este sau nu accesibil, ceea ce este un fel de miracol, ceea ce este un fel de surprinzător, doar că știind câte noduri sunt accesibile, îmi va permite să testez dacă fiecare nod individual este accesibil, pentru că nu există un motiv evident pentru care ar fi fi, așa că va exista o procedură pentru a face ceea ce este pe următorul diapozitiv și aici este în regulă, deci aceasta este ideea cheie pe care o vom repeta mai târziu, dar este bine să înțelegem asta este asta este diapozitivul pe care trebuie să îl înțelegeți, bine, așa că mi se dă graficul, să presupunem că graficul are m noduri acum, așa cum am spus, bine, deci hai să spunem ce facem aici, având în vedere acest număr, putem calcula calea, așa că vom" Voi primi răspunsul pentru fiecare nod din grafic dacă știu doar câți știți, așa că voi ști că pot obține răspunsul pentru care dacă un nod este accesibil sau nu, dacă am doar dacă știu câte noduri accesibile acolo sunt um, ceea ce o să fac este să obțin numărul acela de câți sunt accesibile acum, o să trec prin um o să merg pentru că hai să vedem care este ideea aici înainte de a trece chiar în algoritmul ideea este să presupunem că știu câte noduri sunt accesibile, cum ar fi 100 de noduri accesibile acum, ceea ce o să fac algoritmul este să găsească toate sutele de noduri accesibile, care sunt unul câte unul, dar nu contează. conceptual, va găsi toate nodurile accesibile și le va ghici nedeterminist, așa că nu este sigur dinainte care sunt, dar va ghici practic o sută, nu, va ghici că unele dintre noduri sunt accesibile confirmă faptul că cele acei oaspeți accesibili sunt accesibili și apoi verificați pentru a vedea că acel număr este egal cu 100. pe o ramură a non-determinismului veți ghici corect și veți ajunge cu exact setul potrivit de 100 de noduri accesibile și apoi veți vedea nu este unul dintre acele sute de noduri accesibile, caz în care spui da sau nu este unul dintre acele sute de noduri și atunci știi că răspunsul este nu, pentru că dacă ai ghicit o sută de noduri și știi că acestea" sunt toate accesibile și știți că există exact 100 de noduri accesibile, atunci fiecare alt nod nu este accesibil, așa că acesta este spiritul și asta o să scriu asta aici mai departe în algoritm, mă mai auziți băieți. cineva a spus că sunetul meu este ca și cum ar fi sclipitor. Primesc un semn sau două de internet instabil, așa că știi dacă dacă ai nevoie să repet ceva, doar trimite-mi o notă, mulțumesc bine, bine, așa de bine, uh, poate ar trebui vorbiți încet dacă nu trece prea bine, bine, așa că ceea ce vom face este să mâncăm toate nodurile graficului unul câte unul și să ghicim dacă este un nod accesibil sau nu un nod accesibil dacă presupunem că este accesibil, voi ghici, de asemenea, calea care arată că este accesibilă și apoi voi ține un număr de câte noduri accesibile am găsit dacă numărul este de acord cu valoarea c um am început, atunci i Știu că le-am găsit pe toate și dacă nu este unul dintre ele, atunci știu că nu este accesibil, aceasta este ideea în regulă, așa că iată a mea, acesta va fi o contorizare a numărului de noduri pe care le-am găsit care sunt accesibile, um, asta este k acum aici merg, voi alege nedeterminist dacă este un nod accesibil sau nu, tocmai l-am numit două ramuri ale algoritmului ramura p sau ramura n p înseamnă că există o cale și n înseamnă că nu există cale deci, dacă am ghicit p în acest moment pentru acest nod u, deci parcurg fiecare dintre noduri unul câte unul și u este nodul curent dacă am ghicit că are o cale de la s, atunci i Voi ghici acea cale pentru a mă asigura că este într-adevăr o notă accesibilă, um, dacă nu reușesc să găsesc o cale, atunci aceasta este una dintre ramurile non-determinismului care va eșua, va eșua. spuneți că nu știu sub această ramură, um, pentru că fie ați ghicit greșit și acest nod nu a fost accesibil, fie dacă a fost accesibil, ați ghicit că nu ați reușit să găsiți o cale care să vă arate că este accesibilă, a existat o cale, dar nu ați găsit-o. ghicește-l pe cel potrivit, oricum ai făcut o alegere proastă, o să o faci acum, dacă ai stabilit că nodul pe care tocmai l-ai arătat este accesibil pentru că în acest stadiu nu ai eșuat așa că ai reușit să arăți o cale către um, apoi um uh și u este egal cu t, atunci știi că t este accesibil, deci există o cale de la s la t și ai terminat că știi că ai răspunsul pe care îl cauți pentru și acum puteți spune da, altfel, dacă t este ceva dacă sunteți alt nod, atunci puteți doar să creșteți numărul de noduri accesibile pe care le-ați găsit ok, astfel încât ați găsit un nod accesibil dacă este t. grozav, ai terminat, dacă nu ești doar să includă asta în contul tău de noduri accesibile, um acum, dacă ai ghicit că nodul nu este accesibil, bine, atunci continuă, știi că nu vei fi doar Voi trece la următoarea notă pentru că cauți o colecție de note accesibile, bine, am câteva întrebări aici, dar lasă-mă să aștept până la sfârșit, acum, după ce am terminat de parcurs toate nodurile, așa că Am terminat cu această buclă de a trece prin toate nodurile, acum văd, am găsit c noduri accesibile, deoarece k este numărul nodurilor pe care le-am găsit a fi accesibile dacă este de acord cu c, atunci i Știu că le-am găsit pe toate dacă diferă de c, atunci ceva a mers prost pentru că mi s-a spus că există c noduri accesibile și nu am găsit noduri c accesibile, așa că am făcut o ghicire proastă pe parcurs, cred că un nod care este într-adevăr accesibil. Presupun că nu a fost accesibil, așa că nu le-am găsit pe toate, o să pun um, dar dacă le-am găsit pe toate și așa și și nu am ajuns să accept, nu a spus da în acest stadiu, așa că nu a fost unul dintre cei pe care i-am găsit un accesibil, apoi eu, uh, sunt convins că nu este unul dintre cei care sunt accesibili, care nu a fost unul dintre acele noduri c pe care le-am găsit care sunt accesibile și acum pot spune nu, bine, așa că hai Lasă-mă să pun întrebări aici, pentru că cred că da, acesta este sfârșitul acestui diapozitiv, acesta este genul de o piesă importantă pentru a înțelege că putem petrece câteva minute încercând să rezolvăm asta, așa că cineva întreabă cum alege nedeterminist o cale eșuează dacă eșuezi um ceea ce vreau să spun este să alegi o cale de la s la u, așa că trebuie să mergi de la s la oricare ar fi nodul tău actual u, așa că vei alege o cale către tine Cred că ești accesibil acum, trebuie să demonstrezi că este accesibil, alegând o cale de la s la tine dacă nu ajungi la u um și perechea pe care nu vrei să mergi pentru totdeauna pe orice ramură, așa că vei limita la m pași calea ta trebuie să fie de cel mult m, așa că după m pași, dacă nu ai ajuns la tine până în acel moment, ai ales o cale proastă și vei respinge um ok uh ok deci care este diferența dintre cunoașteți și respingeți, este o întrebare bună, respingerea în acest caz este o nu știu că algoritmul nu a putut face o determinare pe baza presupunerilor că este făcută în această ramură nedeterministă a algoritmului, a făcut alegeri proaste, ceea ce nu nu îi permit să ajungă la o concluzie într-un fel sau altul, bine amintiți-vă că acest algoritm aici calculează o funcție acum, nu este un algoritm determinist în sensul recunoașterii limbajului, acesta este un computer cu funcție și deci trebuie să obțină răspunsul la funcția cale care este un da sau nu sau nu știu despre unele ramuri sau unele ramuri care au voie să facă și asta, așa că nu și respingerea sunt total diferite um ok bine, acesta este același lucru despre care am vorbit ultima dată de ce avem nevoie două ramuri pentru p și n um dacă vom avea doar o propunere doar pentru a avea ramura p bine, dar unele noduri nu sunt accesibile dacă o să cauți dacă o să știi dacă ai un nod inaccesibil deci nu este un r, nu poți ajunge la acel nod din s, trebuie să sări peste acea notă pentru că încerci să găsești un subset al nodurilor accesibile, așa că încerci să alegi acel subset aici, o notă la o notă. deci, dacă veți permite doar lucruri, veți avea nevoie de totul în acest subset, vor exista unele noduri care nu sunt accesibile și nu veți găsi o cale pentru că nu sunt accesibile și dvs. O să sfârșești prin a proiecta tot timpul pe care îl știi pe acel nod, așa că vei fi așa, algoritmul va nu va funcționa nu va funcționa um ok, așa că nu sunt sigur că înțeleg această întrebare aici, dar cineva spune dacă t este accesibil, scoatem da pe acea ramură, dar nu scoatem și nu pe o altă ramură, haideți, e bine, să vedem ce se întâmplă dacă t este de fapt accesibil. ramura care va ieși da, suntem cu toții de acord cu asta, cel puțin dacă urmărești, suntem de acord, dar cum ar putea o altă ramură ieșire nu dacă t este de fapt accesibil pentru că aceasta este o întrebare grozavă și nu, asta nu se va întâmpla dacă t este de fapt accesibil cum ar putea o ramură să scoată nu um [ Muzică], asta trebuie să însemne că nu ghicește ca unul dintre nodurile accesibile, deoarece trece prin toate nodurile de aici, știi că va ajunge la toate nodurile și le alege ca accesibil sau nu dacă alege t este unul dintre cele accesibile, atunci va afișa da, deoarece va descoperi că știi că fie va ieși da, fie dacă nu găsește corect nu ghicește calea corectă. sfârșește prin a respinge acel uh pe acea cale, dar o cale va sfârși prin a spune da, deci dacă este accesibil și dacă ghiciți dacă știți că este accesibil și ghiciți că știți că ghiciți că ești accesibil în momentul în care u este egal cu t, veți sfârși prin a scoate s singurul mod în care nu ați putea să nu scoateți da este dacă ghiciți că acel nod este inaccesibil, dar atunci numărul dvs. nu se va aduna corect, deoarece nu ați fi găsit-o nu ați găsit toate cele accesibile noduri dacă t este unul dintre nodurile accesibile și știți că există 100 de noduri accesibile și ați sărit peste t ca unul dintre cele despre care spuneți că este inaccesibil, în cel mai bun caz, puteți găsi doar 99 de noduri accesibile și nu veți termina spunând nu, o să sfârșești prin a proiecta, deci este o întrebare foarte bună, dar trebuie să te gândești la ce se va întâmpla aici, asta e asta, este un fel de verificare, este aproape ca și cum ai ști bine, este ca o sumă de control. dacă știi ce este, așa că se asigură că tot ceea ce trebuie să vezi dacă ai dacă dacă k este egal cu c în acest moment înseamnă că ai găsit de fapt toate nodurile accesibile, așa că c este un fel de verificare că am găsit toate nodurile accesibile um corect, așa că, dacă k este egal cu c în acest moment, ați găsit fiecare nod accesibil și dacă t a fost unul dintre cele care sunt accesibile, ați găsit că uh bine, să vedem că um este motivul pentru care facem acest lucru cu c în esență așa că știm și putem înceta să ghicim și să identificăm corect dacă este imposibil să ajungem bine, nu este o chestiune de asta, nu este o chestiune de a înceta să ghicim, este este o verificare prin care am găsit totul pentru că o să trecem și facem toate ghiciturile pentru fiecare nod indiferent de ce, așa că nu vom opri nimic mai devreme decât dacă descoperim că t este accesibil, atunci ne putem opri devreme, dar dacă pentru a arăta că t nu este accesibil, trebuie să parcurgem întregul proces, um, cum putem vedea intuitiv că nu avem ramuri contradictorii, așa cum încercam să spun că acum nu știu, sper că a trecut prin tu nu poți avea ramuri contradictorii pentru că dacă ai ajuns în acest stadiu aici ați găsit toate nodurile accesibile, așa că în această etapă, dacă ați ajuns la șase, ați făcut toate presupunerile corecte, ați găsit toate nodurile accesibile, v- ați convins că toate sunt accesibile, ghicind perechile cu ele și ai verificat că ai numărul corect de noduri accesibile pentru că este egal cu c, așa că trebuie să le fi găsit pe toate, așa că nu poți avea un răspuns contradictoriu pentru că fie t a fost unul dintre cele pe care le-ai găsit, caz în care ai fi spus deja da sau altfel le-ai găsit pe toate și nu a fost unul dintre ei și așa vei spune nu, nu poți avea ambele lucruri nu se pot întâmpla, bine hai să mergem mai departe, așa că următorul lucru pe care îl vom face este următorul diapozitivul este exact același cu acest diapozitiv, cu excepția faptului că în loc să spun că nu este accesibil, vreau să știu dacă este accesibil în d, dar la distanță, bine, deci, ceea ce va însemna exact aceeași procedură, pot obține în loc să întreb pot Obțin um um uh de la s la t cu o cale de orice lungime, desigur, va fi cea mai lungă m acum vreau să știu pot ajunge la ea de la s la t printr-o cale de cea mai mare lungime d acestea sunt numărul de muchii în cale spune um și uh, este aceeași procedură pentru că în loc de eu doar voi tăia lucrurile la un d, dar dacă i dacă știu dinainte câte noduri sunt accesibile în d um, voi găsi toate nodurile care sunt accesibile în d și c au fost unul dintre cele accesibile în d este aceeași idee exactă, așa că aici este următorul diapozitiv care arată că uh, aici iată definițiile calea sub d înseamnă accesibil printr-o cale de lungimea celor mai multe bine, deci um r sub d sunt toate cele care sunt accesibile printr- o cale de acea lungime și c sub d este numărul este un număr care poate fi atins uh în d um, așa că dacă ați înțeles ultimul diapozitiv, sperăm că asta slide-ul vi se va părea destul de evident, voi evidenția toate modificările, așa că, dacă acum pot calcula c sub d, care este numărul accesibil printr- o cale de cel mult lungimea d, atunci pot testa dacă nodurile sunt sau nu accesibile de către o cale fără lungime mai întâi calculez c sub d i merg aleg fiecare nod ca fiind accesibil în d sau nu acum trebuie doar să verific dacă calea mea pe care presupun că are o lungime de cel mult d în loc de lungimea de cel mult m, care este ceea ce aveam înainte ține o numărătoare a celor pe care le-am găsit dacă numărul este egal cu c sub d atunci știu că le-am găsit pe toate dacă nu este egal cu c sub d atunci am făcut o alegere proastă pe parcurs și pot pur și simplu pune și spune că nu știu și dacă nu a fost unul dintre cei despre care am demonstrat că sunt accesibili în d, atunci știu că nu este accesibil în d și deci pot spune nu, bine, așa că o fac Nu știu dacă merită întrebări suplimentare, dar asta este într-adevăr același, este doar o repetare a diapozitivului anterior, ceea ce este uimitor este acum, ultimul diapozitiv va fi din nou o repetare. mergem, dar nu ezitați să puneți o întrebare pe acest diapozitiv sau pe primul diapozitiv dacă nu ați primit-o pe diapozitivul anterior, dacă nu ați primit asta, um, de asemenea, putem încerca să vă ajutăm cu asta um următorul diapozitiv ce Voi face este să arăt cum să calculez toate aceste valori c și ar trebui să menționez um valoarea c, care este numărul total accesibil, va fi aceeași cu c sub m accesibil cu un m numărul de noduri ale graficului deci, dacă pot ajunge până la c sub m am terminat um și ceea ce o să-ți arăt este că știind c sub i pot să calculez c sub i plus unu sau c sub d pot să calculez c sub d plus unu din moment ce i Folosesc d ca index aici, practic, așa că c sub zero știm că este foarte bine, știi că este doar unul pentru că poți citi doar începe cu s, acesta este singurul lucru accesibil cu zero și apoi, odată ce știu că pot să-mi dau seama out c sub 1 c sub 2 c sub 3 și așa mai departe și apoi primesc c sub n și apoi am numărul total care poate fi atins și apoi pot testa funcția de cale um ok, așa că trucul acum este să pot numără uh dat c sub d aș dori să-mi dau seama ce este c sub d plus unu acum, cum voi face că ceea ce voi face este scopul meu, ceea ce voi face este ceva între i' voi face o teoremă exact ca aceasta, dar în loc să dau c sub d în loc să calculez căile lui d, voi calcula căile lui d plus 1. așa că știind câte sunt accesibile de la d, voi da un test pentru că lucrurile sunt accesibile în d plus unu și adevărul este că este ușor, deoarece acest lucru îmi spune deja cum să calculez dacă sunt accesibil în d plus unu și faptul că pot fi accesibil din interiorul d plus unu înseamnă că am un avantaj de la ceva care este accesibil în d, deci dacă pot să-mi dau seama care sunt accesibile în d și vreau doar să spun dacă am o margine, știi uh, am o margine de la unul dintre nodurile care sunt accesibile în d, atunci sunt accesibil în d plus unu, atunci dacă pot testa dacă nodurile individuale sunt accesibile în d plus unu, pot număra câte noduri sunt accesibile în d plus unu, care a fost prima teoremă ușoară pe care am arătat-o, așa că știu că există o mulțime de piese aici care trebuie să puneți cap la cap, dar în cele din urmă fiecare p fiecare piesă individuală nu este chiar atât de rea, bine, nu știu câți dintre voi m-ați urmărit, oh, nu, asta nu ar trebui să fie aici, uh, mergem așa că aici este ultimul parte care din nou este doar o simplă modificare a ceea ce avea diapozitivul anterior, așa că voi arăta cum să calculez calea d plus funcția 1, astfel încât să testez dacă există o cale de lungime d plus 1 de la s la un nod t, dar numai știind câte noduri sunt accesibile în d, așa că voi găsi toate nodurile care sunt accesibile în d la fel cum am făcut înainte, dar văd dacă vreunul dintre aceste noduri are o margine la t, nu neapărat că unul este egal cu t, deoarece asta spune că t este accesibil în d, dar vreau să știu dacă are o margine la t, ceea ce înseamnă că t este accesibil în d plus unu, așa că dacă găsesc toate nodurile care sunt accesibile în d și t se dovedește a fi accesibil de la unul dintre cei cu o margine, atunci t este accesibil în d uh d plus unu și dacă d nu este accesibil de la niciunul dintre acele noduri cu margine, atunci t nu este accesibil când d plus unu sper că mă urmăriți, nu sunt sigur că ești uh, deci oricum acesta este algoritmul aici și uh uh corolarul este că poți calcula c sub d plus unul din c sub d pentru că dacă poți număra calea, poți testa pentru fiecare nod dacă este accesibil ca Am menționat înainte să parcurgeți toate nodurile, vedeți dacă sunt accesibile și d plus d plus unu și apoi numărați-le acum am c sub d plus unu și acum am terminat pentru că uh uh voi calcula fiecare d plus unu din valoarea d pe care am calculat-o anterior, voi face asta de la toate acestea ar trebui să spună zero aici de fapt um și cu excepția uh dacă calea spune dacă asta dacă funcția cale spune acum că nu există că răspunsul este nu, deoarece Încerc să vă fac să cunoașteți complementul limbajului căii și respingerea căii uh lucru pentru m spune da și acesta este algoritmul meu nedeterminist pentru complementul căii uh problema oricum poate trebuie să vă uitați puțin la offline um este prezentat într-un mod puțin diferit în carte, uh, nu știu dacă asta vă va fi mai mult sau mai puțin clar, dar cred că acest lucru a fost puțin mai dezambalat în scopul prelegerii, așa că haideți Vezi doar că nu primesc nicio întrebare, ceea ce înseamnă că probabil că am pierdut o mare parte din tine, dar vestea bună este că vom trece la un alt subiect, așa că nu ezitați să întrebați un întrebare despre asta dacă doriți sau vom schimba vitezele acum să vorbim despre teoremele ierarhiei, care va fi a doua jumătate a prelegerii, de asemenea, nu este atât de ușor, trebuie să spun că, probabil, un pic mai puțin tehnic decât este aceasta, dar De asemenea, asta va fi să petrecem timpul doar cu o singură teoremă, dar oricum, să ne uităm la ce vom merge și apoi vom avea o pauză, um, bine, ceea ce am arătat până acum, acestea sunt clasele de complexitate majoră, nu includ, să spunem că clasele complementare, clasele de tip co-np uh, acestea sunt clasele complexe majore pe care le-am văzut până acum și, după cum am văzut, formează o ierarhie a conținărilor, unele dintre acestea. contineri sunt banale și unele puțin mai puțin banale, dar nu am arătat dacă vreuna dintre aceste clase este diferită, știți, am subliniat că există câteva probleme nerezolvate aici, dar știm că vreuna dintre aceste clase diferă între ele sau s-ar putea prăbuși toate până la l și răspunsul la acesta este că știm că p spațiul și l sunt de fapt diferite, ceea ce putem dovedi și se bazează pe teorema care spune că dacă dai unei mașini de turnare mai mult spațiu, atunci poți face mai multe lucruri, așa că deoarece p spațiul este mult este o limită mai mare decât spațiul log, știm că putem face mai multe lucruri, de fapt, deoarece n l este conținut în spațiul log pătrat în mod determinist și spațiul p este mai mare decât putem separa de fapt spațiul p și nm, așa că mergem pentru a demonstra că astăzi, deci, în principiu, ideea teoremei spune că, dacă dai unei mașini de turnare puțin mai mult timp sau puțin mai mult spațiu, atunci poate face mai mult, deși aveți anumite condiții pe care trebuie să le facem Vom ajunge la una dintre concluziile pe care le vom arăta este că timpul n pătrat dacă compari cu timpul, știi timpul cu lucrurile pe care le poți face în timp n pătrat față de lucrurile pe care le poți face în timp cub acolo Sunt mai multe lucruri pe care le poți face în timpul n-cub, apoi poți ceea ce poți face cu timpul n-pătrat, adică la asta te-ai aștepta, dar nu este cazul în care tot ceea ce ne așteptăm în teoria complexității putem demonstra că acesta este unul dintre lucrurile pe care le putem dovedi, astfel încât pe măsură ce adăugați mai mult timp, puteți face mai multe lucruri, deci acesta este un subset adecvat aici, deci există unele lucruri în timp n cuburi care nu sunt în timp n pătrat și la fel pentru spațiu, bine, așa că se întâmplă să fie cel care ne aduce la pauza noastră de cafea și nu ezitați să-mi trimiteți orice întrebare despre ceea ce am făcut până acum sau orice altceva, altfel vom lansa cronometrul și ne vedem în cinci minute, bine, așa că am înțeles. primind câteva întrebări bune aici, am putea face și o soluție, asta este să revenim la acel um um uh um jurnalele nl este egal cu moneda l spune cineva, am putea face o altă selecție doar alegând nedeterminist vârfurile c și apoi nu și apoi să verificăm dacă toate sunt accesibile, asta este ceea ce facem, dar aveți grijă, deoarece nu putem stoca nodurile c, de aceea le facem pe rând, nu putem ghici toate nodurile c din față, deoarece Vom stoca tot ceea ce avem doar spațiu de jurnal, bine altul, așa că poate cineva întreabă de cât spațiu de lucru avem nevoie pentru stocarea pașilor intermediari, nu sunt sigur la ce pași intermediari vrei să spui, dar dacă sunt toate valorile ci pe care le știi, vezi trecând de la c0 la c1 la c2 la c3 nu le stocăm pe cele de care ai nevoie, ai nevoie de c sub d pentru a calcula c sub d plus unu și apoi uiți c sub d nu ai putut stoca toate valorile c, dar nu nu am nevoie de ele pe toate, ai nevoie doar de cea mai recentă pentru a merge la următoarea, bine, cineva întreabă, pot să trec peste de ce complementul căii în nl implică nl monedă egală l pentru că complementul căii este uh, în esență, este complet complet i înseamnă că este um, așa că totul în nl este reductibil la cale totul în cohen l este reducabil la complementul căii prin aceeași reducere um și deci, dacă poți face complementul căii în orice clasă uh, poți face toate complemente ale limbilor nl în orice clasă și astfel încât să puteți face complementul căii în nl puteți face toate problemele connell în afară în nl și deci atunci nl este egal cu virgulă acum trebuie să vă gândiți doar la logica acesteia. nu este că acea parte nu este dificilă, um de ce este suficient să rezolvi problema complementului de cale în nl care face totul pentru că este un lucru bun, deci același fenomen de completitudine pe care l-am văzut, bine, cineva întreabă despre problema celor doi am vorbit ultima dată despre asta și este um și știi, am subliniat că asta este în nl, știi bine problema celor două părți, complementul problemei celor două seturi, știi formulele nesatisfăcătoare ale două seturi că este un limbaj nl pentru că tu practic, pot căuta o contradicție nedeterminist în spațiul de jurnal, asta cred că probabil nu voi putea să explic asta într-un minut, dar poate că vom avea instructorii noștri de recitare să acopere că în recitare este o dovadă frumoasă, nu foarte greu, dar este o dovadă plăcută, este asta, știi că nu este ceva ce trebuie să faci, trebuie să te gândești la tine, trebuie să te certați, dar totuși nu este foarte greu, înțelegi cele două probleme triste și știi complementul de două seturi pe care l-am arătat este în nl și pentru că nl este egal cu monedă l, de asemenea, problema a două ședințe fără completare este în nl și, de fapt, este nl complet, ok, cred că va trebui să trecem mai departe. Rămâi după prelegere în cazurile în care orice întrebări la care pot răspunde rapid în acel moment îmi pare rău dacă nu am putut ajunge la întrebarea ta tocmai acum, bine, continuând aici, bine schimbând vitezele teorema ierarhiei spațiale, așa cum am menționat, cred că um uh poate că este bine să ne întoarcem la acest diapozitiv aici. Vom face teoremele ierarhiei timpului și spațiului care arată că dacă poți face puțin mai mult dacă acorzi puțin mai mult timp sau puțin mai mult spațiu, putem face mai multe lucruri, vom face mai întâi cazul spațiului, deoarece asta tinde de fapt să fie ușor, din anumite motive tehnice, puțin mai ușor, deci uh teorema ierarhiei spațiului, deci iată declarația teoremei și spune că pentru orice limită, gândește-te la s este vor fi unele pe care le cunoașteți legate de spațiu și din nou f trebuie să îndeplinească o anumită condiție tehnică în galben, amintiți-vă că este galben, deoarece asta va fi relevant mai târziu, um uh, deci va fi o condiție tehnică um, indiferent de funcția pe care o aveți. delimitat de spațiu aveți atâta timp cât îndeplinește această condiție, care este o condiție ușoară, dar aveți nevoie de ea, indiferent de spațiu limitat pe care îl aveți, puteți găsi o limbă a care necesită exact atât de mult spațiu, așa că dacă f este ca n cub, mergem pentru a găsi o limbă a care necesită n spațiu cub, dacă este de la n la suta, putem găsi limba care necesită în spațiul al 100-lea și nu poate fi făcută în spațiul 1999, orice ar fi, puteți găsi o limbă care necesită exact atât de mult spațiu și dacă Îți place puțin mai formal, așa că înseamnă că se poate decide în atât de mult spațiu, dar nu poate fi decis în mai puțin spațiu, bine încadrându-l într-un mod ușor diferit în ceea ce privește clasele noastre spațiale, eu voi defini un noțiune care este, știi, nu este, nu este spus așa în carte, dar poate că este o modalitate utilă de a o nota, este spațiul mic o din f din n, așa că acestea sunt toate lucrurile pe care le poți face printr-o funcție care este mică o din f din n în spațiu, astfel încât spațiul mic o din f n este conținut în mod corespunzător în spațiul f din n, cu alte cuvinte, există ceva aici care nu se află acolo, bine imagine ilustrat, voi prezenta un limbaj un limbaj explicit a pe care îl pot faceți în atât de mult spațiu, dar nu în mai puțin acum, știți că puteți să vă gândiți la asta un pic ca situația pentru limbile fără context și limbile obișnuite, în care am prezentat un anumit limbaj care a diferențiat că era fără context, dar nu este obișnuit și vom face cam același lucru acum, dar singura diferență cheie este că, în cazul separării contextului liber și obișnuit, am putea da un limbaj frumos precum 0 la k1 la k aici limbajul nu va fi atât de drăguț să descrii, va fi limbajul pe care o va decide o mașină de turnare pe care o vom oferi, dar nu vei reuși să înțelegi o înțelegere simplă și simplă a unei mașini de turnare. mașina face și așa că, în acest sens, nu este un limbaj foarte natural, um, care este ușor să-ți iei mintea în jurul um, așa că schița i și într-adevăr nu trebuie să-ți faci griji pentru asta, dar poate te ajută, va fi într-adevăr un fel o dovadă a diagonalizării um felul în care va funcționa această mașină d um, așa că d vă va oferi limbajul meu a um deci d va fi proiectat și vă voi arăta d pe următorul diapozitiv uh d merge să rulez în spațiul meu țintă legat de f de n și iată cheia iată că kicker-ul d va fi proiectat pentru a se asigura că limbajul său nu poate fi făcut în mai puțin spațiu și modul în care face asta este că se asigură că limbajul său este diferit din orice limbaj care poate fi decid de către o mașină de turnare în mai puțin spațiu și va fi diferit în cel puțin un loc, așa că orice d va garanta că limbajul său nu poate fi făcut în puțin o din f din n spațiu, deoarece este va fi diferită de orice limbă care este realizabilă în puțin o din f din n spațiu undeva, bine, acesta este ideea și apoi limba a va fi limba acestei mașini de turnat d ok, așa că arată ca o ordine mare pe care o are d. pentru a vă asigura că fiecare știți că, pentru fiecare mașină, limba sa diferă de limbajul acelei mașini dacă acea mașină rulează în puțin spațiu de evenimente, dar practic va fi o diagonalizare, astfel încât pentru toate intrările diferite posibile la d asta intrarea va codifica de fapt o mașină pe care ne vom asigura că suntem diferiți de acea mașină dacă este o mașină cu spațiu mic, bine să vedem, așa că pot răspunde la câteva întrebări aici trebuie să fie calculabil, așa că aceasta va fi una dintre condițiile pe care va trebui să le garantăm dacă f îndeplinește condiția tehnică, da, va ajunge la jumătate, va fi calculabilă, dar nu este suficientă întrebare bună, deși uh, bine, deci haideți să trecem de acolo, bine acum, deci iată care este treaba mea să vă ofer această mașină de turnat, astfel încât aceste limbi vor fi limba mea a mea, ceea ce poate, ceea ce necesită f din n spațiu, nu se poate face decât dacă OK, hopa, trebuie să am nevoie de diapozitivul complet aici, așa că trebuie să mă scot eu [Muzică] în regulă, acum, acesta este scopul meu. Vreau să expun această limbă pe care o pot face în atât de mult spațiu, dar nu în mai puțin. și așa că o să dau acestei mașini d, așa cum am menționat, unde limbajul lui a is d rulează în ordinea f spațiu de eveniment și așa ceva realizează această parte și d se asigură că limbajul său nu poate fi făcut în mai puțin spațiu, așa că care realizează această parte, așa că este diferit de limbajul oricărei mașini care rulează în puțin o eveniment f de n spațiu ok um [ Muzică] așa că așa va funcționa d. Ok voi încerca să vă fac o mică imagine uh pentru a ajuta la vizualizarea pentru a însoți descrierea uh, așa că d primește intrarea w, care are lungimea n, primul lucru pe care d îl face este că marchează f din spațiul lui n, deoarece este permis doar să utilizeze, vom permite doar lui d să folosiți f din n spațiu, deoarece altfel suntem în pericol ca d nu să nu fie în spațiul f din n, așa că d va garanta că, asigurându-vă că va marca f din n spațiu și dacă va încerca vreodată să folosiți mai mult decât atât, pur și simplu respinge și, în virtutea asta, suntem siguri că aceste limbaje sunt în spațiul f din n, deoarece d este o mașină de rotație spațială f din n și va fi partea în regulă, așa că această parte până acum este nu prea greu, bine, acum vom începe să intrăm în carne aici, așa că dacă acum, ceea ce vrem să ne gândim a fost o descriere a unei mașini pe care o vom alimenta, aceasta va funcționa pe w deci asta va trece puțin, știți, înapoi la ceva mai devreme, când am vorbit despre diagonalizare, așa că nu vă lăsați dezamăgiți de acest lucru, um noi, dacă ne gândim la w nu numai ca intrare pentru d, ci va fi și descrierea unei mașini și dacă se dovedește că w este nu descrie nimic, este doar un salt w atunci nu ne interesează, vom respinge doar acest lucru w ne interesează doar w este care descrie o mașină m bine, așa că dacă m dacă w uh descrie o mașină m, atunci vom rula m pe w și vom face opusul a ceea ce face m, asta este ideea pe care o facem. Vom doar să ne asigurăm că ceea ce facem nu este același cu ceea ce face Emma, la un nivel înalt, ideea de bază pentru asta nu este grea, așa că vom simula m pe w dacă m x respinge atunci vom accepta și dacă m acceptă, atunci vom respinge, vom face doar opusul și cred că așa trebuie să fim atenți când facem simularea, acesta este puțin detaliu, dar tu știți că aceasta este o dovadă în care trebuie să acordați atenție unor detalii, um costul simulării m pe d este doar un factor constant um, deoarece dacă m utilizează o anumită cantitate de spațiu atunci când d simulează m, știți că m poate avea o bandă mai mare alfabetul decât d face, dar acestea pot codifica apoi banda um m folosind mai multe celule pentru fiecare dintre celulele lui m, dar va fi doar un factor constant și asta este important aici, pentru că trebuie să ne asigurăm că știi dacă a fost o lovitură mare. sus um d nu ar fi capabil să ruleze m um cred că argumentez detaliile fără să mă asigur că înțelegem conceptul fundamental um, așa că permiteți-mi să susțin ideea că d face ceva opusul m acum uh d nu poate fi diferit de fiecare m, deoarece d în sine este o mașină de turnare, desigur, dar lucrul este că d rulează doar în intervalul f din n celule de bandă, așa că trebuie să poată face acea simulare a lui m în acea cantitate de bandă dacă m folosește o mulțime de bandă, atunci d va folosi o mulțime de bandă și doar va respinge, așa că acest lucru va intra într-adevăr în joc, fiind capabil să simuleze m dacă m folosește o cantitate mică de utilizare o cantitate mică de spațiu pentru ca d să poată face simularea bine, așa că hai să vedem, poate, așa că vor fi niște probleme aici, dar înainte de a ajunge la asta, hai să vedem care sunt întrebările tale cum poate ști o mașină de turing dacă w codifică o altă mașină de turing, nu, e simplu, știi ce este o codificare a unei mașini de turing, doar că știi standardul, avem o codare standard, um, doar că știi să codifice regulile mașinii, așa că trebuie să aibă stări funcția de tranziție bla bla bla, așa că trebuie doar să știți care ar fi codificarea noastră pentru mașina de turing, putem întotdeauna să testăm dacă un șir este o codificare legitimă a unei mașini de turing, astfel încât asta să nu fie rău, cineva spune de ce faceți respingem dacă folosim mai mult de f n celule, nu este bine să folosim ordinea f din n da ar putea fi, dar trebuie să o tăiem undeva, știi că ar putea fi, este în regulă, am putea folosi două f din n, am putea folosi 10 f din n, dar trebuie să avem o constantă pentru d și să fim pur și simplu constantă, așa că d trebuie să ruleze în f din n celule um și asta ne va garanta că va fi suficient de bun pentru noi, bine, trebuie să facem sigur că m rulează puțin din f din n, așa că nu putem spune cu adevărat dacă m rulează în puțin o din f din n sau ne putem spune dacă putem termina simularea, așa că de fapt asta va fi, poate poți doar să ții dezactivați această întrebare pentru că există un punct pe care trebuie să-l urmărim în ceea ce este um uh doar pentru că știți că putem sau nu reușim să terminăm de simulat m pe acest w nu ne spune neapărat care este comportamentul asimptotic din m este, dar va trebui să ne uităm la asta puțin în regulă, așa că cineva va spune ce se întâmplă dacă m buclă pe w, aceasta va fi una dintre problemele noastre cu care trebuie să ne confruntăm, este o întrebare bună, doar pasul doi le poate folosi mai mult de f din n celule, da, doar pasul doi poate folosi mai mult de f din n celule, dacă o face, vom ajunge doar să proiectăm bine, așa că primim întrebări bune aici, unele dintre ele la care mergem Mă voi adresa oricum, așa că de ce nu mergem mai departe, um, bine, așa că aici este o întrebare, cred că aceasta este una dintre întrebările care se referă la una dintre cele care au fost întrebat ce se întâmplă dacă rulează în puțin f din n spațiu, așa că ne amintim ceea ce încercăm să facem este să fim diferiți de fiecare spațiu mic pe care îl cunoașteți puțin o din f din n mașină spațială, așa că dacă m rulează puțin o din f din n spațiu, dar are o constantă mare deci ceea ce vreau să spun prin asta în mod concret este să presupunem că d este un spațiu cu n n cuburi, așa că să presupunem că încercăm să introducem un în spațiu cub, dar arătăm ce nu este în spațiu n pătrat d va rula un n cub și ce și trebuie să asigurați-vă că orice mașină care rulează în spațiu n pătrat nu poate face același limbaj, um, așa că vom fi diferiți de asta, dar problema este că mașina m ar putea rula în spațiu n pătrat, dar cu o constantă uriașă deci s-ar putea să ruleze într-un milion de n pătrat, deci aceasta este încă o mașină care rulează într- un pic de n cub și trebuie să fim diferiți de ea, dar pentru w anume la care lucrăm, s-ar putea să nu avem suficient spațiu pentru a rula m din cauza constantei uriașe, că comportamentul asimptotic va fi relevant doar pentru w mare pentru b mai mic, este posibil să nu vedem că este posibil să nu avem suficient spațiu pentru a rula m, deci ce vom face pentru a remedia asta vom rula acel m pe infinit de w diferite, deci vor fi infinit de multe w diferite care toate vor codifica același m și modul în care o voi face este prin a mă gândi la w ca reprezentând m dar având un număr nelimitat de zerouri finale după aceea, așa că voi elimina primul lucru pe care îl voi face cu w este că voi elimina zerourile finale în cel final pe care îl voi face să le eliminam și apoi să iau restul și ca descrierea mașinii, așa că acum voi avea potențial w care au un număr enorm de zerouri la sfârșit suficient de mari încât să pot vedea comportamentul asimptotic al lui m și că dacă m rulează într-adevăr în puțin o din f din n spațiu, voi avea suficient spațiu pentru a rula m până la finalizare pe w și atunci voi putea fi diferit de el, bine, așa că arăt asta aici. deci iată un w foarte mare, voi elimina zerourile finale, restul va fi doar m și voi rula acest m pe ansamblu w întregul w fără zero, așa că acum m va rula pe o intrare foarte mare, um suficient de mare, astfel încât d uh d care are asimptotic mai mult spațiu decât m va avea suficient spațiu pentru a rula completarea goală um acum o altă întrebare care a fost întrebată ce se întâmplă dacă m bucle va fi o problemă pentru că d trebuie să țină întotdeauna și dacă doar simulează orbește m, atunci d ar putea fi în buclă pe m, apropo, niciunul dintre m nu va folosi mult spațiu pentru că atunci d îl va prinde la pasul unu, dar dacă m își folosește buclele pe o cantitate mică de spațiu, atunci uh d s- ar putea să ajungă să facă bucle așa cum a fost construit în prezent, așa că ceea ce voi face este să pun un contor care îl face să se oprească dacă rulează pentru 2 la f din n spațiu, deci practic, pentru că atât timp ar putea rula d fără să facă bucle oricum m ar putea rula oricum fără să facă bucle și așa că o vom rula pentru această cantitate din acest număr de pași și voi respinge dacă a făcut-o. încă nu m-am oprit la fel de bine și asta pentru că oricum trebuie să fie în buclă în acel moment și deci nu este interesant pentru noi, nu contează ce vom face dacă nu s-a oprit pentru că m nu este un hotărât și ultimul lucru este cum să calculăm f um, așa că voi încerca să răspund la câteva întrebări aici în timpul care ne rămâne, uh, cum să calculăm f, așa că pentru a marca f din n celule, trebuie să calculăm și dacă nu am crezut că nimeni dintre voi, băieți, ați pus această întrebare, cu excepția faptului că f este o funcție calculabilă, cu siguranță, f va trebui să fie calculabilă, dar nu numai că trebuie să fie calculabilă, ci trebuie să fie calculată în spațiul limitat și asta se întâmplă. să fie o condiție pe care o vom impune dacă este așa- numita construcție în spațiu și anume că o puteți calcula în cadrul propriului spațiu și toate funcțiile frumoase la care ne pasă vor fi construite în spațiu, așa că nu se dovedește a fi un obstacol în aplicarea teoremei ierarhiei, dar este o condiție că avem nevoie de ea, de fapt, nu este adevărată fără această condiție, um, bine haideți să facem doar oh, asta am o verificare aici, poate putem răspunde mai întâi câteva întrebări. De fapt, anticipați înregistrarea mea, ceea ce este bine, așa că permiteți-mi să renunț la cei scuze puțin confuzi în ceea ce privește ce este m putem spune d ca intrare m și să simulăm m pe da, așa că cineva spune că putem spune că d are intrare m și simulează m pe sine, da exact asta se întâmplă, motivul pentru care facem asta este pentru că trebuie să acoperim toate m-urile posibile, astfel încât să obținem toate intrările posibile, ele vor varia peste toate capetele posibile și astfel fiecare posibil O să mă adresez pentru a vedea dacă îl putem rula în spațiul delimitat și să fim diferiți de el. Treaba lui este să fie diferit de fiecare dintre acele capete, dar nu știi din nou că au fost câteva detalii aici care au fost ridicate în acestea. probleme, um, dar într-un fel este doar ceva mai tehnic, m-aș concentra pe înțelegerea a ceea ce am scris inițial pentru că aceasta este ideea principală, restul este doar un fel de detalii de implementare, bine, așa că de ce nu pot să dau un exemplu a unei funcții care nu poate fi construită în spațiul da jurnal jurnal jurnal n spațiu nu poți calcula jurnal jurnal jurnal n spațiu în jurnal jurnal jurnal n spațiu și, de fapt, se știe că nu este nimic nou între spațiul constant care este doar obișnuit și jurnal jurnal jurnal n spațiu orice puteți face în jurnal jurnal jurnal n spațiu este un limbaj obișnuit, așa că teorema ierarhiei nu se aplică nu se va aplica acolo pentru că bine se aplică, dar asta nu este un nu este bine, știi că nu este, nu este construibil în spațiu pentru a găsi un nivel mai înalt, știi funcții mari, care nu pot fi construite în spațiu, poți face asta, dar ele știi că nu sunt ușor de descris, bine hai să ne verificăm aici ce se întâmplă când rulăm dion în sine. Am un Câțiva oameni m-au întrebat despre asta, așa că acesta este doar un bun indiciu pentru check-in și trebuie să înțelegeți puțin ce se întâmplă pentru a vedea ce se face atunci când vă hrăniți în sine, poate cu niște zerouri finale. pentru că amintește-ți că algoritmul elimină finalul zero, deci ce este ce face în acest caz, așa că iată opțiunile mele acolo, pe care le poți alege pe care dintre ele, care crezi că este răspunsul, așa că îți voi mai acorda încă 30 de secunde la asta, deoarece asta necesită puțină gândire, dacă vrei să investești în asta, bine, închei asta băieți cinci secunde pentru a merge bine, o voi termina, așa că obțineți-vă punctele de participare într- o mulțime dintre voi nu ați uh a spus ceva, um, pot vedea numărul aici și sunt trei sau patru dintre voi nu vi se răspunde bine, veți pierde închiderea bine, așa că răspunsul corect este de fapt c respinge, să înțelegem ce s-a întâmplat este cu siguranță că nu avem o contradicție, adică acesta este un algoritm pe care tocmai l-am descris, va face ceva, umh, presupun că oamenii care l-au ales se distrează așa cum am făcut eu când am venit cu check-in-ul dar um uh nu o întrebare, răspunsul a nu va fi nici bun pentru că d trebuie să fie un decident, astfel încât să nu se potrivească nimic, așa că singurul tip de răspunsuri rezonabile sunt acceptarea sau respingerea atunci când rulați d pe sine. uh ce va încerca să facă, va merge la primul lucru pe care îl veți ști, marcați f din n celule de bandă și apoi va primi intrarea, care încearcă ea însăși să se simuleze pe aceeași intrare pe care a simulat-o d va încerca, de asemenea, să marcheze f din n celule de bandă, dar um, din cauza unor simulări, știi că va fi un cost pentru a face stimularea atunci când d simulat va încerca să marcheze f din n celule de bandă pe care o va face aruncați spațiul d original și depășiți limita și așadar d va respinge chiar la pasul unu când încearcă să obțină o intrare a lui însuși, așa că este foarte clar ce se va întâmpla în asta, doar va respinge din cauza pentru aceasta respinge acest respingere în special și observă asta, știi, da, știi bine, lasă-mă să nu încerc să-l confund, bine, așa că asta e tot ce vreau să spun despre asta, um, hai să trecem acum în cele șapte minute rămase până la ora. teorema de ierarhie care este foarte are aceeași dovadă, dar unele dintre detaliile tehnice sunt ușor diferite, bine, așa că acum, dacă îți dau din nou o limită de timp, vei avea o față cu aceeași noțiune pe care trebuie să o poți calcula f în intervalul de timp al lui f, așa că trebuie să fie un timp construit, nu voi defini asta, um, deci există un limbaj a care necesită atât de mult timp um, așa că trebuie să fie decidabil în atât de mult timp, dar există o mică diferență aici și există și acesta este un artefact al demonstrației teoremei nu pentru că este un adevăr absolut, din câte știm noi, nu este că nu este decidabil, de fapt, nu poți dovedi ceva puțin mai slab atunci când ai o mașină de turnat bandă. că este puțin decidabil o mică, există un mic decalaj în ceea ce poți dovedi, așa că nu numai că nu poți să-ți demonstrezi că necesită puțin o, dar puțin o din puțin din f din n peste log f din n este uh ce poți demonstra că obții din această teoremă a ierarhiei în timp, dar să nu ne lăsăm deocamdată deocamdată, umh, bine, așa că schița dovezii este aceeași schiță ca și înainte, um uh, vom da un d care rulează în ordinea f de n timp, astfel încât se asigură că limbajul se află în acel timp de clasă de complexitate uh timp f din n și se asigură că este diferit de fiecare mașină care rulează mai repede printr- o dragoste semnificativă printr-un factor de log mai rapid, bine și de ce nu Nu arăt cum merge asta, dovada este, în unele privințe, aproape exact aceeași, eu voi da un d care rulează atât de mult timp și arată că este diferit de fiecare m care rulează într-un timp mult mai puțin algoritm pentru d acum calculează f n, dar face ceva puțin diferit cu f din n ține minte în teorema ierarhiei spațiului am marcat f din n spațiu acum acest eveniment f va fi folosit într- un scop diferit, va fi un ceas și trebuie să închideți m dacă rulează mai mult de f din n pași, nu dacă folosește mai mult de f din n spațiu, deoarece ne interesează doar m-urile care folosesc semnificativ mai puțin de f din n timp, așa că vom rulați un m, știți pentru f pentru un anumit număr de pași, orice ar spune m, vom face opusul și numai dacă putem finaliza cu adevărat acea simulare, vom fi capabili să fim siguri că suntem diferiți de ceea ce este m făcând um, acesta este tot algoritmul aici, nu trebuie să facem alte modificări și de unde provine acel factor de conectare, de fapt, vine dintr-un loc amuzant și știi că trebuie să intri în curajul asta când simulați m pe w amintiți-vă că m însuși a fost descris de w, așa că va trebui să scrieți o copie a lui m, care este că știți așa cum este descris de w și apoi veți fi și apoi Voi avea banda la care lucrez și care începe cu w și trebuie să fii acum trebuie să fii puțin atent cum reușești asta pentru că dacă descrierea ta pentru m este doar la început a benzii pe măsură ce simulați m de fiecare dată când faceți un pas și modificați banda, nu doriți să fiți nevoit să vă întoarceți la începutul casetei pentru a căuta următorul pas al lui m, așa că de fapt trebuie să purtați m împreună cu tine în timp ce faci simularea și poți face asta extinzând alfabetul benzii, astfel încât să poți avea efectiv două simboluri pe o celulă, unul va fi pentru a descrie m, iar celălalt va fi pentru doar pentru m pentru banda de simulare și îl vei purta cu m cu tine oriunde îți este capul, astfel încât să nu trebuie să mergi foarte departe pentru a căuta m și asta este tot posibil pentru că asta va adăuga doar un factorul constant pentru că m este fix în dimensiune nu depinde de știi că știi că pentru intrări mari la m m este fix, dar lucrul dificil aici este contorul pentru a ne asigura că nu folosim prea mult timp um [Muzică] contorul are dimensiunea jurnalului f din n pentru că atât de mare trebuie să numere până la, așa că ar trebui să-l poți închide dacă va depăși f din n pași um și pentru că știi că trebuie să alergi pentru o anumită perioadă de timp și purtând ținerea contorului în apropiere are contorul acum ar putea fi destul de mare și, deci, vă va costa un factor log de um costul de simulare pentru a muta acel contor tot timpul și de aceea trebuie să rulați doar cu un factor de log mai puțin. astfel încât să puteți termina într-adevăr în interval de f din n timp, deoarece sunteți așa cum vi se cere să faceți bine, îmi dau seama că este o gură acolo și poate că nu ați înțeles cu toții că nu contează, nu este atât de critic, cred ce Sunt cu adevărat mai îngrijorat dacă înțelegeți ideea principală a teorema ierarhiei, unele dintre aceste detalii de implementare, le cunoașteți dacă nu le primiți, nu mi-aș face griji pentru asta, cred că trebuie să le includ pentru a fi complet binecuvântat și să fiu sincer cu tine în ceea ce privește dovada, dar dacă nu ai urmat tot ce este în regulă, vreau să înțeleg ideea principală a algoritmului, asigurându-mă că ceea ce face este diferit de ceea ce face fiecare mașină dacă acea mașină funcționează în puțin o din f din n spațiu sau sau într-o mică perioadă de timp, știi puțin o din f n peste log f din n timp, bine deci și cred că vom termina aici, așa că nu mai mult timp Voi rămâne puțin pe aici, în cazul în care există întrebări aici, așteaptă, există una, hai să ne verificăm, deși hai să ne uităm la asta, acesta este un fel interesant de continuare a teoremei ierarhiei, um, dacă uită-te la cele două întrebări: l este egală cu p și p este egală cu p spațiu, acestea sunt ambele probleme nerezolvate, dacă teorema ierarhiei ne spune ceva despre acele întrebări și este destul de interesant că de fapt se descurcă bine, o las pe seama să- mi spui dacă vezi ce s- ar putea să-ți spună de fapt la închidere primiți răspunsul în bine unu doi trei Simt că conduc o casă de licitații aici ar trebui să am un ciocan. Ok da, de fapt, știm că dvs. știm că acestea sunt separate, deci nu, chiar dacă nu știm dacă l este p sau p este egal cu p spațiu, nu pot fi amândoi egali pentru că atunci um l-ar fi egal cu p spațiu și știm că este fals um, deci cel puțin unul dintre acestea are răspunsul nu, bine, așa că, cu asta, să încheiem prelegerea de azi, știi că demonstrăm aceste teoreme ale ierarhiei și de ce nu o să ne închid aici, dar înainte bine am terminat, ca să poți nu ezitați să mergeți, um, dar voi rămâne în cazul în care cineva are întrebări pentru câteva minute oricum și apoi o vom numi o zi, deoarece tocmai am arătat spațiu și este un subset adecvat de spațiu de la n la k pentru orice k de ce nu putem spune, de asemenea, că spațiu n este un subset propriu al spațiului p, da spațiul n este un submulțime adecvat al spațiului p, da, așa că cineva tocmai a întrebat că tocmai am arătat că spațiul n este un submult adecvat al spațiului n la k face asta De asemenea, spunem că spațiul n este o submulțime propriu-zisă de p spațiu, cu siguranță, orice um spațiu n la k este o submulțime adecvată de spațiu n la k plus unul care este o submulțime de p spațiu, astfel încât orice polinom fix va fi o submulțime de p spațiu, deoarece p spațiu include toate polinoamele care dintre cele două probleme nerezolvate, uh, cred că este mai probabil să fie adevărată, cred că majoritatea vreau să spun că aș paria că ambele nu sunt egale, așa că ambele au răspuns nu um uh ar fi ciudat, știi, adică crezi că l este egal cu p că orice poți face în timp polinomial, închei cu spațiul jurnal, spațiul jurnal este incredibil de slab și și spațiul p este incredibil de puternic, aș fi șocat dacă oricare dintre acestea ar fi egali, deci problema este că nu avem o metodă pentru a demonstra că problemele sunt, de fapt, au o complexitate mare de orice fel, nu știm cum să arătăm lucrurile în afara Nu știu cum să arătăm lucrurile în afara de p, cu excepția utilizării teoremei ierarhice, diagonalizarea este singura metodă pe care o avem pentru a arăta lucruri sau în afara orelor și există motive să credem că, pe măsură ce vom ajunge acest lucru, cred că următoarea prelegere, de fapt, există un fel de motive să credem că argumentul de tip teorema ierarhiei, care este diagonalizarea, nu va răspunde la aceste tipuri de întrebări, așa că avem nevoie de o metodă diferită, iar diagonalizarea este tot ce avem o întrebare bună, deși, dacă nu am apucat să răspund la întrebarea dvs., aveți o întrebare pentru mine. din nou, pentru că a fost îngropat, așa că înseamnă că suntem foarte departe de a infirma p versus np, așa că s- ar putea întâmpla mâine, știi cum faci cum faci cum poți spune că nu știi pare clar că prezentul Starea matematicii în acest moment este că știi că nu avem habar cum să răspundem la acest tip de întrebări și nu este evident că am făcut vreun progres, dar știi că asta este natura jocului care este natura bestia, știi că cineva are o idee bună și dintr-o dată se pot schimba multe lucruri și asta se poate întâmpla și apoi, în orice moment, poate unul dintre voi când au fost primele aceste rezultate, aceasta este chestia în regulă, teorema ierarhiei este veche asta se întoarce chiar la momentul când clasele de timp au fost definite pentru prima dată, cred că este unul dintre primele rezultate care arată ierarhia și asta e la sfârșitul anilor 60, nl equal coen l cred că am menționat a fost ca la mijlocul anilor 1980 mult mai târziu, vreau să spun din punctele tale de Vedeți că a fost puțin în epoca peșterii, oricum, dar uh, da, dar echipa ierarhică care este de fapt anterioară venirea mea pe teren, dar dar conelul nl egal era ceva ce eram Am simțit personal cât de surprinși au fost oamenii în regulă, cred că o să vă dau drumul pe drumul vostru.