[SCRÂȘIT] [FOSȘIT] [CLIC] MICHAEL SIPSER: Bună, oameni buni. Bine ai revenit. Așa că vom continua discuția pe care am avut-o... pe care am făcut-o în ultimele câteva prelegeri. Am vorbit mai întâi despre complexitatea timpului. Și apoi am schimbat treptele pentru a vorbi despre complexitatea spațiului. Așa că am avut câteva prelegeri despre PSPACE, cum au culminat cu a demonstra că există limbi care sunt PSPACE complete, și anume acest limbaj TQBF, de unde am început. Și apoi am demonstrat, de asemenea, că există probleme care implică jocuri, cum ar fi jocul de geografie generalizată, în care a determina care parte are o strategie câștigătoare este completă PSPACE. La sfârșitul prelegerii data trecută, ne-am mutat la un regim diferit de spațiu, și anume de la spațiu polinomial până la spațiu logaritmic. Și am introdus clasele L și NL. Așa că voi începe prelegerea de astăzi prin a revizui o parte din materialele despre N și NL, care cred că a venit puțin prea repede data trecută. Și apoi avem două teoreme importante pe care le vom acoperi astăzi. Unul este despre a demonstra că există limbaje complete pentru NL care au o legătură cu întrebarea L versus NL - spațiu de jurnal, spațiu de jurnal determinist, față de spațiu de jurnal nedeterminist. Aceasta este încă o problemă nerezolvată în domeniul nostru. Și astfel există o noțiune de problemă completă pentru NL. Și apoi vom demonstra o teoremă care a fost, la vremea ei, foarte surprinzătoare pentru oameni. Îmi amintesc când a apărut în anii 1980, că NL, de fapt, este închisă sub completare, că clasa NL și clasa coNL se prăbușesc ambele la 1, că sunt egale, ceea ce nu este modul în care credem că este situația. pentru NP. Dar până când cineva are dovada că este diferit, se pot întâmpla lucruri ciudate. BINE. Deci, cu asta, mă voi muta în colț. Și hai să ne facem recenzia. Deci, pentru a vorbi despre clasele de complexitate spațială care sunt mai mici decât n, a trebuit să introducem un nou model, care a fost modelul cu două benzi, unde era o bandă doar pentru citire care avea intrarea pe ea, la care de obicei te-ai gândi la ceva foarte mare -- tot internetul, sau ceva atât de mare încât nu poți să-l citești în memoria locală. Și apoi ai o bandă de lucru, care este memoria ta locală. Și modul în care vom gândi la asta în contextul spațiului de jurnal este că acea bandă de lucru este logaritmică în dimensiunea intrării. Și asta este suficient pentru a avea contoare sau indicatori mici în intrare, pentru că o locație de referință a intrării este doar-- aveți nevoie doar de log n biți pentru a face asta. Așa că am dat câteva exemple de L și NL-- de limbi L și NL, deci acest limbaj de ww invers, după cum vă amintiți. Deci, aici este o intrare în ww invers. Este un șir care urmează-- este un șir palindromic, care este de lungime uniformă. Și astfel puteți face o mașină în spațiul de jurnal aici care poate testa dacă intrarea sa este de acea formă. Și banda de lucru este doar-- tot ce are nevoie este un indicator în-- sau câteva indicatoare care se referă la locurile corespunzătoare ale intrării la care te uiți în acest moment. Așa că poate începeți să vă uitați la cele două simboluri a din exterior și apoi la simbolurile b care sunt lângă acestea. Și puteți scrie pe bandă unde căutați în prezent. Și asta va fi suficient pentru a-- s- ar putea să trebuiască să faceți zig-zag, desigur, înainte și înapoi mult pentru a face acel test. Dar asta e în regulă, folosind modelul. Nu vom măsura timpul. Ne vom concentra doar pe cât spațiu folosim. Un alt exemplu pe care l-am dat este limbajul PATH, în care vi se oferă un grafic și un nod de pornire și un nod țintă. Și vrei să știi, există o cale în acest grafic direcționat care merge de la s la t? Și acesta este limbajul care este, de asemenea, acea limbă este în NL, de fapt, nu se știe că este în L. Deci, așa cum ar arăta, trecând la o intrare în limbajul PATH, ai avea un grafic reprezentat, să zicem, printr-o succesiune de margini și un început și o țintă. Și banda de lucru ar ține evidența nodului curent. Deci mașina nedeterministă ar ghici o cale care te duce de la s la t, nod cu nod. Și banda de lucru ar ține evidența nodului curent. OK, deci sper că ai asta... să dezvolți puțin o intuiție pentru aceste clase, L și NL. O să petrecem întreaga prelegere astăzi vorbind despre asta. BINE. Deci, așa cum am menționat, problema L și NL este o problemă nerezolvată. Și este foarte analog cu problema P versus NP, cu excepția, așa cum am menționat, așa cum vom arăta, că NL și complementul său ajung să fie aceleași, ceea ce nu pare să fie cazul pentru NP, deși noi nu stiu. Ne putem gândi la asta ca la o mașină Turing cu mai multe capete? Primesc o întrebare despre asta, care cred că poți. De fapt, acesta este un mod alternativ în care oamenii îl privesc. Puteți crede că are mai multe -- știți, un cap are nevoie practic de spațiu în jurnal pentru a stoca locația -- pentru a stoca locația unde ar fi capul. Deci, dacă vă imaginați că aveți mai multe capete diferite pe banda de intrare, vă puteți gândi la o mașină cu spațiu de jurnal ca fiind un fel de mașină Turing care are mai multe capete pe tabelul de intrare. Este echivalent. Buna intrebare. Deci hai să mergem mai departe, atunci. BINE. Deci, unul dintre lucrurile pe care le-am demonstrat data trecută a fost că orice puteți face în L, puteți face și în timp polinomial. Și voi răspunde la unele dintre aceste întrebări de chat într-un minut. Dar... deci clasa L este o submulțime a lui P. Acest lucru este ușor de demonstrat. Dar cred că este totuși important să vedem de ce este adevărat, deoarece stabilește un fel de definiții ale lucrurilor pe care le vom folosi mai târziu. Deci, în special, trebuie să cunoaștem noțiunea de configurație a unei mașini de spațiu de jurnal pe o intrare. Deci, deoarece intrarea nu se schimbă, nu considerăm cu adevărat că intrarea este parte a configurației. Singurul lucru care este -- lucrul care este relevant în configurație este partea dinamică a mașinii -- starea, locațiile capului și conținutul benzii de lucru. Deci definim că configurația pentru mașină pe o anumită intrare, w, este acele patru lucruri -- starea, cele două locații ale capului și conținutul benzii. Și lucrul important de reținut pentru această teoremă este că avem doar un număr polinom de configurații diferite dacă doar faceți calculul. Partea principală este numărul de conținuturi diferite ale benzilor pe care le puteți avea, care este exponențial în jurnalul n. Și acesta este un polinom. Prin urmare, orice mașină care rulează în spațiul de jurnal, cu condiția să țină mereu, și presupunem întotdeauna că mașinile noastre țin întotdeauna, ele pot rula doar pentru un număr polinom de pași, pentru că sunt atâtea configurații diferite câte au. Dacă ar rula, să zicem, un număr exponențial de pași, ar trebui să repete configurații. Și apoi ar fi făcut buclă. OK, așa că iată-ne. OK, lasă-mă să mă întorc... așa că cineva mi-a pus o întrebare. Care este mai greu? P versus NP sau L versus NL? Complet habar. Este o... Presupun că a existat o linie comună de gândire că, dacă vrei să... că este bine să încerci să te gândești la... dacă încerci să separați clasele, ați putea la fel de bine să urmați cursuri care sunt la fel de bine departe unul ca altul. De exemplu, dacă încerci să demonstrezi -- dacă compari P diferit de NP și P diferit de PSPACE, poate că P diferit de PSPACE ar putea fi mai ușor, deoarece P și PSPACE par să fie și mai departe decât P și NP. Nimeni nu stie. Și bănuiesc că există ceva fundamental în calcul pe care pur și simplu nu îl înțelegem. Și apoi, odată ce cineva face o descoperire și rezolvă una dintre acele probleme, multe dintre ele vor fi rezolvate în scurt timp. Dar din nou, este pură speculație. OK, d. Ce este d aici? d ar fi dimensiunea alfabetului benzii. OK, deci acesta este numărul de conținut diferit de bandă pe care îl avem. Bun. În regulă. Deci hai să continuăm. Un alt lucru pe care l-am menționat cam repede în treacăt, dar totuși un fapt important, este că teorema lui Savitch funcționează până la nivelul spațiului logaritmic - aceeași dovadă exactă. Deci, asta înseamnă că spațiul log nedeterminist este conținut în spațiul log pătrat determinist, pentru că asta face teorema lui Savitch pentru tine. Convertește mașinile nedeterministe în mașini deterministe cu prețul unei pătrate în spațiul de care aveți nevoie. Și deci nu voi trece prin asta în detaliu. Dar aceeași imagine pe care am copiat-o dintr-un diapozitiv anterior cu o simplă modificare este că, în loc de-- că sunt chiar jos-- dimensiunea configurației va fi acum log n, pentru că atât de mari sunt configurațiile atunci când aveți o mașină de spațiu de jurnal nedeterministă. Simulând asta... așa ar arăta tabloul pentru o mașină din NL. Și apoi puteți simula asta în același mod încercând toate intermediarile posibile și apoi împărțind-o, făcând jumătatea superioară și apoi jumătatea inferioară. Folosim spațiul, desigur, recursiv. Cantitatea de spațiu de care veți avea nevoie va fi suficientă pentru a stoca, pentru un nivel de recursivitate, o configurație. Și acesta este spațiul de jurnal de comenzi. Și apoi numărul de niveluri de recursivitate va fi un alt factor al log n, deoarece acesta este log la timpul de rulare, care va fi exponențial în log n, care este polinom. Deci, cantitatea totală de spațiu de care ai avea nevoie ar fi spațiu log pătrat. Din nou, aceasta este un fel de a spune dovada teoremei lui Savitch, din nou. Deci, dacă vine prea repede pentru tine, revizuiește doar dovezile teoremei lui Savitch și observă că funcționează, chiar dacă cantitatea de spațiu pe care mașina-- cu care începe mașina nedeterministă este spațiu de jurnal. În regulă. Și ultimul lucru pe care urma să-l fac -- ultimul lucru din categoria unei recenzii este teorema noastră că nu numai că tot L este în P -- și asta este un fel de banal, cam imediat. Nici măcar nu trebuie să schimbați mașina. Dacă aveți o mașină de spațiu de jurnal pentru o anumită limbă, aceeași mașină este o mașină a timpului polinomială pentru limba respectivă, deoarece poate rula doar pentru o perioadă de timp polinomială. Dar acum, avem o mașină nedeterministă pentru un anumit limbaj. Va trebui să o schimbăm pentru a deveni o mașină deterministă care rulează în timp polinomial. Și așa vom oferi o simulare de timp polinomială deterministă a unei mașini spațiale nedeterministe. Și am cam făcut asta ultima dată, dar puțin repede. Deci, acum, dacă avem o mașină nedeterministă a spațiului de jurnal , deci un M, care decide limbajul A în spațiul de jurnal, vom arăta cum să simulăm acea mașină cu o mașină a timpului polinomistă deterministă . Iar ideea cheie, care va apărea într-o teoremă ulterioară, atât de bine să o înțelegem nu numai aici, ci și să o înțelegem pentru următoarea teoremă care urmează, este noțiunea de graf de configurație. Mă gândeam să-i numesc un grafic de calcul. Dar acum, la o reflecție ulterioară, cred că graficul de configurare este poate termenul mai sugestiv. Deci hai să rămânem cu asta. Deci, un grafic de configurare pentru o mașină pe o intrare este doar un set de toate configurațiile pe care le are mașina, toate configurațiile diferite posibile pe care le poate avea mașina, cu muchii care conectează configurații care corespund mișcărilor legale ale mașinii. Deci, aici este o configurație. Acesta este un instantaneu al mașinii la un moment dat. Iată o altă configurație, un alt instantaneu al mașinii la un moment n timp. Și vei desena o margine între ci și cj dacă cj ar putea urma într-un singur pas de la ci. Și ați putea spune doar uitându-vă la configurații dacă acest lucru ar putea fi posibil. Evident, capul trebuie să fie un loc peste în cj de unde era în ci. Și trebuie să fie actualizat conform regulilor mașinii. Așa că puteți spune dacă... pentru a putea completa acest grafic. Puteți nota toate configurațiile posibile. Și puteți lăsa marginile în jos. Acum, ideea este că atunci când avem o mașină de spațiu de jurnal, nu avem prea multe configurații posibile. Există doar un număr polinom. Deci dimensiunea acestui întreg grafic este polinomială. Așadar, simularea noastră de timp polinomial va scrie întregul grafic de configurare al mașinii de spațiu de jurnal pe intrarea sa. Există [INAUDIBLE] multe configurații. Pot fi doar polinomial multe. Deci, puteți nota toate acele configurații ca noduri și apoi mergeți să vă uitați la fiecare pereche de noduri, dacă această configurație ar putea duce la acea configurație. Potrivit... este o mașină nedeterministă. Deci, o configurație ar putea merge în mai multe locații diferite - ar putea exista mai multe moduri diferite de a merge. Dar acestea sunt doar câteva muchii de ieșire diferite de la un anumit nod din acest grafic care reprezintă configurația, care ar putea avea mai mulți succesori legali diferiți în calculul nedeterminist. BINE. Acum, lucrul important aici este că M își acceptă intrarea, w, exact atunci când există un grafic de configurare a căii [INAUDIBIL] care vă duce de la configurația de pornire la configurația de acceptare. Și așa cum am menționat, să presupunem, așa cum am făcut, că mașina... ar fi trebuit să o pun aici, dar nu am făcut-o. Dar aparatul, când este pe cale să accepte, își șterge banda de lucru și își mută ambele capete în poziția de acasă la capătul stâng al benzii. Deci, există o singură configurație care acceptă de care trebuie să vă faceți griji. Pur și simplu face viața mai simplă. Deci va exista o configurație de pornire, o singură configurație de acceptare în acest grafic de configurare. Și acum va exista o cale, indicată aici, care conectează configurația de pornire la configurația de acceptare dacă și numai dacă M acceptă w, deoarece acea cale este secvența de configurații prin care ar trece mașina dacă l-ai lansa pe w. Ar începe de la început. Și ar putea exista mai multe moduri diferite de a merge. Dar dacă există una dintre ele care te conduce la o acceptare, aceasta va corespunde unei ramuri a calculului pe care o acceptă. OK, așa că asta ne spune care este algoritmul de timp polinomial. Pe intrarea w, construiți acel grafic de configurare pentru M pe w, G sub Mw. Și testați dacă există o cale de la începutul c până la acceptarea c folosind orice algoritm de căutare în profunzime în timp polinomial sau în primul rând pe lățime pentru a testa dacă există o cale de conexiune într-un grafic. Și dacă există o astfel de cale, accepți, pentru că asta înseamnă că mașina M a acceptat. Și dacă nu a existat cale, respingi, pentru că atunci M trebuie să nu fi acceptat. Și, prin urmare, aveți o simulare în timp polinomială a mașinii tale nedeterministe de spațiu de jurnal M, OK? Cum facem? OK, deci asta ne spune că NL este conținut în P. Și, de asemenea, L este conținut în NL, ca înainte. Deci avem o astfel de ierarhie a claselor. Acum, puteți chiar să vorbiți despre, nu numai că L este diferit de NL, ci chiar și L este diferit de P? Este posibil ca orice puteți face în timp polinomial, să puteți face spațiu [INAUDIBIL]? Nu stiu. Intrebare deschisa. OK, am primit o întrebare foarte bună aici chiar acum. De ce această construcție ocupă spațiu pentru bușteni? Nu este. Această construcție necesită timp polinomial. Acest algoritm de aici nu este un polinom - acesta nu este un algoritm de spațiu log pe care vi-l dau. Vă ofer un algoritm de timp polinomial pentru simularea unei mașini de spațiu de jurnal nedeterministă . Acum, mai târziu... Nu vreau să încurc problema chiar acum. Pentru acest slide special, tot ce trebuie să fac este să construiesc acel grafic în timp polinomial. Este un grafic de mărime polinomială. Nu pot stoca întregul grafic într-o memorie de spațiu de jurnal. OK, deci întrebare aici - putem vedea că enumerarea nodurilor și marginilor ar fi timp polinomial. Dar cum oferim de fapt structură acestei reprezentări grafice? Nici măcar nu știu ce înseamnă asta. Deci, dacă îmi puteți clarifica asta, atunci poate voi încerca să răspund. Dar un grafic este doar o listă de noduri și o listă de muchii. După aceea, știm care este graficul. Adică, s-ar putea să-ți placă o poză. Dar aparatul nu are nevoie de o poză. Definiția noastră a... noi doar reprezentăm aceste lucruri ca șiruri, în cele din urmă. Așa că vă rog să clarificați dacă doriți să... Voi răspunde la următoarea pauză. Sunt recunoscător pentru toate întrebările, pentru că sunt sigur, orice întrebare pe care o aveți oricare dintre voi, o aveți și alți 20. Deci întrebările sunt bune. Nu fi timid. Și, de asemenea, întreabă-i pe AT dacă devin supraîncărcat. OK, acum vom schimba treptele într-un material nou. În regulă. Vom vorbi despre noțiunea că-- un fel de gândire, analog cu problema P versus NP , unde au existat aceste probleme NP-complete, acum avem problema L versus NL. Vor exista probleme NL-complete care să captureze esența NL în felul în care problemele NP-complete captează esența NP, într-un sens, în sensul că toate problemele din NP sunt reductibile la ele. Deci sunt cam ca cele mai grele probleme NP. Aici, vom avea situații exact analoge pentru NL, în care vom arăta probleme în care toate celelalte probleme NL sunt reductibile la ele. Deci, dacă puteți rezolva una dintre ele, cum ar fi rezolvarea uneia dintre aceste probleme NL-complete în spațiul de jurnal determinist, atunci rezolvați toate problemele NL din spațiul de jurnal determinist. Deci este o definiție foarte asemănătoare cu cea pe care o aveam înainte. Este NL complet dacă este în NL. Și apoi toate celelalte limbi din NL ar trebui să fie reductibile. Dar acum, avem o nouă noțiune aici, cu un L în loc de un P. Acum, înainte, când vorbeam despre completitudinea NP, aveam reductibilitatea în timp polinomială. Asta nu va mai funcționa, pentru că, dacă vă amintiți, NL este un submult al lui P. Deci, toate limbile NL sunt polinomiale - sunt limbi în P. Și dacă vorbim despre -- dacă folosim reducerea timpului polinomial, toate limbajele în P sunt reductibile între ele. Trebuie să avem o noțiune de reductibilitate care este mai slabă decât clasa. Și astfel, reducția polinomială a timpului nu ar funcționa aici, pentru că totul ar deveni NL complet, pentru că totul este reductibil unul la altul. Deci trebuie să avem o noțiune mai slabă. Vom folosi reducerea spațiului de jurnal, pe care trebuie să o definim. Deci, aici, pentru asta, va trebui să vorbim despre noțiunea de funcție pe care o puteți calcula în spațiul de jurnal. Și aici este puțin complicat. La fel ca atunci când am vorbit despre recunoașterea limbii în spațiul de jurnal, acolo unde aveam banda de lucru trebuia să fie mai mică decât banda de intrare, deoarece intrările pot fi mari. Zona de lucru este mică. Acum, ieșirea ar putea fi, de asemenea, mare în raport cu zona de lucru. Deci vom avea un model cu trei benzi, unde intrarea va fi doar citire, ieșirea este doar scrisă - este ca o imprimantă. Este ceva pe care poți doar să scrii, dar nu poți să citești înapoi, pentru că altfel, ai putea înșela folosind rezultatul ca un fel de stocare. Și apoi aveți zona de stocare, care este banda de lucru pentru citire-scriere. OK, așa că asta-- vom numi asta-- numele tradițional al acestuia este un traductor de spațiu de jurnal. Deci convertește intrările în ieșiri, dar folosește doar spațiu de jurnal pentru memoria de lucru. OK, deci banda de intrare stochează n biți-- n simboluri. Banda de lucru stochează jurnal n simboluri, jurnalul de ordine n simboluri. Și apoi avem banda de ieșire. Poate doriți să vă gândiți cât de mare va fi un check-in care să vă întrebe cât de mare ar putea fi rezultatul? Dar îl vom păstra pentru final dacă... poți să te gândești la asta dacă vrei să te gândești înainte. BINE. Așadar, ne gândim la un traductor de spațiu log ca calculând o funcție, care este doar o mapare de la intrare la ieșire pe care traductorul ți-o oferă. Un traductor este o mașină deterministă, de altfel. Deci iei traductorul. Îi dai w. Și îl pornești. Și apoi se oprește cu f din w pe banda sa de ieșire. Asta înseamnă să calculezi funcția f, bine? Și vom spune că A este spațiul logaritmic reductibil la B, folosind simbolul indicele l pe semnul mai mic sau egal cu semnul, dacă este mapare reductibilă la B, dar printr-o funcție de reducere care poate fi calculată în spațiu logic, în același mod. definim reductibilitatea timpului polinomial. Dar acolo, am insistat că funcția de reducere era calculabilă în timp polinomial. BINE. Doar repede, am din nou o întrebare. De ce să înregistrați spațiu aici? Deoarece timpul polinom ar fi prea puternic pentru a face reduceri interne la P. Fiecare limbă din P este reductibilă la orice altă limbă din P. Și astfel, totul din NL ar fi reductibil la orice altceva din L cu o reductibilitate de timp polinomială. Și așa că nu ar fi o noțiune interesantă. Trebuie să folosim o noțiune mai slabă decât aceea, un fel de reducere mai slab, folosind un model mai slab, astfel încât să nu obțineți -- altfel, funcția de reducere ar putea răspunde dacă -- ar fi capabilă să rezolve problema A în sine dacă am avea o reducere a timpului polinomial și mapam lucrurile din NL la alte probleme din NL. Reducerea ar rezolva problema. Și nu asta vrei. Reducerea ar trebui să fie constrânsă doar pentru a putea face transformări simple asupra problemei, nu pentru a rezolva problema. Oricum, trebuie să te uiți la asta. Aceasta este o problemă care a mai apărut când am vorbit despre, care este noțiunea corectă de reducere de utilizat pentru completitatea PSPACE? Exact aceeasi discutie. BINE. Acum, există totuși o problemă la care trebuie să fim atenți. Când avem A fiind spațiu logaritmic reductibil la B și B în L, atunci ceea ce doriți -- dacă A este spațiu logaritmic reductibil la B și B în L, atunci doriți ca A să fie în L. Acesta este același model și noi. am avut întotdeauna pentru reduceri. Dacă A este reductibil la B și B este ușor, atunci A este ușor. Deci, iată, noțiunea de ușor este a fi un L. Acum, dacă vă amintiți dovada asta pe care am avut-o de înainte, pe care o voi pune doar pentru dvs., este aceea că pentru a arăta un rezolvator de spațiu de jurnal pentru A, luați un intrare, w. Și acum, dacă A este reductibil la B, calculați reducerea. Și apoi rulați decizia pentru B. Deci, dacă presupunem că A este reductibil la B și B este în L, deci B are un decident de spațiu logaritmic, luați w, pe care doriți să o știți, este în A ? O mapați la o problemă B folosind funcția de reducere. Și apoi rezolvi folosind decizia pentru B. Și dai același răspuns. Acum, acest lucru de fapt nu mai funcționează, sau nu funcționează într-un mod evident, pentru că, dacă mă urmăriți... sper că majoritatea dintre voi sunteți... există o problemă aici, care... pentru că noi Încercăm să oferim un algoritm de spațiu log pentru A. Și acel algoritm va calcula această funcție de reducere, mapând w la f din w. f din w ar putea fi în sine foarte mare, așa cum sugerează această imagine aici. Este posibil să nu puteți stoca f din w în memoria spațiului de jurnal pentru mașina care decide A. Deci acesta este un obstacol pe care trebuie să-l rezolvăm pentru a demonstra această teoremă, de care avem nevoie, deoarece aceasta este întreaga justificare pentru a face aceste reducbilități-- ar trebui să fie un fel de linie familiară cu ceea ce am văzut înainte. Deci nu avem spațiu pentru a stoca f din w. Ce facem? Și voi menționa, de asemenea, că acest lucru va fi relevant pentru una dintre problemele tale legate de teme. Deci ce facem? Nu avem spațiu pentru a stoca rezultatul intermediar de care avem nevoie pentru a rezolva problema. Am început cu w. Acum ar trebui să testăm dacă f din w este în B. Acesta poate rula în spațiul de jurnal. Dar pur și simplu pune mâna pe f de w... ce faci în privința asta? Deci, ceea ce vom face este următorul lucru, este hotărâtorul - decizia pentru B, care are nevoie de f din w, pentru că decide dacă f din w este în B - nu are nevoie de toate f din w stând acolo în fața ei deodată. Dacă vă gândiți la modul în care mașina Turing funcționează la intrarea sa, se uită doar la un simbol la un moment dat. Începe să citească simbolul cel mai din stânga al lui f din w, apoi poate că își mișcă capul spre dreapta și trece la al doilea simbol al lui f din w, apoi al treilea simbol al lui f din w. Poate ajunge până la al 10-lea simbol al lui f din w. Poate că îi mută capul pe spate și merge la al nouălea simbol și la al optulea simbol. Dar capul mașinii Turing , care decide B, se uită doar la un simbol al lui f din w o dată. Deci, în loc să scriem toate f din w, ideea este că vom calcula simbolurile individuale ale f din w de care avem nevoie doar în momentul în care avem nevoie de ele. Deci, dacă decizia pentru B citește al 10-lea simbol al lui f din w, pornim traductorul pe w. Și pe măsură ce își scrie ieșirea, pe care nu mai avem spațiu pentru a o stoca, aruncăm toate valorile de ieșire până ajungem la a 10-a. Și apoi spunem, ah, al 10-lea este orice, este un c, indiferent de valoare. Acum introducem asta în decidetorul pentru B. Acum putem simula acel decident pentru încă un pas. Acum decidentul spune, în regulă, acum am nevoie de al 11-lea simbol al lui f din w. OK, acum putem rula mașina aceea pentru încă un loc. Dar dacă are nevoie... dar nici măcar nu trebuie să o facem. Cred că cel mai bun mod de a ne gândi la asta este, de fiecare dată când acel decident pentru B are nevoie de un alt simbol, pornim traductorul din nou și pur și simplu aruncăm totul, cu excepția acelei ieșiri de simbol de care avem nevoie. Deci, de fiecare dată când facem un alt pas de simulare a lui B, va trebui să rulăm din nou traductorul de la început, doar pentru a-l recalcula , sau poate pentru prima dată, sau recalculam dacă avem nevoie de el ulterior. Va fi lent, dar nu ne interesează, să recalculăm acel simbol pe care simulatorul-- pe care îl cere decizia pentru B, bine? Deci spun asta aici. Recalculați simbolurile lui f din w după cum este necesar. OK, deci lasă-mă... hai să luăm câteva întrebări. Și apoi vom trece la un check-in. Deci cineva întreabă, de ce a trebuit să introducem traductor pentru reducerea spațiului logaritmic, când nu am făcut-o pentru reducerea timpului polinomial? Am putea avea pentru reducerea timpului polinomial. Dar nu aveam nevoie, pentru că am putea să o facem cu toții pe aceeași bandă. Problema este că, pentru spațiul de jurnal, banda este-- banda de lucru este prea mică pentru a reține intrarea pe ieșire. Deci nu putem - din moment ce lucrăm doar - avem un log n legat în care trebuie să lucrăm. Trebuie să separăm acele funcții de funcțiile de lucru, funcția de intrare și funcția de ieșire. Deci, dacă avem mai mult decât cantitatea de resurse pe care o avem, fie timpul, fie spațiul a fost de cel puțin n, atunci le-am putea pur și simplu să le adunăm pe toate și să avem ca banda aceea să facă mai multe funcții. Și cineva m-a întrebat aici, da, aceasta este cartografierea reductibilității, acest m. Aceasta este din noțiunea pe care am văzut-o înainte. BINE. F din w se află pe banda de intrare a lui B? Ei bine, da. Deci suntem... o întrebare bună. Deci f de w... știi, pentru că ce facem? Încercăm să găsim un decident pentru A aici, folosind decizia pentru B și maparea de la A la B, reducerea de la A la B. Deci, decizia pentru B se așteaptă să-și găsească intrarea pe o bandă de intrare. Acea intrare va fi f din w. Dar trebuie să obținem efectul acestui lucru fără a scrie de fapt acea bandă de intrare, pentru că nu avem suficient spațiu pentru a scrie banda de intrare pentru decident-- pentru decident B, pentru că ar putea fi foarte mare. Și avem doar... nu avem unde să punem f din w. Așa că gândește-te la ce se întâmplă aici. Facem o mașină cu spațiu de jurnal a cărei intrare este w, trebuie să calculeze f din w ca valoare intermediară, pentru a o introduce în decizia B. Nu va fi posibil să păstrați tot acel f de w la unu-- cu totul, pentru că este prea mare. Dar asta nu contează. Nu avem nevoie de ea. Aveam nevoie de un singur simbol la un moment dat, pe care îl putem recalcula. OK, deci să vedem. Deci cineva spune, ne putem asigura că banda de ieșire este de ordinul n, așa că nu trebuie să folosim mai multă bandă decât intrarea? Comanda n va fi încă prea mare. Unde vei pune acea ieșire? Chiar dacă este doar ordinul n-- în primul rând, răspunsul este nu, nu putem, pentru că vor exista reduceri care sunt mai mari decât atât. Dar cealaltă întrebare este, ne putem asigura că rezultatul este de ordinul n? Nu puteți pune ieșirea pe banda de intrare. Banda de intrare este doar pentru citire. Banda de ieșire este doar pentru scriere. Deci nu există loc pentru a-- chiar dacă ieșirea este la fel de mare ca și intrarea, nu te ajută. Dacă rezultatul este doar log n, OK, atunci am putea face acest lucru. Dar asta nu va fi interesant pentru noi. Veți avea nevoie, pentru aceste reduceri mari de spațiu , de ieșiri mari, așa cum vom vedea într-un minut. Care este timpul de rulare pentru această reducere a spațiului de jurnal? Totul va fi polinom. Totul va fi un algoritm de spațiu de jurnal. Deci totul va fi polinom. Există vreo reducere a completității NP care poate fi făcută în spațiul de jurnal? Toate NP-- toate reducerile tipice ale completității NP, acele reduceri de timp polinomial , toate pot fi făcute în spațiu logaritmic, deoarece sunt-- reducerile tind să fie transformări foarte simple. Și spațiul de jurnal va fi suficient pentru a le face pe toate. BINE. Nu pot să răspund la a doua parte. E prea complicat. Și cred că ar trebui să mergem mai departe. Deci, să ne uităm la primul check-in aici. Deci, dacă avem un traductor cu spațiu lung care calculează f și dacă îl alimentați cu intrări de lungime n, cât de mari pot fi ieșirile, de fapt? Deci de ce nu te gândești la asta și îmi dai un răspuns? Îți las un minut să răspunzi la această întrebare. Oh, acesta este unul greu. Permiteți-mi să spun din față, sunt... Mă lupt cu această prelegere, pentru că unele... mai ales lucrurile din a doua jumătate, sunt cam greu. Nu as spune ca este tehnic. Dar din punct de vedere conceptual, cred că o parte din material este puțin mai greu, poate în parte pentru că oamenii nu sunt obișnuiți să se gândească la complexitatea memoriei sau la complexitatea spațiului, chiar dacă nu văd de ce... Adică, cred că este o resursă importantă. a fi luat în considerare. Dar cred că este mai puțin obișnuit. Și cred că există un oarecare disconfort cu asta. OK, așa că am terminat. Încă cinci secunde, te rog. În regulă, pe cale să închei. Încheiați check-in-ul. 1, 2, 3. În regulă. Deci da, răspunsul corect este c. După cum am menționat, vom dori să avem ieșiri mai mari decât log n. Și nu există niciun motiv pentru care nu ar putea fi mai mari decât log n, conform definiției pe care v-am dat-o . Nu există nicio limită la ieșire. Măsurăm spațiul de rulare al acestui algoritm doar în ceea ce privește banda de lucru. Casetele de intrare și de ieșire nu contează. Deci pot fi mai mult decât log n. Ele pot fi mai mult de n. Polinomul este răspunsul corect. De ce? Pentru că un traductor de spațiu de jurnal, dacă ignorați doar rezultatul, este doar o mașină obișnuită de spațiu de jurnal. Și poate rula doar pentru un număr polinom de pași fără ca acesta să ajungă într-o buclă. Același argument pe care l-am dat pentru asta înainte se aplică și aici. Deci, dacă va depăși un număr polinom de pași, nu va ține niciodată. Și așa va fi... nu permiteți... trebuie să se oprească cu ieșirea pe banda de ieșire. Și astfel va fi descalificat ca traductor de spațiu de jurnal dacă nu se oprește. Deci nu poate fi nimic mai lung decât polinom. E bine să te gândești, să înțelegi. OK, deci hai să continuăm. Deci vom arăta că problema PATH este NL completă. Acum, am definit completitatea NL. Și am mai văzut problema PATH. Și acum vom arăta că PATH ocupă o poziție foarte specială pentru NL, și anume că este o problemă completă NL. Deci, dacă puteți rezolva problema PATH în mod determinist în spațiul de jurnal, ați obținut un rezultat mare. Nimeni nu știe cum să facă asta. Și ar prăbuși tot NL până la spațiul de jurnal dacă ați putea face PATH în spațiul de jurnal în mod determinist. Bine, deci să vedem de ce. Deci, în primul rând, cele două componente ale a fi complet sunt în limba și partea de reducere. Deci, în limbaj, am arătat deja. Acum, vrem să arătăm că pentru orice altă limbă din NL, spațiul de jurnal va fi redus la PATH. Într-un anumit sens, acest lucru poate să nu fie atât de surprinzător, gândindu-ne la dovada noastră că NL este un subset al lui P, pentru că am reușit să transformăm orice mașină NL, funcționarea oricărei mașini NL, într-o problemă PATH pe care mașina polinomială a timpului. apoi rezolvat. Și deci este chiar aceeași idee care spune că PATH captează cu adevărat orice mașină NL. Calcularea oricărei mașini NL poate fi văzută într-adevăr ca o problemă PATH, unde nodurile sunt configurațiile mașinii. Deci haideți să vedem cum... permiteți-mi să încerc să trec prin asta dacă nu a fost foarte clar, ceea ce nu sunt sigur că a fost. Deci, să presupunem că avem o mașină decisă de -- un limbaj decis de un nedeterminist -- o mașină NL, o mașină nedeterministă în spațiul de jurnal. Din nou, ar fi trebuit să pun asta înainte. Dar vom modifica M pentru a-și șterge banda de lucru și a-și muta capul la capătul din stânga la acceptare. Deci are o configurație unică de acceptare. Acum îi voi oferi reducerea spațiului de jurnal care mapează limba noastră A, care este în NL, cu limba PATH. Deci, gândindu-mă la ce înseamnă asta, voi lua o intrare, w, care poate fi sau nu în A, și voi produce pentru dvs. un grafic cu un nod de început și țintă, note de început și țintă, unde va urma w fi în limba dacă și numai dacă G are o cale de la s la t. Și care crezi că va fi acel grafic? Acesta va fi graficul de configurare pentru mașina care decide A, OK? Deci așa va arăta. Deci poate aici este o poză. Dreapta. Deci f din w, unde w, din nou, este problema ta despre apartenența la A, va deveni o problemă despre apartenența la PATH. Și va fi doar graficul de configurare pentru M pe w. Acum, ceea ce rămâne este să arătăm că putem face această conversie cu un traductor de spațiu log. Deci este o reducere calculabilă a spațiului de jurnal. Deci să încercăm să trecem prin asta rapid -- conceptual, nu foarte greu. Deci, iată traductorul nostru. Să ne gândim doar ce trebuie să facă. Trebuie să ia o intrare, w și să convertească acel f din w în acest lucru aici - graficul de calcul al lui M pe w - graficul de configurare M pe w, configurația de pornire și acceptare. Deci aici va arăta așa. Asta vrem să apară în cele din urmă pe banda de ieșire. Deci, modul în care vom realiza asta-- avem doar un spațiu mic de jurnal, comandă bandă de lucru pentru spațiul de jurnal. Și modul în care vom putea produce această ieșire este -- graficul de configurare este doar o serie de muchii, care sunt -- să zicem, puteți trece de la această configurație la acea configurație într-un singur pas. Deci, ceea ce vom face este, pe banda noastră de lucru, vom trece prin toate perechile posibile de configurații, din nou, doar în ordinea contorului de parcurs, doar uitându-ne la toate șirurile posibile, într-adevăr, în ordinea lungimii log n care sunt suficient de mari pentru a reprezenta două configurații. Din când în când, va fi de fapt o pereche de configurații. În acel moment, ne uităm la acele două configurații, ne uităm la M și vedem, poate această configurație să meargă la acea configurație? Dacă da, îl tipăriți pe banda de ieșire. Dacă nu, treceți la următoarea pereche de configurații. Și apoi, la sfârșit, notezi la început și accepți configurații. Deci am indicat asta aici. Aici este traductorul. Spune, la intrarea w, pentru toate perechile de configurații, că-- acum, acest lucru este notat pe banda de lucru-- scoateți acele perechi care sunt mișcări legale pentru M. Și apoi, în sfârșit, scoateți startul și Accept. Asta este. Deci, să vedem. Lasă-mă să răspund la orice întrebări aici. De ce avem nevoie de o stare specială de acceptare pentru M? Ei bine, vrem să avem... Cred că vrei să spui că accepti configurația. Vreau doar să am o-- nu vreau să am o multitudine de configurații diferite de acceptare posibile, pentru că atunci nu este cu adevărat o problemă PATH. Apoi devine o întrebare: pot ajunge de la început la unul dintre acele noduri care reprezintă configurații de acceptare? E puțin dezordonat. Aș putea să o repar. Dar cea mai simplă remediere este doar să existe o singură configurație de acceptare. Ei bine, de ce ies start și accept la sfârșitul casetei de ieșire? Așa îmi scriu problema PATH. Este un grafic, urmat de un nod de pornire și un nod țintă. Deci trebuie să urmez acea formă. Nu sunt sigur ce întrebi. Vrei să pun asta pe primul loc? Nu sunt sigur ce-- sau de ce deloc? Pentru că trebuie să fie un... iată-l. Iată rezultatul pe care îl caut. BINE. Cele trei... caseta de lucru de citire-scriere de aici stochează indicatori către configurație sau un fel de contor? Nu, ele stochează configurația reală. Configurația pentru M este... doar gândiți-vă ce este. Este un obiect cu dimensiunea spațiului de jurnal. Este o casetă pentru M. Este o locație a capetelor și a stării sale. Așa că ai putea să scrii chestiile astea chiar aici, în partea stângă a acestui... slot din stânga. Și în slotul din dreapta, vei scrie o altă configurație pentru M pe w. Și vei pune marginile în consecință. OK, deci cineva... a ajutat asta? Cineva, din nou, întreabă, de ce configurația este doar spațiu de jurnal? Este doar o bandă. Este o bandă de spațiu pentru jurnal. Acesta este principalul lucru în configurația benzii. Pe banda de lucru citire-scriere scriem doar două configurații deodată? Da. Doar scriem o margine candidată pe care o vom scoate pe banda de ieșire. Deci, de aceea avem două configurații. Vreau să știu, pot trece de la această configurație la acea configurație? Dacă da, îl imprimez, tipărim acea pereche. Acesta este un avantaj în graficul meu de configurare , care este ceea ce ar trebui să scot aici. Pot fi mai multe... OK, de ce nu mergem mai departe? Din nou, trimiteți întrebări către AT-ul nostru, care ar fi mai mult decât bucuroși să vă ajute. Și o să... lasă- mă să dau repede... ne descurcăm puțin aici din punct de vedere al timpului. Dar să vedem. Iată un exemplu care arată că o altă problemă este NL completă. Ai o problemă legată de teme. Așa că am crezut că vreau să vă dau un exemplu. Poate că putem amâna acest lucru până la recitare. Așa că poate vom încerca să facem asta puțin repede pentru a ne salva la timp. Dar problema 2SAT, care este la fel ca problema 3SAT, cu excepția a două literale pe propoziție-- în mod curios, complementul acelei probleme, deci formulele nesatisfăcătoare, care formează un limbaj complet NL. Și deci, în primul rând, trebuie să arăți că este în NL. Nu vom face asta. Este un exercițiu frumos. Nu este total banal de făcut. Dar poate vrei să încerci asta. Vom arăta că PATH este reductibil la complementul 2SAT. Trebuie să oferim o reducere care convertește graficele în formule, acolo unde există un PATH, acum, când formula este nesatisfăcută. Și ceea ce se va întâmpla este că PATH va corespunde unei secvențe de implicații în formulă, ceea ce produce o contradicție și o forțează să fie nesatisfăcută. Din nou, asta va veni puțin repede. Și atunci poate putem discuta despre asta în pauză, care este următoarea. Deci, fiecare nod din G va avea o variabilă asociată în formulă. Deci există o variabilă pentru fiecare dintre noduri. Pentru fiecare margine, va exista o clauză de implicare care conectează cele două noduri asociate. Deci, dacă există o margine de la u la v, atunci va exista o implicație în formula care spune, dacă xu este adevărat, atunci xv este adevărat. Și rețineți că acesta este echivalent cu modul mai convențional [INAUDIBIL] xu complement sau xv. Acestea sunt echivalente din punct de vedere logic. Așa că nu te înșel aici pentru a fi o problemă 2SAT. Ei chiar arată așa. Și, în sfârșit, voi pune două clauze suplimentare. Este [INAUDIBIL] x pentru variabila de pornire-- de la nodul de pornire, s-- aici, s. Vreau să-l forțez să fie adevărat. Deci este x-- deoarece vreau să am exact două pe clauză, adică xs sau xs. Deci asta forțează x-- acea variabilă adevărată. Și în sfârșit, dacă t este adevărat, asta va forța -- dacă xt este adevărat, asta va forța xs să fie fals. Deci, acum, dacă există de fapt o cale în grafic care merge de la s la t, va exista o secvență de implicații, începând de acum cu s fiind adevărat, forțând alte lucruri să fie adevărate, inclusiv forțarea t să fie adevărată, care apoi forțează e să fie fals. Și asta e contradicția noastră, care arată că formula nu poate fi satisfăcută. Deci, acum, trebuie să dovediți că acest lucru funcționează. După cum am spus, pentru direcția înainte, dacă există o cale, urmați implicațiile pentru a obține o contradicție. Dimpotrivă... permiteți- mi să nu petrec timp aici. Vă las pe voi să vă gândiți la offline. Dar dacă nu există o cale, există o modalitate de a atribui variabilele la adevărat și fals pentru a face o atribuire satisfăcătoare formulei. Deci asta dă cealaltă direcție, OK? Și puteți arăta că este calculabil în spațiul de jurnal. E foarte simplu, pentru că o transformare foarte simplă acolo, bine? Așa că cred că vom trece la pauză. Și sunt bucuros să răspund întrebărilor în acest moment despre asta. Configurația, mergând înapoi, include intrarea? Nu. Configurația nu-- așa cum am spus, configurația pentru M pe w este starea, pozițiile capului și conținutul benzii de lucru , nu banda de intrare, pentru că atunci ai fi-- nu există dintr-un motiv. . Intrarea este uriașă. Dar nu aveți nevoie de intrare acolo, deoarece intrarea va fi constantă pentru toată lumea. Toată lumea se poate uita la acea intrare, care este un fel de lucru extern fix. Cineva mă întreabă dacă există probleme NP-complete în-- cu siguranță există NP-complet [INAUDIBIL].. Nu știu-- există unele probleme în teoria numerelor unde este-- ca factoring, unde noi nu cunoașteți statutul, undeva între P și NP, formulat ca limbaj, desigur. Dar există probleme în rezolvarea anumitor tipuri de ecuații, ecuații de grad scăzut, pe care nu le amintesc acum dacă [INAUDIBLE] se știe de fapt că este NP complet. Acum, ați întrebat despre NL complet [INAUDIBLE].. Nu știu dacă există probleme de teoria numerelor NL-complete . O, bună întrebare. Mă întreabă cineva , NL are și o definiție alternativă folosind certificate sau martori? Da. Da, un fel. Pentru NL, puteți face un certificat, care este, din nou, certificat de dimensiune polinomială. Dar trebuie să fie... ai voie să-l citești doar cu capul unidirecțional. Deci este ca un certificat unidirecțional. Deci trebuie să fie... îl poți procesa doar într-un anumit mod. Acesta este un exercițiu frumos, de fapt, în sine. Dar oricum, haideți... acum am terminat. Și ne vom muta înapoi. Vom continua. Deci toată lumea se întoarce. Acesta este ceea ce urmează pe ordinea de zi, demonstrând că NL este egal cu coNL. Aceasta este o dovadă dură. O să încerc să o descompun cât de mult pot. Și să sperăm că vei obține... Sper că vei obține. Voi încerca să fiu cât de util pot. BINE. Dar dacă ți se pare greu, nu vei fi singur. Deci, în primul rând, vom arăta-- modul în care vom rezolva acest lucru este arătând că complementul PATH este rezolvabil în NL, deoarece complementul PATH este-- la fel cum PATH este complet pentru NL , complementul este complet pentru coNL. Și astfel, făcând acea problemă în NL, vom reduce toate-- toate coNL vor fi reductibile la probleme în NL. Prin urmare, vom fi în NL. coNL va fi atunci în interiorul NL. Și atunci NL va fi egal cu coNL. Dacă această secvență de conexiuni logice, nu este clară. Nu vă faceți griji. Ideea este că vrem [INAUDIBLE] să ne întoarcem și să ne dăm seama de ce este suficient mai târziu. Dar ceea ce înseamnă aceasta este că vrem să oferim o mașină nedeterministă, care va accepta atunci când nu există cale de la s la t. BINE? Și vă rog să nu spuneți, de ce nu luăm mașina pentru PATH și răsturnăm răspunsul? Nu poți face asta cu o mașină nedeterministă. Așa că mai bine... dacă crezi că asta e permis, du-te înapoi și revizuiește nondeterminismul. Deci vrei să faci o mașină nedeterministă, care va accepta atunci când nu există cale. Deci, o ramură va face o secvență de ghiciri. Și trebuie să fie sigur că nu există cale. Și atunci va fi... și atunci poate accepta atunci când nu există cale. Acum, dacă puteți găsi o modalitate de a face un separator, ceva care să taie graficul în jumătate și să separă s de t, atunci ați fi bine. Singura problemă este că nu există o modalitate evidentă de a face asta, pentru că astfel de separatori, chiar dacă erau [INAUDIBILI], probabil prea mari pentru a fi notate în spațiul de jurnal. Așa că vă voi oferi un mod complet diferit de a face asta. Și o să fac... aceasta este o prezentare puțin diferită de ceea ce este în carte. Cred că, sper, acest lucru este puțin mai lung și, prin urmare, puțin mai clar. Vom vedea. Deci, mai întâi de toate, voi defini o noțiune de mașină nedeterministă care calculează o funcție. Și asta e o idee simplă. Ceea ce vrei este, pe diferite ramuri, deci aveți o funcție, f, care are, pentru fiecare w, există o ieșire, f din w. Și mașina nedeterministă poate opera astfel încât pe toate ramurile sale, este permis fie să dea f din w, fie să spună respingere, adică să spună, fie să spună, nu știu. Deci fiecare ramură trebuie să dea răspunsul corect. Deci toate ramurile care dau un răspuns trebuie să fie de acord, pentru că există un singur răspuns corect. Toate ramurile care dau un răspuns trebuie să dea răspunsul corect, sau pot spune, nu știu. Singurul lucru este că trebuie să spuneți și că cel puțin una dintre ramuri dă de fapt un răspuns. Deci cineva nu poate respinge. Cineva nu poate spune, nu știu. Deci cel puțin una dintre ramuri dă un răspuns și... dă răspunsul. Și toate celelalte ramuri fie pot da răspunsul, fie pot spune-- pot doar respinge. Dar nu există ideea de a accepta. Există doar o noțiune despre această mașină nedeterministă, pe unele ramuri, dând valoarea de ieșire, iar alte ramuri doar spunând respingere. Poate respinge este cuvântul greșit. Aș putea spune doar punt. În regulă. Deci vom vorbi despre funcții pe care le puteți calcula cu mașini nedeterministe, în special cu mașini NL. În regulă? Așa că ne vom uita la această funcție de cale acum. Acum, acesta nu este exact același cu limbajul PATH. Aceasta este o funcție aici, scrisă cu litere mici. Deci, având în vedere un grafic, s și t, voi spune da dacă există o cale și nu dacă nu există cale. Și aceasta este o funcție acum, care va scoate da sau nu, nu o limbă. Aceasta este o funcție. Este foarte strâns legat. Am înțeles. Deci, dacă puteți rezolva funcția, puteți face limbajul. Dar ceea ce vom da este o mașină NL, o mașină nedeterministă, care va calcula această funcție. Și, prin urmare, puteți folosi asta pentru a face limbajul PATH. Două lucruri importante pentru noi sunt, dacă G este un grafic, ei bine, iată nodul de pornire, s. R reprezintă toate nodurile la care puteți ajunge din s. Aceasta este o colecție de noduri. Și c, care înseamnă count, este numărul de noduri accesibile. Așa că am scris asta mai mult aici... dacă îți place mai formal. R este numărul - este colecția de noduri pentru care există o cale de la s la nod. Și c este dimensiunea lui R. Deci trebuie să înțelegeți aceste două, pentru că ne vom juca cu asta pentru următoarele trei diapozitive. BINE. Acum, în primul rând, aceasta este un fel de teoremă de exercițiu. Dar tot va fi un fapt util de care vom ajunge să avem nevoie mai târziu. Dar este și un pic doar pentru a vă testa înțelegerea. Să presupunem că există o mașină NL care calculează această funcție de cale. Deci, pe diferitele ramuri ale nondeterminismului, având în vedere un grafic, G, s și t, vor exista unele ramuri care pot scoate da, sau unele ramuri care pot scoate nu. Și alte ramuri ar putea spune, nu știu. Dar aparatul trebuie să dea întotdeauna răspunsul corect dacă va da vreun răspuns. Deci toate ramurile fie trebuie să spună da, fie toate ramurile-- toate ramurile trebuie să spună da sau punte, sau toate ramurile trebuie să spună nu sau punte, pentru că unul dintre aceste răspunsuri va fi răspunsul corect. Deci, să presupunem că am un mod de a calcula calea de către o mașină NL. Apoi, pot calcula și -- pot face o altă mașină NL care calculează numărul, numărul de noduri accesibile? Deci, dacă pot testa dacă un nod este accesibil, îmi pot da seama câte noduri sunt accesibile? Acest lucru ar trebui să fie ușor. Aceasta este un fel de practică. Deci, dacă îmi pot da seama dacă nodurile sunt accesibile, da sau nu, atunci pot spune, îmi dau seama câte noduri sunt accesibile. Doar parcurgeți-le unul câte unul, testând dacă sunt accesibile și numărați pe cele care sunt. Asta e tot ce am în minte. Deci, începeți cu un numărător care este setat la 0 inițial. Și treceți prin fiecare dintre nodurile lui G unul câte unul. Și folosesc mașina mea NL care calculează calea. Asta vreau să spun prin această parte. Asa ca il testez. Dacă aparatul NL spune da, există o cale, atunci măresc contorul. Și dacă spune că nu există cale, atunci continui fără să măresc contorul. Acum, când rulez mașina mea NL pentru a calcula această funcție, acea mașină NL ar putea să pună la punct, ar putea respinge uneori pe unele ramuri. Asta e ok. am si eu voie. Sunt, de asemenea, un aparat NL. Eu calculez o valoare. Și s-ar putea, de asemenea, să pun pe unele ramuri. Deci, la sfârșit, voi scoate acel număr, OK? Deci, ceea ce voi dovedi în continuare este inversul. Și asta-- și asta este partea magică dificilă, că dacă pot calcula numărul, atunci pot face testul dacă nodurile individuale sunt conectate, au o cale de la s. OK, deci să vedem. Cineva întreabă dacă mașinile nedeterministe - deci ca M nu au voie să circule în buclă? Nu. Dacă o mașină, dacă oricare dintre aceste mașini, cum ar fi o mașină din NL, face bucle, va merge pentru totdeauna. Asta nu este permis. Deci fără buclă. Nu sunt sigur de ce este relevant, dar nicio buclă. Dar ceea ce mă îngrijorează mai mult este că înțelegi această teoremă aici. Cred că urmează un check-in. Să vedem. BINE. Acest lucru ar putea fi de ajutor. Deci, luați în considerare afirmația că complementul PATH este NL. Asta încercăm să dovedim și, de asemenea, că o mașină NL poate calcula funcția cale. Acestea vor fi fapte legate. Pe care o putem demonstra cu ușurință din cealaltă? Adică, ambele vor fi adevărate. Deci, într-un anumit sens, este banal. Dar vreau să știu, pe care o putem dovedi imediat, fără a lucra prea mult? Că pot rezolva această problemă PATH în NL, complementul problemei PATH în NL sau că pot calcula funcția cale în NL? Deci ce crezi? OK, aproape terminat aici? Da. Final. Nu v-ați descurcat bine. Asta e ok. De fapt, răspunsul corect este c. Cei mai mulți dintre voi înțelegeți că dacă pot rezolva funcția cale, deci valoarea da-nu, o pot folosi acum pentru a rezolva atât PATH, cât și complementul PATH. Asta pare mai clar. Dar să presupunem că pot rezolva problema complementului PATH în NL. Și mai știu că pot rezolva problema PATH în NL. Asta, am arătat deja. Așadar, cunoscând ambele, dacă mi se oferă un G, s și t, ceea ce pot face este să aleg în mod nedeterminist care dintre cele două direcții. Știi, aleg... O să ghicesc, ei bine, este în PATH, sau este în complementul PATH. Deci, există două căi diferite, nedeterministe. Unul dintre aceștia va sfârși mereu prin a respinge. Și asta va sfârși prin a deplasa. Cealaltă direcție va ajunge, uneori, să accepte și alteori să-și piardă. Și pe baza faptului că care parte ajunge -- una sau cealaltă va avea unele accept -- va fi acceptare. Și așa că cel care acceptă îmi va spune dacă să răspund da sau nu. Deci, de fapt, ambele direcții, ambele implicații urmează destul de ușor. BINE. Oricum, hai să încercăm să arătăm... aceasta este partea grea. Și avem cinci minute. Să vedem cât de departe putem ajunge. Deci această teoremă funcționează prin magie. Așa că a cam uimit mintea tuturor când a apărut prima dată. Deci, să vedem. Nu este chiar atât de greu. Dar este un fel de-- este cam sucit. Deci, să presupunem că o mașină poate calcula c, numărul, numărul accesibil de la s. O voi folosi pentru a rezolva calea, funcția cale, pentru a testa, da, pot scoate da dacă există o cale sau nu, nu există cale, pentru fiecare nod t. Deci, dacă știu câte noduri sunt accesibile, atunci pot rezolva acum pentru noduri individuale, ceea ce este ciudat că puteți face asta. Acum, nu vă spun cum să calculați c. Asta pentru mai târziu, la care probabil nu voi ajunge. Dar pretindeți-vă că ne putem da seama cumva care este numărul de noduri accesibile, OK? Deci, iată algoritmul meu nedeterminist pentru calea de calcul. În primul rând, voi calcula c, sau să presupunem că este dat c. Și acum, poate cel mai bun lucru de făcut este să încerci să-ți dai ideea din față. Ceea ce vom face, din moment ce avem puțin timp, ceea ce vom face este, să presupunem că vă spun, există, în acest grafic, 100 de noduri accesibile din s. Deci c este 100. Există 100 de noduri accesibile. Acum vreau să știu... spun, ei bine, nu prea... asta e foarte frumos. Dar aș dori să știu acest nod anume, t. Este accesibil de la s? Acum, sunt o mașină nedeterministă. Acum, dacă t ar fi accesibil, atunci mi-ar fi bine, pentru că nedeterminist, nici măcar nu mă interesează de 100. Iau, nedeterminist, pe vreo ramură, începând de la s, o să lovesc t. Și ramura aceea va spune da. Celelalte ramuri, poate vor scăpa. Dar o ramură va primi răspunsul corect. Problema este să presupunem că nu este accesibil. Atunci vrei ca vreo ramură să spună nu. Și cum ar putea acea sucursală să spună vreodată nu, dacă nu este sigur că nu este accesibil? Și cum poate fi sigură o ramură? Ideea este aceasta. Să presupunem că știu că există 100 de noduri accesibile. Ceea ce voi face nedeterminist este să ghicesc acele 100 de noduri, unul câte unul. Nu le poți stoca pe toate, pentru că ar putea fi... 100 ar putea fi un număr mare. O să le ghicesc unul câte unul. Am să le ghicesc. Și de fiecare dată când ghicesc un nod, voi dovedi că este accesibil ghicind calea care arată că este accesibil. Deci voi ghici 100 de noduri, voi demonstra că sunt accesibile și apoi voi vedea, nu dintre acele noduri accesibile? Dacă ar fi, ei bine, atunci l- aș fi găsit și aș ști să spun da. Dar dacă t nu a fost unul dintre cele 100 de noduri accesibile și știu că sunt doar 100 -- deci dacă t nu este unul dintre acele noduri -- cu alte cuvinte, dacă le-aș găsi pe toate și nu ar fi unul dintre ele, atunci știu că nu este accesibil. Și uite așa, folosind numărătoarea, pot fi sigur că anumite noduri nu sunt accesibile, pentru că doar le găsesc pe toate cele care sunt, dovedesc că sunt, verific dacă numărul este de acord cu ceea ce mi s-a dat și apoi spun nu, nu este accesibil, dacă nu este unul dintre acele noduri pe care le-am găsit a fi accesibile, ceea ce se adaugă la numărul dat. Asta e toată ideea. Desigur, cum obțineți numărul? Destul de ciudat, este cam aceeași idee repetată iar și iar. Dar cred că va trebui să facem asta data viitoare. Deci hai să scriem asta. Și îl vom folosi ca început al prelegerii de joi. Deci vom trece prin fiecare nod u, unul câte unul. Acum vom ghici, pentru fiecare nod, dacă există o cale către el sau nu. Așa că o voi numi fie p, fie n. Din nou, acesta este acum... gândiți-vă la cele 100 de noduri ale mele. O să ghicesc toate cele 100 de noduri. Voi alege nedeterminist o cale de la acel nod care cred că este accesibilă. Deci, dacă ghicesc un nod, există o cale. Voi confirma că există o cale prin alegerea nedeterminată. Dacă nu găsesc acea cale, doar resping puntea pe acea ramură. Dacă acea cale pe care am găsit-o chiar m-a condus la t, deci u, acel nod la care lucrez, este în prezent t, atunci știu să accept. Dar, altfel, voi număra numărul de noduri pe care le găsesc că sunt accesibile. Dacă am ghicit că nu ești accesibil, o să- l omit. La sfârșit, văd dacă numărul de noduri pe care le-am determinat sunt accesibile este de acord cu numărul meu inițial, c. Deci k este egal cu c sau nu? Dacă nu este egal, nu sunt egali, atunci nu am găsit toate nodurile accesibile. Nu am ghicit bine. Și așa am punte. Eu spun, ei bine, ramura proastă a nondeterminismului. Pur și simplu renunț. Dar o ramură a nondeterminismului va ghici toate nodurile corecte care sunt accesibile. Și apoi, dacă nu s-ar fi găsit deja a fi unul dintre ei, în acest moment, știu că nu este accesibil. Și așa pot ieși nr. BINE? Deci asta e totul. Ce este m? m este... da, bună întrebare. m este numărul de noduri ale graficului. Ar fi trebuit să spun asta. Deci nu vrei să mergi... nu vrei să intri într-o buclă. Așa că mai bine întrerupeți alegerea unei căi către o valoare limită. Deci o vei tăia la m, care este numărul de noduri, care va fi suficient de lung. De fapt, ne vom juca cu asta ceva mai târziu, dar... OK, să vedem. De unde știu că nu am vizitat același nod de două ori când număr? Pentru că voi trece prin toate nodurile într-o anumită ordine. Alege orice comandă. Nodurile apar într-o anumită ordine în reprezentarea graficului pe intrare. Deci orice ordin vechi... voi trece prin noduri în ordine. Prin urmare, nu voi vedea niciodată același nod de două ori. Ce înseamnă pasul 4? Deci, pasul 4 este -- pasul 4 înseamnă, pentru fiecare nod, bănuiesc că acel nod fie are o cale către el de la s, fie nu are o cale către el de la s. Așa că mă gândesc la asta, originalul... nu avem timp. Deci, de ce nu... sunt bucuros să discut despre asta în programul de lucru. Voi trece peste restul diapozitivelor de aici și voi revizui. Ne lipsește un check-in. Hai doar... Vreau să mă asigur că toată lumea are toate înregistrările aici. Deci, de ce nu doar-- dacă știm că NL este egal cu coNL, am arătat și noi-- am arătat că complementul 2SAT este NL complet. De asemenea, rezultă că 2SAT în sine este NL complet, deoarece NL este egal cu coNL. Așa că o să vă dau răspunsul la asta doar, pentru că vreau să finalizați acest sondaj. Totuși, unii dintre voi înțelegeți greșit. BINE. Așa că vă rog să răspundeți repede. Și apoi vom termina. Am terminat cu toții? Obțineți punctele de participare aici. Trei secunde. OK, se încheie. OK, nu contează. Așa că iată, am fugit peste. Îmi pare rău pentru asta. Scurtă revizuire. Asta nu am terminat. Aceasta este partea 5. Dar o vom termina data viitoare. OK, când arată că PATH este NL complet, trebuie să listăm și nodurile pentru construirea graficului. Slide-urile menționează doar... da, am cam omis asta. Dar da, poți doar să notezi toate nodurile. Din nou, dar și asta va ocupa doar spațiu în jurnal, așa cum ați observat. Da, din punct de vedere tehnic, atunci când scrii un grafic, notezi o listă a nodurilor și notezi o listă a marginilor. Am cam omis să scriu nodurile. Dar da, este la fel... nu contează. Așa că am să vă iau rămas bun de la voi toți. Mulțumesc.