[SCRÂTÂND] [FOȘTIT] [CLIC] MICHAEL SIPSER: Să revenim la complexitatea spațiului. Așa că doar pentru a trece în revistă ceea ce am făcut de la ultima prelegere, care pare demult, dar a fost cu doar două zile în urmă, ne-am uitat la acele trei teoreme, care aveau toate practic aceeași dovadă. Unul era despre problema scarii, în care încercați să vedeți dacă puteți trece de la un șir la altul, schimbând câte un simbol pe rând. Și toate șirurile erau în limbajul unui automat finit, sau aveai o regulă rezonabilă pentru a spune care sunt șirurile valide, care nu. Și apoi ne-am construit pe această idee. Am arătat teorema lui Savitch , că trecerea de la orice mașină nedeterministă la o mașină deterministă nu face decât să pătrați cantitatea de spațiu. Și apoi am demonstrat în sfârșit că TQBF, această problemă despre formule booleene cuantificate, testând dacă sunt adevărate, că acea problemă este completă pentru PSPACE. Așa că vom construi azi din ultima teoremă și vom vorbi despre o altă problemă completă și, de asemenea, vom arăta o legătură între PSPACE și testarea părții care poate câștiga în anumite tipuri de jocuri. Și apoi, la sfârșitul prelegerii, a doua jumătate a prelegerii, vom vorbi despre scufundarea mai adânc în complexitatea spațiului. Vom vorbi despre o altă parte a spațiului parametrilor unde, în loc să ne uităm la spațiul polinomial, vom vorbi despre ceea ce se întâmplă dacă aveți spațiu logaritmic, care este un alt punct natural de analizat pentru complexitatea spațiului. Dar la asta vom ajunge după pauză. Vorbește despre complexitatea jocului și jocuri-- așa că, când eram mic, obișnuiam să ne jucăm, eu și surorile mele, jucam un joc numit Geografie. Nu știu câți dintre voi ați auzit-o sau poate că poartă un alt nume. Dar a fost un joc în principiu despre cuvinte și locuri. Și are un set de reguli foarte simplu. Să zicem că au fost doi oameni. Alegeți pe rând numele locurilor. Și apoi fiecare persoană trebuie să aleagă un loc care începe cu litera cu care s- a încheiat locul persoanei anterioare . Deci, de exemplu, ai doi oameni care joacă. Poate că sunteți de acord cu un loc de plecare, cum ar fi un oraș important din apropiere, cum ar fi Boston. Deci un jucător, primul jucător, alege Boston. Și apoi, după aceea, următorul jucător trebuie să aleagă un loc care începe cu N, pentru că Boston se termină cu N. Și așa poate că Nebraska ar fi un posibil răspuns la Boston. Și atunci primul jucător ar trebui să răspundă la asta cu un loc care începe cu un A, pentru că Nebraska se termină cu un A, poate Alaska, care începe și cu A, se termină cu A. Deci, atunci Arkansas, poate, ar fi un mod rezonabil. răspuns la asta. Și apoi se termină cu S, deci San Francisco, și apoi așa mai departe, și așa mai departe. Și, desigur, doriți să interziceți oamenilor să refolosească nume pentru că atunci veți intra într-o buclă. A spune „Alaska”, „ Alaska”, „Alaska” nu va face jocul foarte interesant, așa că trebuie să interziceți această posibilitate. Numele nu pot fi refolosite. Pot fi folosite cel mult o dată. Și apoi, în cele din urmă, o parte sau cealaltă va rămâne fără nume și nu va avea - fie din cauza lipsei cunoștințelor lor geografice, fie poate tocmai ați epuizat toate posibilitățile - și nu va avea un răspuns bun. . Și acea persoană va rămâne blocată. Și acea persoană este învinsul. Cealaltă persoană a câștigat jocul. Deci obiectivul este să încercăm să nu rămânem blocat. Deci haideți să aruncăm o privire. Mă voi gândi la acel joc într-un mod puțin mai abstract, formalizat. Deci notați toate locurile legitime. Ele devin noduri ale unui grafic, așa cum am arătat aici. Și apoi tragi o margine de la un nod la altul dacă asta corespunde unei mișcări legale în joc, o etapă legală a jocului. Așadar, Boston se conectează la locuri care încep cu N, cum ar fi New York și Nebraska. Deci prima persoană ar putea alege Boston. A doua persoană ar putea alege oricare dintre aceste două, și apoi înapoi la prima persoană. Dacă ar alege Nebraska, ar putea alege Arkansas. Ei pot alege Alaska și așa mai departe, așa cum am descris. Credeți sau nu, de fapt am jucat acest joc. Îmi amintesc că am jucat acest joc când eram copil. Asta era, desigur, înainte de a avea „League of Legends” și alte chestii distractive, dar așa făceau copiii. Deci, oricum, doar pentru a o pune pe diapozitiv, regulile sunt... presupunând că avem doi jucători, îi vom numi Jucătorul I și Jucătorul II. Jucătorul I merge primul. Și aleg pe rând locurile care încep cu litera care se termină pe locul precedent, fără repetări permise. Și primul jucător blocat pierde, persoana care nu are o mișcare de făcut. Deci, ceea ce ne vom uita astăzi este o versiune generalizată a acesteia, în care vom elimina doar numele, dar vom lăsa doar graficul de bază. Și noi numim asta „geografie generalizată”. Deci, aici, asta poate fi jucat pe orice grafic direcționat. Tu iei numele nodurilor. Acum ai doar un grafic arbitrar. Veți desemna un anumit nod ca nod de pornire. Și apoi jucătorii se pe rând urmând acele margini. Și pentru că veți interzice să aveți bucle care reutilizează nodurile, ceea ce veți face este, lucrând împreună, veți construi o cale simplă în acel grafic. Calea simplă urmează doar acele margini și nu se intersectează niciodată. Iar primul jucător blocat este învinsul. Deci celălalt este câștigătorul. Așa că o vom numi „geografie generalizată”. Și ne vom uita la complexitatea de calcul de a decide, pentru un anumit grafic și punct de plecare , care parte ar câștiga dacă ambii jucători ar juca optim, cel mai bine posibil. Și vom numi acea problemă GG sau vom privi limba asociată. Deci aici este un grafic și nodul de pornire. Și vrei să spui că perechea este în limba GG dacă primul jucător, Jucătorul I, care trebuie să joace la acel nod A pentru a începe, are o victorie forțată în acel joc de geografie generalizată pe acel grafic care începe cu A. Din nou, ce Adică printr-o victorie forțată... nu voi defini asta în mod formal, deși am putea face asta... nu este greu de făcut. Dar o victorie forțată este numită și „strategie câștigătoare”. Asta înseamnă doar că, dacă ambele părți joacă în mod optim, vor juca cel mai bine posibil -- nu din capacitatea lor, mă refer la cel mai bun joc posibil -- atunci acel jucător pe care l- ar câștiga în continuare. Jucătorul II nu poate face nimic pentru a împiedica Jucătorul I să câștige dacă Jucătorul I are o strategie de câștig sau o victorie forțată. S- ar putea să fi văzut, de exemplu... există exemple în acest sens că... Adică, nici nu știu dacă mai există, dar odinioară era în ziar. Odinioară erau exemple de table de șah și începeau de la o anumită poziție. Și ei spuneau: „Alb să câștige în trei”. Și asta înseamnă că albul are o victorie forțată. Indiferent ce face negrul, albul va sfârși prin a câștiga. Dar trebuie să te gândești care este strategia. Poate că nu este atât de evident să te gândești care sunt mișcările potrivite pe care le face albul. Dar ideea este că indiferent ce ar face negrul, albul ar ajunge să câștige. Și ceea ce poți arăta-- nu vom face asta-- dar pentru o clasă de jocuri care include această geografie generalizată, fie o parte, fie cealaltă, se va garanta că va avea o victorie forțată. Acest lucru nu este neapărat adevărat pentru toate jocurile posibile, evident, dar pentru o clasă mare de jocuri, o parte sau cealaltă este garantată să aibă o strategie câștigătoare sau o victorie forțată. Așa că haideți doar să trecem în revistă , pentru că acest lucru va fi esențial pentru prima jumătate a prelegerii -- pentru a înțelege ce înțelegem prin joc și ce înțelegem printr-o parte sau cealaltă pentru a avea o victorie forțată. Și ceea ce vom arăta este că GG este complet PSPACE, că problema dat fiind unul dintre aceste grafice și un punct de plecare , a afla dacă Jucătorul I are o victorie forțată sau este Jucătorul II care are o victorie forțată? Care parte este garantată să câștige în condiții de joc optim? Aceasta este o problemă completă PSPACE. Și haideți să verificăm puțin asta. Așa că vă voi da un exemplu foarte mic de joc de geografie generalizată. Trebuie să vă dați seama dacă Jucătorul I sau Jucătorul II este cel care are câștigul forțat, strategia câștigătoare sau poate niciunul sau ambele. Acestea sunt cele patru opțiuni. Și înțelegeți că Jucătorul I trebuie să joace aici, pentru că acesta este locul de plecare al acestui joc de geografie generalizată. Deci, depinde de Player II să continue. Bine, deci hai să lansăm acel sondaj. Va trebui să te gândești puțin la asta și să-mi spui ce crezi. Care parte are o victorie forțată? Care jucător face prima mutare? Este Jucătorul I care face prima mutare, iar Jucătorul I joacă, așa cum v-am arătat aici, acesta este Jucătorul I care joacă la A. Deci Jucătorul I îl alege pe A și apoi Jucătorul II trebuie să aleagă unul dintre acești doi. Bine, cred că suntem sfârșitul sondajului. Toți sunt înăuntru? Alege ceva. Nu v-ați descurcat bine la acest sondaj. Cel puțin nu prea mulți dintre voi l-ați ales pe D. Este puțin liniștitor pentru că nu puteți avea ambii jucători să câștige forțat. Am spus că în astfel de jocuri , o parte sau cealaltă va avea o victorie forțată, așa că nici C nu este o alegere foarte bună. Deci poate ar trebui să petreceți mai puțin timp citind e-mailul și mai mult timp ascultând prelegerea. Răspunsul corect real este B. Jucătorul II, care, evident, este o poziție minoritară aici - Jucătorul II are câștigul forțat. Să înțelegem de ce. Deci Jucătorul I joacă aici. După cum am spus, aceasta este prima mișcare. Jucătorul II poate lua fie nodul superior, fie nodul inferior. Jucătorul II ia nodul superior, apoi Jucătorul I nu are de ales decât să ia nodul din dreapta, iar acum nu mai este mișcare pentru Jucătorul II. Deci Jucătorul II va pierde dacă Jucătorul II ia nodul superior, alegerea superioară acolo. Pentru că Jucătorul II va merge aici, Jucătorul I va merge acolo și jocul se va termina. Și Jucătorul I va fi câștigat pentru că Jucătorul II a fost blocat. Cu toate acestea, Jucătorul II a avut o altă opțiune. Jucătorul II ar fi putut să coboare și aici. Deci Player II, dacă s-a jucat aici, lucrurile arată mult mai bine pentru Player II. Dacă jucătorul II merge aici, mutarea jucătorului I este forțată, merge aici. Dar acum, a mai rămas o mișcare pe care Jucătorul II ar putea-o face. Deci Jucătorul II merge aici, eu merg acolo, Jucătorul II merge sus. Și acum Jucătorul I este blocat. Deci, este alegerea Jucătorului II , Jucătorul II poate face o mișcare care va duce la blocarea jucătorului I , pentru că asta este natura a ceea ce înțelegem prin a avea o strategie câștigătoare. Există o modalitate de a garanta dacă joci optim și, cu siguranță, joci optim, înseamnă că vei face mișcarea inferioară. Atunci vei lua asta. Deci, în condiții de joc optim, Jucătorul II va câștiga acest joc și astfel Jucătorul II are o strategie câștigătoare. Are o victorie forțată. Deci văd. Așa că nu voi defini „jucatul optim”. Sunt câteva întrebări aici despre asta. Am de gând să... O să o las oarecum informală, dar am putea face totul precis. Nu cred că ar fi clar pentru a trece printr-o definiție precisă a acestui lucru. Nici nu trebuie să ne gândim la asta în termeni de joc optim. Puteți spune că un jucător are o victorie forțată dacă are mișcări pe care le-ar putea face ca răspuns la fiecare mișcare posibilă pe care o poate face adversarul și care va garanta că va ajunge să câștige. Deci nici măcar nu trebuie să vorbiți despre optimitate aici. Vorbește doar despre fiecare adversar posibil. Fiecare adversar posibil va pierde în fața cuiva care are o strategie câștigătoare și urmează acea strategie. Văd că a existat o confuzie cu privire la cine mergea primul și așa mai departe. Mă bucur. Acesta a fost o parte din motivul pentru care am dat această verificare, doar ca să sperăm să clarific unele dintre acele puncte. Deci Jucătorul I joacă aici, apoi Jucătorul II pleacă. Și am primit câteva comentarii că unii oameni erau confuzi cu privire la ce înseamnă acesta unde se mișcă prima persoană. Să sperăm că este mai clar. În regulă, deci să trecem mai departe pentru că vom petrece un timp demonstrând ceva despre geografia generalizată în aceste grafice. Deci hai sa continuam. Deci, pentru a face legătura între jocuri și complexitate, va trebui să vorbim despre o problemă, una legată de una pe care am văzut-o deja, unde putem reformula acea problemă ca un joc. Și asta va fi o problemă cu formulele booleene cuantificate numite „Jocul cu formule”. Deci, acesta este un alt joc acum, nu unul pe care probabil să ajungi să-l joci. Dar într-un sens în care veți vedea, acesta este încă un joc rezonabil în care doi jucători pot juca unul împotriva celuilalt. Și unul dintre ei va sfârși prin a câștiga, iar unul dintre ei va sfârși prin a avea... unul sau altul va avea o strategie de câștig. Deci, să înțelegem care este jocul. Jocul se joacă pe o formulă. Deci scrieți o formulă booleană cuantificată. Amintiți-vă, am vorbit despre asta pentru câteva prelegeri acum. Este o grămadă de cuanti-- variabile cu cuantificatori. Și apoi există o parte care nu are cuantificatori, pe care o puteți pune oricând în formă normală conjunctivă dacă doriți. Dar în scopul acestei discuții de până acum, nu contează. Mai târziu, ne vom dori de fapt să fie în CNF. Dar deocamdată avem doar o formulă. Și asociat cu această formulă există un joc, într-un sens foarte firesc. Deci, în primul rând, vor fi doi jucători. Dar acum numele acelor jucători vor fi Player Exist și Player For All. Și așa merge jocul - ambii jucători vor alege valori pentru variabile. Ei vor spune că variabila x1 este adevărată, variabila x2 este falsă, variabila x3 este falsă, variabila x4 este adevărată. Și așa merg mișcările jocului. Ei doar atribuie valori variabilelor, astfel încât, în cele din urmă, tuturor variabilelor li se atribuie o valoare booleană. Și așa ajungem cu o misiune. Dar înainte de a ajunge la această etapă, ce jucători pot alege ce variabile? Și modul în care funcționează este că jucătorul Exist va atribui valori variabilelor Exist. Deci Exist va alege x1 și x3 și le va atribui valori. Jucătorul For All va atribui valori variabilelor care au atașat un cuantificator For All. Deci, în acest caz, jucătorul For All va alege valoarea pentru variabila x2. Se estompează aici. Și ordinea jocului este conform ordinii de apariție a calificărilor în formulă. Deci, așa cum am scris- o în această formulă specială, este Exist x1 - așa că Exist va alege valoarea pentru x1. Apoi, rândul lui For All. For All va alege valoarea x2. Apoi, va fi Exist alege valoarea pentru x3 și așa mai departe, până când ajung la sfârșit și toate variabilele au fost atribuite valorii de o parte sau de alta. Și acum jocul s-a terminat. Deci, ce rămâne este să înțelegem cine a câștigat în acel moment. Și modul în care spunem cine a câștigat este Exist câștigă dacă, în final, această parte psi, care este partea fără cuantificatori, a ajuns să fie satisfăcută de acea misiune pe care cei doi jucători au ajuns împreună să o aleagă. Și apoi For All va câștiga dacă acea parte a formulei nu este satisfăcută. Așa că lasă-mă să scriu asta aici. După ce variabilelor li s-au atribuit valori, determinăm câștigătorul. Exist câștigă dacă misiunea care a construit în cooperare împreună a satisfăcut psi și, în caz contrar, For All, dacă nu satisface psi. Așa că gândiți-vă la asta în acest fel - Exist înseamnă alegerea valorilor acelor variabile. El încearcă să facă această parte a formulei satisfăcută, încercând să satisfacă această parte a formulei. For All alege valori, dar încearcă să facă nesatisfăcut această parte a formulei. Deci sunt în opoziție unul cu celălalt. Și până la urmă, unul dintre ei va fi reușit, iar celălalt va fi eșuat. Și acum, gândindu-ne la asta ca pe un joc, în funcție de formulă, o parte sau cealaltă va avea capacitatea de a o domina pe cealaltă și de a câștiga întotdeauna. Și deci întrebarea este, care parte are această capacitate de a câștiga întotdeauna? Care parte are strategia câștigătoare? Desigur, va depinde de formulă. Unele formule, jucătorul Exist va fi cel care are strategia câștigătoare. Și alte formule, jucătorul For All va fi cel care are strategia câștigătoare. Și din punct de vedere computațional, am dori să facem această determinare. Care parte va câștiga pentru o anumită formulă? Și există o modalitate foarte, foarte drăguță și, de fapt, foarte ușoară și simplă de a înțelege asta, deoarece ne-am confruntat deja cu această problemă înainte. Problema determinării cărei părți are o victorie forțată este exact același lucru cu a determina dacă această formulă booleană cuantificată este adevărată, deoarece jucătorul Exist are o câștig forțat atunci când acea formulă-- permiteți-mi să o spun din nou-- jucătorul Exist are un câștig forțat. câștigă atunci când formula este adevărată. Deci, dacă această formulă booleană cuantificată ar fi o formulă booleană cuantificată adevărată, atunci Exist este garantat că va putea câștiga acel joc dacă își joacă mâna corect. Dacă aceasta este o formulă falsă, jucătorul For All va putea întotdeauna să câștige dacă își joacă mâna corect. Deci de ce este asta? Urmează într-adevăr aproape fără a lucra deloc. Această dovadă, deși pare superficial că ar putea să nu fie atât de ușor de demonstrat, rezultă dintr-un motiv foarte simplu, deoarece sensul a ceea ce înseamnă pentru Exist să aibă o strategie câștigătoare este exact surprins de semantica cuantificatorilor. Să vedem ce înseamnă asta. Ce înseamnă că Exist are o victorie forțată, să spunem aici sus? Asta înseamnă că Exist are o mișcare pe care ar putea-o face, că Exist poate alege o anumită valoare pentru x1-- așa că a existat o modalitate de a atribui x1, astfel încât indiferent ce face adversarul, indiferent ce face For All, va exista un răspuns pe care Exist îl poate face, o anumită atribuire la x3, astfel încât, indiferent de ce face For All, va fi o atribuire la următoarea variabilă și așa mai departe, astfel încât acest lucru să fie adevărat. Așa că lasă-mă să spun asta din nou cumva. Nu am simțit că a ieșit foarte clar. Deci, Exist are o strategie câștigătoare exact atunci când există o anumită atribuire la x1 pe care Exist o poate face astfel încât, indiferent de ce sarcină pe care For All o face lui x2, există o anumită atribuire x3, astfel încât indiferent ce atribuire pe care For All o face lui x4 și așadar on, face acest lucru adevărat. Asta înseamnă pentru Exist să aibă o strategie câștigătoare. Exact asta spun cuantificatorii în primul rând. Deci, chiar și fără a face nimic, puteți vedea că „Exist are o strategie câștigătoare” înseamnă exact același lucru cu care formula booleană cuantificată este adevărată. Așadar, a face testul pentru care parte are o strategie câștigătoare este același lucru cu a testa dacă formula este adevărată. Așa că permiteți-mi să încerc să apelez la chat înainte de a trece la altceva. Începem. Așa că primesc câteva întrebări despre ordinea jocului și despre alternanța cuantificatorilor aici. Așadar, modul în care o arăt este că cuantificatorii alternează întotdeauna -- Există, pentru toți, există, pentru toți. Asta chiar nu contează. Puteți avea mai multe Exist la rând, iar asta ar corespunde cu Exist care face mai multe mișcări la rând înainte de a- l întoarce la For All. Dar, alternativ, am putea adăuga variabile suplimentare care nu joacă niciun rol în psi. Și sunt doar un fel de variabile fictive care servesc ca distanțiere, așa că dacă aveți două Exist la rând și nu vă place asta, puteți doar să adăugați un For All din unele variabile pe care nu le mai vedeți niciodată între ele. Așa că puteți face întotdeauna ca acesta să fie alternativ dacă doriți. OK, de asemenea, întrebare-- diferența dintre phi și psi. Deci psi este partea de aici care nu are nici un cuantificator. Deci, modul în care scriem întotdeauna QBF-urile noastre este că sunt cuantificatori de frunte cu variabilele și toate variabilele trebuie să fie în domeniul de aplicare a uneia dintre variabilele cuantificate. Deci nu există variabile libere care să fie necuantificate în QBF-urile noastre. Și astfel, toate aceste QBF-uri au o serie de cuantificatori și apoi o parte fără cuantificatori, deci partea logică booleană. Psi aici este partea logică booleană. Și phi este totul împreună cu cuantificatorii. Așa că nu sunt sigur că înțeleg unele dintre acestea... de ce nu ca jucătorul For All să câștige forțat? Jucătorul For All ar putea avea o victorie forțată. O parte sau cealaltă parte are garantat o victorie forțată. Deci, dacă Exist nu are o victorie forțată, atunci For All va avea o victorie forțată. Nu am de gând să dovedesc asta. Aceasta este o dovadă destul de simplă prin inducție, pe care nu o voi trece. Luați-o ca pe un fapt. Cineva se întreabă, de ce For All vrea să nu satisfacă această expresie, partea psi? Ei bine, așa am configurat jocul. Pentru a face acest lucru să corespundă cu TQBF, doar adevărul acestei expresii, vrem să facem Exist să încerce să satisfacă această parte și For All să încerce să nu fie satisfăcut pentru că asta funcționează. Nu sunt sigur ce altceva, ce altceva aș putea răspunde acolo. Voi răspunde aici la câteva dintre cele mai elementare întrebări. Cineva întreabă, de unde știm câte variabile să folosim? Deci variabilele sunt variabilele formulei. Deci cineva o să- ți înmâneze o formulă. Va avea x1 până la x10, indiferent de formula respectivă, un număr de variabile. Și astfel jocul va avea 10 mutări. Dacă cuantificatorii alternează, atunci mișcările vor alterna, dar oricare ar fi modelul cuantificatorilor va fi modelul mișcărilor. Deci Exist va urmări locurile în care apare cuantificatorul Exist, iar For All va urmări locurile în care apare cuantificatorul For All. Deci, dacă aveți Exist, For All, Exist, For All, Exist se va muta primul, apoi For All se va muta, apoi Exist se va muta, apoi For All se va muta. Împreună, aleg valori pentru variabilele lor respective cu obiectivele lor opuse. Exist încearcă să facă partea psi satisfăcută. For All încearcă să evite să fie satisfăcut, să facă ca misiunea să nu satisfacă acea parte. Și dacă te gândești la ce înseamnă asta, doar în ceea ce privește sensul, va însemna exact același lucru, că formula este adevărată. Deci, oricum, dacă nu... hai să vedem. Nu știu dacă mai sunt întrebări la care pot încerca să răspund aici. Tot despre numărul de variabile este vorba. Fiecare formulă va defini un joc diferit. Vezi formula. Deci formula, oricât de mare, poate avea 50 de variabile, poate avea două variabile. Ei bine, vom face un exemplu. Poate asta va ajuta. Următorul check-in, care va avea loc destul de curând -- ar putea fi de fapt acum -- vă vom da un exemplu. Așa că vom vedea cine înțelege și cine nu. Deci hai să continuăm aici. Prin urmare, problema determinării dacă Exist are un câștig forțat este exact problema TQBF, deoarece Exist are un câștig forțat exact atunci când formula este adevărată. Și ceea ce vom arăta este că TQBF este un timp polinom reductibil la geografie generalizată, dar conceptual, ne vom gândi la TQBF acum ca un joc pentru că așa este configurată geografia generalizată. Deci, având în vedere o formulă ca aceasta, vom construi o instanță de geografie generalizată. Vom construi un grafic în care jocul pe acel grafic va imita jocul în jocul cu formule. Deci, efectuarea mișcărilor în acel grafic va corespunde cu setarea variabilelor adevărate și false, deoarece graficul va fi special conceput pentru a forța acel comportament. Deci cred că avem un check-in. Da, deci să vedem cum... Vă sugerez să acordați atenție acestui check-in, să încercați să vă gândiți la asta și să o rezolvați, pentru că cred că asta vă va ajuta face legătura între adevărul formulei și Exist având o strategie câștigătoare. Deci, dacă luați această formulă aici, aceasta este o formulă specială, există x pentru tot y, bla, bla, bla. Va fi asociat acelei formule, un joc de formule în care primul Exist se mută, atribuie o valoare pentru x și, în funcție de această valoare, For All se va muta și va atribui o valoare pentru y. Și după ce s-a terminat, această parte de aici fie va fi adevărată, fie falsă, fie va fi satisfăcută, fie nesatisfăcută. Și vreau să știu, poate Exist să găsească întotdeauna o modalitate de a garanta că această parte va fi satisfăcută sau For All poate găsi întotdeauna o modalitate de a garanta că această parte nu este satisfăcută? Așa că trebuie să te uiți la această formulă pentru a înțelege care parte va ajunge să reușească. Deci, dacă nu sunteți clar cu privire la reguli, priviți înapoi aici. Exist încearcă să facă această parte satisfăcută. For All încearcă să facă această parte nesatisfăcută. Dar niciunul dintre ei nu are total avantaj, deoarece Exist alege una dintre variabile, For All alege cealaltă variabilă. Dar o fac într-o anumită ordine. First Exist va alege, apoi For All va alege. Deci așa funcționează jocul: Exist alege o valoare, apoi For All alege o valoare și apoi vezi cine câștigă. Deci cine câștigă? Cine are garantat că va câștiga? Ne putem asigura că Exists câștigă întotdeauna sau ne putem asigura că For All câștigă întotdeauna pentru această formulă specială? Deci aici sunt doar două variabile. Poți să te gândești la asta în oricare din două moduri: strict vorbind, pur ca un joc, sau poți să te uiți, să înțelegi dacă formula este adevărată sau nu. Sunt moduri echivalente de a privi problema. De fapt, într-un anumit sens, este la fel. Asta încerc să transmit. Să te gândești la asta ca pe un joc sau să te gândești la asta în termeni de cuantificatori... nu are nicio diferență. Aproape terminat aici. Deci în regulă, ultimul apel. Închiderea sondajului. Cred că ăsta l-ai luat. Te-ai descurcat destul de bine. Deci răspunsul corect este jucătorul For All are o strategie câștigătoare, are o victorie forțată. Și, de asemenea, în mod similar, expresia, phi este falsă. Pentru că dacă încerci să găsești niște x astfel încât indiferent ce ai alege, asta va fi adevărat, asta va fi satisfăcut, nu ai noroc. Pentru că dacă faci x adevărat, atunci... acum sunt confuz. Ce se întâmplă. Dacă faceți x adevărat, atunci bara x este falsă, deci bara y trebuie să fie adevărată. Acum sunt complet confuz. Oh nu. Dacă faci x adevărat, trebuie să lucrezi For All y. Deci acest lucru este clar fals. Dacă faceți x adevărat, atunci această bară x va fi falsă și nu este cazul ca pentru fiecare y, setarea pentru y-- deoarece y este forțat aici. y va trebui să fie adevărat. bara y va trebui să fie adevărată, deci y va trebui să fie falsă. Deci, dacă încercați din nou să faceți x fals -- poate că la asta trebuie să vă gândiți mai întâi -- dacă faceți x fals, veți rămâne blocat la prima clauză, deoarece trebuie să funcționeze pentru ambele setări ale lui y. Dar poate că este mai bine să te gândești la asta ca pe un joc. Indiferent ce face x, y va avea o modalitate de a face una dintre aceste două clauze nesatisfăcute. Deci, dacă x este adevărat, putem seta y pentru a face a doua clauză nesatisfăcută, iar dacă x este fals, y poate fi atribuit pentru a face prima clauză nesatisfăcută. Deci, oricum, răspunsul corect este că jucătorul For All are aici strategia câștigătoare. Și la sfârșitul zilei, nu este esențial să înțelegi această corespondență, dar atunci, dacă nu înțelegi prea bine asta, va trebui să asumi încredere că jocul cu formule este același cu TQBF pentru că asta vom folosi. Și apropo, aș vrea să menționez și aici că această corespondență între jocuri și cuantificatori este ceva pe care matematicienii îl folosesc tot timpul. Pentru că dacă aveți o expresie care apare adesea în matematică, unde există o serie întreagă de cuantificatori în fața unei afirmații, este foarte greu pentru oricine să-și facă o idee despre ce înseamnă asta. Dacă aveți șase cuantificatori alternanți, ceea ce se întâmplă adesea în matematică -- veți avea enunțuri care au o mulțime de alternanțe cu cuantificatori -- foarte greu să vă dați o idee despre ce înseamnă asta. Dar dacă te gândești la asta ca la un joc, este mult mai intuitiv. Și este complet echivalent să ne gândim la cuantificatori. Mergeți înainte și înapoi între cuantificatori și jocuri. Oricum, să ne uităm la reducere, construcția care arată geografia generalizată este completă. Puțin mai mult decât credeam... Vreau doar să mă asigur că toată lumea este alături de mine în asta. Deci, de ce nu sunăm la pauză acum, apoi ne vom întoarce și ne vom uita la construcție după aceea. Deoarece construcția în sine va dura aproximativ 10 minute , descoperiți cum să reduceți TQBF și să construiți un grafic care simulează formula. Așa că voi trece direct la... și ne vom întoarce. Așa că nu ezitați să puneți câteva întrebări și pregătiți-vă pentru a ne scufunda într-o construcție pentru reducerea TQBF la geografie generalizată. Deci, este o întrebare interesantă despre care este relația dintre o formulă și când schimbați ordinea cuantificatorilor. Cel care întreabă se întreabă, asta se referă cumva la negarea părții fără cuantificatori, a părții fără cuantificatori? Și nu cred că aceasta este corespondența potrivită. De fapt, există o relație. Când spui „ există pentru toți”, este de fapt o afirmație mai puternică decât a spune că „ există pentru toți”. Și, în general, asta implică de fapt -- existe x pentru un y implică pentru un y există un x, pentru că ceea ce spui este că, dacă există un x pentru un y, există un x care funcționează pentru fiecare dintre y. Dacă spui că pentru un y există un x, alegerea acelui x poate depinde de y. Deci există o conexiune, dar trebuie să vă gândiți bine ce înseamnă pentru a înțelege acea conexiune. Nu va trebui să știți asta pentru a procesa ceea ce vom face, dar poate doar vă ajută să vă gândiți la asta. Alte intrebari aici. Cred că nu avem timp aici. Deci, să revenim la prelegerea noastră. Așa că mă voi întoarce. Sper că asta nu va prăbuși totul. Iată-ne. Deci acum vom reduce TQBF la geografie generalizată. Suntem toți împreună acum? BINE. Așa că o să ilustrez această construcție, care este o construcție foarte frumoasă, de altfel. O să ilustrez această construcție doar făcând un exemplu, sau un exemplu parțial, dar cred că vă va da ideea. Deci, înțelegeți ce încerc să fac aici, este că încep cu o formulă booleană cuantificată. Deci aici este. Voi presupune că este în formă normală conjunctivă, pe care o pot converti oricând în acea formă, poate adăugând câteva variabile suplimentare, dar fără a face ceva prea drastic. Și așa că acum, pornind de la acea formulă, acum voi construi un grafic, în care jocul de geografie pe acel grafic -- care înseamnă, amintiți-vă, luarea pe rând, alegerea nodurilor care formează o cale -- va corespunde cu jocul cu formule, care este alegerea variabilelor acelei formule. Și atunci vrei... dacă jucătorul Exist câștigă în formulă, atunci Jucătorul I ar trebui să câștige în jocul de geografie. Deci, iată cum va arăta graficul. Așa că încearcă să urmezi asta. Deci vor fi un fel de două părți, una care va corespunde variabilelor și cealaltă parte care va corespunde clauzelor. Și astfel, pentru fiecare variabilă, voi avea aici o structură de diamant. Deci, există un mic lucru de pornire care va fi unic pentru prima variabilă. Dar apoi fiecare variabilă va avea o mică structură de diamant aici. Și vor fi atașate unul la altul. Și vom înțelege ce înseamnă asta când vom juca geografia pe această bucată a graficului, dar să înțelegem mai întâi structura. Deci acesta este nodul de pornire. Și acum, aici Jucătorul I va juca rolul Exist. Jucătorul II va juca rolul For All. Și, de fapt, o să identific asta. Așa că o să sun-- pentru că va fi util doar să mă gândesc la Jucătorul I ca fiind jucătorul Exist. Deci, jucătorul Exist va juca pe acest grafic. Jucătorii Exist și For All se vor juca pe grafic. Sunt doar jucătorii I și II. Deci, jucătorul Exist, Jucătorul I, după reguli, trebuie să aleagă nodul de pornire. Și acum este mutarea jucătorului II, mutarea jucătorului For All. Acum, dacă sunteți cu mine pe acest grafic, mișcarea jucătorului For All nu este acum foarte interesantă pentru că este forțată. Trebuie să meargă aici, pentru că din nou, ei doar aleg nodurile unei căi simple în acest grafic. Deci, jucătorul For All, Player II, For All, trebuie să meargă aici dacă Exist a început de acolo. Acum este rândul jucătorului Exist. Și acum se întâmplă ceva interesant. Jucătorul Exist are de ales - poate merge la stânga sau la dreapta. Există două posibilități. Și apoi, după aceea, este rândul jucătorului For All , care este, din nou, doar forțat. Până acum, For All nu a avut multe lucruri interesante de făcut în acest sens, nu a trebuit să se gândească bine. Deci, indiferent dacă Exist a mers la stânga sau la dreapta, mișcarea jucătorului For All este forțată și ajunge aici. Și acum este rândul acestui jucător. Și din nou, acesta este unul ușor. Oh, înainte să fac asta, să ne uităm doar la cum ar putea merge piesa. Așa că primele două mișcări, așa cum sugeram eu, Exist merge aici și apoi For All merge acolo. Voi ilustra posibilele jocuri prin acest grafic, urmărindu-le în verde. Deci acum Exist merge aici, For All merge acolo. Aceștia au fost forțați. Dar acum, spune jucătorul Exist , ar putea fie să meargă în această direcție, fie ar putea merge așa. Deci acestea sunt două moduri diferite posibile de a juca jocul pe care îl construim. Și acum, cui este rândul aici? Acesta a fost jucătorul For All ales pe acesta, deci următorul turn este jucătorul Exist, iar asta este forțat. Dar acum observă-- acum, pentru prima dată, jucătorul For All trebuie să se gândească, pentru că jucătorul For All poate merge fie la stânga, fie la dreapta, deci poate să meargă fie la stânga, fie la dreapta. Și apoi va exista o secvență a acestor structuri de diamant, în care acestea sunt construite astfel încât, alternativ, fie Exist să aibă de ales, fie jucătorul For All să aibă de ales, până când ajungi până la capăt. Acesta este graficul pe care l-am construit până acum. Acum, dacă ne-am opri aici, atunci oricine a ajuns în acest moment, indiferent dacă a fost Exist sau For All, ar fi câștigător pentru că nu are unde să meargă adversarul. Desigur, asta nu ar fi foarte interesant. Deci, vor fi mai multe lucruri pe care le vom adăuga, care vor corespunde clauzelor. Acum, cum să ne gândim la ce s-a întâmplat până acum? Poate că unii dintre voi ar putea ghici că, atunci când jucătorul Exist de aici are de ales, ar fi putut să plece fie la stânga, fie la dreapta, asta va corespunde -- pentru că ar trebui să imite jocul cu formule -- asta va corespunde cu Există un jucător în formulă care alege variabila fie adevărată, fie falsă. Deci, la stânga sau la dreapta va corespunde adevărat sau fals. Deci, să spunem în mod arbitrar, stânga va corespunde alegerii adevărate și dreapta va corespunde alegerii false. Deci, modul în care l-am setat până acum este Exist a ajuns să aleagă prima variabilă false, apoi For All a ales a doua variabilă false. Și a n-a variabilă a fost, de asemenea, setată false. Totul a fost setat fals până acum. Cine știe ce s-a întâmplat aici, desigur, așa că doar pentru a înțelege ce am făcut până acum. Acum vă voi arăta cum să construiți restul graficului. Deci, să luăm partea verde. Și acum ne-am întors la construcție. Partea verde este de fapt modul în care folosești acea construcție. Așa că revenim la construcție aici... acum, ce vrem să realizăm? Până când jucătorii din grafic au ajuns aici, au făcut efectiv o atribuire variabilelor mergând fie la stânga, fie la dreapta la fiecare dintre aceste diamante. Deci sarcina este gata. Din perspectiva jocului cu formule, jocul s-a terminat, iar acum o parte sau cealaltă a câștigat. Aici, vrem să construim o structură suplimentară aici, ca un fel de joc final, pentru a ne asigura că jucătorul For All rămâne blocat dacă jucătorul Exist a făcut o misiune care satisface această parte a formulei. Iar jucătorul Exist ar trebui să rămână blocat dacă jucătorul For All, dacă misiunea pe care a făcut-o nu satisface formula. Deci, să vedem cum vom realiza asta cu o structură suplimentară. Deci va fi un nod suplimentar aici. Permiteți-mi să vă spun care este structura și apoi vom argumenta de ce funcționează. Deci, plecând de la acest nod inferior, vom începe a doua parte a graficului. Va exista un nod care se extinde într- un nod pentru fiecare dintre clauze. Și fiecare dintre aceste clauze, la rândul său, se extinde într-un nod pentru fiecare dintre literalele sale. Deci vedeți că avem clauza c1 și are literalele x1, x2 bar, x3, x1, x2 bar, x3. Deci, există un nod pentru fiecare dintre literalii din clauza c1, același lucru pentru clauza c2 și așa mai departe. Acum aproape am terminat. Acum am să vă spun cum să conectați aceste noduri literale. Deci x1, fiecare nod va corespunde înapoi cu propriul său diamant. Așa că acum o vom lega înapoi de prima parte, unde am făcut partea de atribuire a graficului. x1 se va conecta înapoi la partea adevărată a diamantului x1. Și x2 pentru că, este negat, se va lega înapoi de partea falsă a diamantului x2 pentru că este o variabilă x2. În mod similar, x1 bar-- deoarece x1 bar-- aici este x1 bar în clauza 2-- x1 bar se va conecta acum la partea falsă a diamantului x1. Și bara x2 se va conecta la partea falsă a diamantului x2 și așa mai departe. Nu am celelalte diamante aici, dar x4 s-ar conecta la partea adevărată a diamantului x4, de exemplu. Asta e toată construcția. Să înțelegem de ce funcționează. Deci finalul aici este că vrem ca Exist să câștige dacă misiunea a îndeplinit toate clauzele. Și For All ar trebui să câștige dacă ar exista niște clauze nesatisfăcute. Deci de ce se întâmplă asta? Deci, să punem înapoi o misiune care a fost făcută. Deci, cea pe care o pun înapoi, misiunea pe care au construit-o în cooperare avea x1 fiind adevărat, x2 fals și alte lucruri. Acum, de ce funcționează asta? Deci, ceea ce vrem să se întâmple acum - deci acum, mutarea continuă până aici și trebuie să o aranjați astfel încât Exist să fie cel care alege acel nod. Dacă acest lucru ar fi fost For All, trebuie doar să adăugați un nod suplimentar pentru a schimba cui este rândul. Dar vrei ca Exist să fie aici sus. Și ceea ce vrei este ca For All să aleagă nodul clauzei. Acum, iată partea care trebuie să înțelegem ce se întâmplă: vrem ca For All să câștige dacă acest lucru nu este satisfăcut. Deci For All va face o revendicare. Dacă nu este satisfăcut, există o clauză care nu este satisfăcută. Există o clauză care a ajuns să fie falsă în sarcină. Deci jucătorul For All va spune: „Cred că am câștigat. Și am câștigat pentru că clauza numărul 1 este nesatisfăcută”. Deci va alege clauza numărul unu. Așadar, aici este [INAUDIBLE] al jucătorului For All. Aici este jucătorul Exist. Și astfel jucătorul For All alege clauza reclamată nesatisfăcută. Deci aici, jucătorul For All spune că clauza c1 este nesatisfăcută. Mă mut aici. Jucătorul existent spune: „Uh-uh, nu sunt de acord cu tine. Atribuirea, linia ta... alocarea de fapt face ca unul dintre literalele din clauza c1 să fie adevărat. Să presupunem că ai făcut ca x1 a fost adevărat, deoarece de fapt, este aici-- x1, de fapt, este adevărat. Deci, Exist va alege acum literalul care a fost adevărat în atribuirea din acea clauză, despre care jucătorul For All pretinde că este nesatisfăcut. Unul dintre ei minte în acest moment. Acest lucru este fie acum adevărat aici, ceea ce înseamnă că jucătorul For All nu a ales o clauză nesatisfăcută, fie jucătorul Exist a ales literalul fals, adică jucătorul existent a ales literalul fals, astfel încât jucătorul existent minte. Acum, momentul de adevăr pentru că să vedem... dacă Exist a fost ales aici, acum este rândul jucătorului For All. Este conectat înapoi la partea adevărată a diamantului. Deci acel nod a fost deja folosit. Acesta este singurul loc în care For All ar putea merge. Pentru Totul este blocat și Exist a câștigat jocul, ceea ce doriți deoarece afirmațiile lui For All sunt false și Exist a fost corect spunând că x1 a satisfăcut clauza c1. Deci x1 este adevărat, așa că nu există niciunde unde să meargă For All. Dar comparați asta cu situația în care atribuirea, pe această parte a graficului, ar fi trecut prin fals, ar fi atribuit x1 ca fiind fals, așa că calea ar fi trecut prin partea For All a diamantului. Acum acest nod ar fi încă neocupat, ar fi încă disponibil. Așa că acum jocul For All-- deci dacă Exist pretindea că x1 este adevărat și că într-adevăr era fals, jucătorul For All ar putea trece pe acel nod. Și acum este rândul jucătorului Exist, iar Exist ar fi blocat pentru că acest nod de aici este garantat că a fost folosit. Deci asta este ideea. Este într-adevăr foarte frumos și, de fapt, nu atât de complicat. Trebuie să te uiți puțin la el. Deci, să vedem ce se întâmplă, de exemplu, dacă am mai avut un alt caz -- poate că nu este necesar în acest moment, dar dacă jucătorul For All a susținut că este a doua clauză care este nesatisfăcută în misiunea selectată de comun acord, atunci -- deci acesta este un fel de cazul în care jucătorul For All este corect, în sensul că, dacă jucătorul Exist spune acum, ei bine, cred că x1 bar a satisfăcut a doua clauză, dar această atribuire a făcut ca x1 să fie adevărat, deci x1 bară este falsă. Și astfel jucătorul Exist minte de data asta. Și acum, jucătorul For All poate lua această ultimă avantajă și poate merge aici și are de făcut o ultimă mișcare. Și apoi jucătorul Exist este blocat. Deci For All va câștiga în acest caz. Deci, să ne întoarcem acum, schimbând vitezele într- o altă parte a complexității spațiului. În loc să ne uităm la spațiul polinomial, care este foarte puternic, ne vom uita la spațiul jurnal, care este, comparativ vorbind, mult, mult mai slab. Deci, spațiul de jurnal sunt lucrurile pe care le puteți face atunci când aveți suficient spațiu pentru a scrie, în esență, un pointer sau un număr fix de indicatori în intrare. Asta obțineți când aveți spațiu logaritmic, deoarece spațiul de log este suficient pentru a scrie un index al ceva. Deci, asta este ceea ce puteți face cu o grămadă de indicatoare. Și pentru a înțelege acest lucru, trebuie să schimbăm modelul de calcul. Pentru că dacă folosim mașina Turing obișnuită cu o bandă, doar scanarea prin intrare, doar citirea intrării așa cum am definit-o, ar costa spațiu n. Și deci nici măcar nu puteți citi intrarea dacă aveți mai puțin de n spațiu disponibil, cum ar fi spațiul de jurnal. Așa că vom introduce un model diferit doar pentru a ne permite să definim acest lucru. Și acesta este un model în care va avea două benzi, unde partea care conține intrarea nu contează. Și pentru a vă asigura că nu este înșelat, banda de intrare va fi doar citită, dar nu contează în spațiul utilizat. Doar banda de lucru, care acum poate fi scrisă sau citită, va conta pentru limita spațiului. Deci, acum, ceea ce vom defini este, folosind această definiție pentru complexitatea noastră spațială, vom defini SPACE log n, lucrurile pe care le puteți face dacă aveți doar o cantitate log de spațiu aici, pe banda de lucru. Deci lungimea intrării este n. Lungimea benzii de lucru este jurnalul de comandă n. Deci avem clasele asociate deterministe și nedeterministe -- SPACE log n și NSPACE log n. Îl numim L și NL - spațiu de jurnal și spațiu de jurnal nedeterminist. Și așa cum am spus, este suficient spațiu pentru a scrie niște indicatoare în intrare. Și hai să facem câteva exemple rapide. Deci, dacă luați limbajul palindromului, în esență, sau ww invers, acesta este în spațiul de jurnal. Deci iată un șir. Iată un șir care este în ww invers. Și modul obișnuit pe care l-ați putea folosi pentru a testa dacă un șir are această formă în ww revers ar putea fi să tăiați locațiile corespunzătoare aici. Dar nu poți face asta. Este o bandă de intrare numai pentru citire. Deci, trebuie să evitați cumva să scrieți pe banda de intrare, dar totuși să testați dacă sunteți în această limbă. Nu este greu de făcut. Puteți folosi banda de lucru doar pentru a ține evidența unde ar fi indicatorii dvs. Și, făcând acest lucru, vă puteți asigura că potriviți locațiile corespunzătoare între ele în intrare. Deci, spațiul de jurnal, datorită capacității sale de a stoca un număr fix de pointeri, vă oferă suficient pentru a testa apartenența în această limbă. Deci, acest lucru este rezolvabil în spațiul de jurnal. Problema căii, pe care am văzut-o înainte-- vi se oferă un grafic și un nod de început și un nod de sfârșit, sau un început și o țintă. Vi se oferă un grafic al unui s și t-- este un grafic direcționat-- și pot să știu, pot trece de la s la t? Deci, acea problemă este rezolvabilă în spațiul de jurnal nedeterminist, deoarece modul în care am face asta, nu notând acest lucru în detaliu, ci ceea ce ați face în mașina dvs. de spațiu de jurnal nedeterminist - aveți graficul de intrare scris aici în intrare și veți doar să ghiciți succesiunea de noduri unul câte unul, care vă duce de la nodul de pornire la nodul țintă. Nu veți scrie în avans întreaga secvență pentru că asta v-a costat prea mult spațiu pentru a o nota. Singurul spațiu pe care îl veți folosi este să vă amintiți locația curentă în care vă așezați. Deci începi, notezi pe banda de lucru nodul de pornire. Apoi, veți alege nedeterminist una dintre marginile de ieșire din nodul de pornire și veți privi nodul asociat, și înlocuiți-o pe banda de lucru și continuați să repetați asta. Dacă ajungi vreodată la nodul t, atunci poți accepta. Și trebuie să fii puțin atent... Nu am asta pe tobogan. De asemenea, trebuie să vă asigurați că, dacă graficul are o buclă în el, deoarece acest lucru nu este permis în complexitatea spațiului, deci veți avea nevoie și de un contor pentru a vă asigura că dacă numărați până la... ați trecut prin un număr de noduri care depășește numărul total de noduri din grafic, apoi puteți închide acea ramură a nedeterministului, deoarece merge doar într-o buclă. Dacă există vreo cale care conectează s la t, cu siguranță va exista o cale care are cel mai mare număr de noduri ale graficului în ea. Deci calea este în NL. Această limbă aici este în L. Care este relația dintre L și NL? Ei bine, cu siguranță clasa deterministă este conținută în clasa nedeterministă. Asta e tot ce se știe. Dacă aceste două se prăbușesc pentru a fi la fel, nu este rezolvată. Și așa vom petrece puțin timp următoarea prelegere explorând asta. Dar să ne uităm mai întâi la unele dintre faptele de bază despre spațiul de jurnal, cum să ne pregătim pentru următoarea prelegere. Deci, în primul rând, orice puteți face în spațiul de jurnal, puteți face în timp polinomial - într-un fel, într-un fel trivial, și într-un fel am demonstrat deja acest lucru. Pentru că, dacă vă amintiți, am spus că orice puteți face într-o anumită cantitate de spațiu, puteți face în timp, care este exponențial în cantitatea de spațiu, în cantitatea corespunzătoare de spațiu. Deci, trecerea din spațiu în timp te aruncă în aer exponențial. Și exponențialul de ordine log n este polinom. Așadar, felul în care vom demonstra acest lucru-- și din nou, am cam dovedit acest lucru deja, dar hai să trecem prin el din nou, specific spațiului de jurnal. Vom spune - și oricum aceasta va fi o definiție utilă pentru noi - o configurație pentru M pe w. Deci am vorbit deja despre configurația mașinii Turing M, care este doar un instantaneu, care este banda, starea și poziția capului. Când avem o intrare, care este un fel de intrare numai pentru citire , care nu este luată în calcul pentru spațiu, nu o includem în configurație. Spunem doar că este o configurație a lui M pe intrarea respectivă, dar vom număra configurațiile. Și nu vreau să număr și toate intrările diferite. Voi repara intrarea și voi număra toate configurațiile legate de acea intrare. Și astfel, numărul de astfel de configurații va fi pur și simplu numărul de stări ori numărul de poziții ale capului pentru cele două capete acum, ori numărul de conținut posibil al benzii, care este, așa cum am menționat, aici există o serie de diferite posibil conținutul benzii. Este d, care este alfabetul benzii, la jurnalul de ordine n. Și asta va fi doar n la k pentru niște k. Deci va fi polinom. Deci, asta ne spune că, deoarece numărul total de configurații pentru M pe w este polinom, această mașină poate rula doar pentru un număr polinom de pași. În caz contrar, va fi în buclă. Va repeta o configurație. Prin urmare, acea mașină trebuie să funcționeze singură în timp polinomial. Deci, într-un fel, nu trebuie să faci nicio treabă. Dacă o mașină decide în mod determinist o limbă în spațiul de jurnal, de asemenea, decide determinist limba în timp polinomial, deoarece acesta este tot timpul pe care îl puteți folosi atunci când aveți spațiu de jurnal, cu excepția cazului în care faceți buclă, ceea ce nu este permis. Prin urmare, aceeași mașină arată că și tu ești în P. Voi ajunge la asta într-o secundă. Un lucru pe care am uitat să-l menționez în diapozitivul anterior când vorbesc despre model este, apropo, acest model nu este atât de nerezonabil, unde aveți un fel de-- imaginați-vă că aveți o intrare foarte mare, numai pentru citire și localul dvs. stocarea este mult mai mică. Este mult prea mic pentru a introduce întreaga intrare. Modul în care obișnuiam să explic asta cu ani în urmă a fost contribuția dvs. ca un CD-ROM, pe care probabil că abia mai știți ce este, dar obișnuiați să distribuiți software în acest fel. Deci ROM-ul era pe un DVD sau pe un CD, care conținea tot ce încercați să -- cum ar fi software-ul dvs. pe care încercați să îl distribuiți. A fost ceva mare , relativ, și așa că vă imaginați că aveți o cantitate mai mică de memorie în comparație cu asta. Deci nu ați vrut să copiați neapărat tot acel lucru în spațiul dvs. de stocare. Poate chiar un exemplu mai bun acum este că te gândești la intrare ca fiind întregul internet. Evident, cu excepția cazului în care sunteți Google, nu puteți descărca întregul internet în propria memorie locală, dar puteți avea referințe, indicatoare în introducerea în diferite locuri. Acesta este poate mai analog cu acest tip de model de mașină Turing cu intrare numai pentru citire pe care îl descriu. Și există un alt fapt pe care vreau să-l menționez, este că orice puteți face în spațiul de jurnal nedeterminist îl puteți face în spațiul determinist, dar acum cu pătratul. Și asta se folosește aceeași dovadă. Asta folosește teorema lui Savitch, pe care trebuie să o verifici că funcționează și pentru a înregistra spațiu -- aceeași dovadă. Deci, orice faceți nedeterminist în spațiul log n, îl puteți utiliza determinist în spațiul log pătrat n. Deci, permiteți-mi să văd dacă există câteva întrebări la care vreau să răspund aici. Relația dintre L și NL nu este cunoscută ca fiind strictă. Nimeni nu știe de un exemplu. Nimeni nu știe dacă sunt egali. Și oamenii s-au uitat la clase de timp subliniare? Da, în general, atunci când aveți nondeterministice sau probabilistice-- ceea ce nu am definit încă, dar vom-- oamenii s-au uitat și la acele clase de timp subliniare. Din punct de vedere determinist, nu are atât de mult sens pentru că atunci nici măcar nu poți vorbi despre întreaga intrare. OK, lasă-mă să merg mai departe. Acesta este ultimul meu slide. Lasă-mă să văd dacă putem face asta înainte de a întrerupe. Nu numai că L este conținut în P, dar afirmația mult mai puternică este că NL este conținut în P. Și pentru asta va trebui să lucrați, deoarece convertiți mașina dvs. de spațiu de jurnal nedeterministă într-o mașină deterministă - evident, sunteți va trebui să schimbe mașina. Și așa vom introduce o nouă metodă aici. Poate vom trece rapid peste asta la începutul următoarei prelegeri. Nu-mi place să mă grăbesc prin lucruri la sfârșit. Dar pentru aceasta, dacă mi se oferă o mașină nedeterministă care rulează în spațiul de jurnal, vreau să fac o nouă mașină care să ruleze în timp polinomial determinist pentru același limbaj. Și voi defini ceva numit „ graficul de configurare” pentru M pe o intrare w. Și asta e doar că luați M și w, intrarea lui, și vă uitați la toate configurațiile pentru M pe w -- de fapt, configurația -- de fapt, asta ar trebui să fie numit „graficul de calcul”. Așa se numește în carte, dar este o greșeală de tipar. Da, o să rezolv asta data viitoare. Nu contează. Grafic de calcul, grafic de configurare, la fel. Practic, veți lua toate configurațiile lui M pe w, dintre care am observat deja că sunt doar polinomiale. Și devin nodurile unui grafic. Iar marginile conectează două configurații dacă una urmează pe alta conform regulilor mașinii. Deci iată o poză. Acesta este un grafic. Nodurile acestui grafic sunt configurațiile lui M pe w. Deci, fiecare nod aici corespunde unui instantaneu al mașinii, conținutului unei benzi, poziției capului și stării. Deci, notând toate acele configurații diferite, mă conectez una la alta, dacă pot ajunge la C j din C i într-un singur pas legal pe mașină. Și apoi, mașina nedeterministă M acceptă w exact atunci când există o cale de la configurația de pornire la o configurație de acceptare. Să presupunem că avem doar o singură configurație de acceptare, așa cum am susținut că putem face una sau două prelegeri înapoi, dacă curățăm casetele. Deci testarea dacă puteți obține de la început până la acceptare este aceeași cu testarea dacă aparatul își acceptă intrarea. Și astfel, pentru că putem testa dacă există o cale într-un grafic care conectează două noduri în timp polinomial, putem rezolva această problemă pe acest grafic de calcul/configurare în timp polinomial. Și astfel ne putem da seama dacă mașina nedeterministă își acceptă intrarea. Îmi pare rău, a venit puțin mai repede decât îmi place, așa că o vom vedea din nou. Deci, iată algoritmul de timp polinomial. Construiți graficul, acceptați dacă există o cale de la început până la acceptare și respingeți dacă nu există. Și asta ne spune că nu numai L este conținut în NL, ci și NL în sine este conținut în P. Deci, iată un fel de ierarhie frumoasă a limbilor. Nu numai că nu știm dacă L este egal cu NL, nu știm dacă L este egal cu P. Este posibil ca orice puteți face în timp polinomial, să puteți face determinist în spațiul logaritmic, oricât de șocant ar fi, deoarece acesta este un clasă destul de slabă. Dar nu știm cum să dovedim că există ceva diferit, orice în P care nu este aici. Ultima verificare. Așa că am arătat că PATH este în NL. Care este cel mai bun lucru pe care îl putem face cu privire la complexitatea spațială deterministă a PATH? Deci determinist. Deci, acesta este spațiu de jurnal nedeterminist. Ce putem spune în mod determinist despre PATH? Sugestie... nu ar trebui să fie greu dacă te gândești la ceea ce am arătat recent. Obțineți punctele de check-in. Închiderea. Se închide magazinul aici. Toate gata, 1, 2, 3. Da, deci răspunsul corect este spațiul log pătrat, deoarece aceasta este doar teorema lui Savitch. O putem face în spațiul de jurnal în mod nedeterminist, deci o puteți face în spațiul de jurnal în mod determinist. Deci asta este ceea ce am făcut astăzi. Și așa cum am menționat, voi face acest lucru din nou în prelegerea de marți, doar ca să recapitulez. Bine, așa că voi rămâne puțin pentru întrebări. Și cineva mă întreabă de nomenclatură. De ce este spațiu L și nu L? Pentru că oamenii nu vorbesc de obicei despre timpul L. Deci L este un fel de-- toată lumea știe că singura opțiune rezonabilă este spațiul, așa că oamenii spun doar L și NL. Adică, unele dintre aceste nume au evoluat puțin în timp. Și chiar și acum, unii oameni vorbesc despre... eu numesc „cursuri de timp”, unii oameni numesc „cursuri de timp”. Acolo poți face diferite alegeri. Să vedem. Bun. De ce funcționează teorema lui Savitch pentru log n? Trebuie să te uiți înapoi și să vezi de ce ai nevoie. Și tot ce trebuia să poți face era să notezi configurațiile. Și dacă te uiți înapoi la modul în care funcționează filmul lui Savitch, trebuie doar să notezi configurația. Deci mașina deterministă poate scrie configurațiile pentru mașina nedeterministă. Au exact aceeași dimensiune. Și apoi te uiți la recursivitate. Și adâncimea recursiunii va fi exponențială în dimensiunea configurațiilor. Și așa vei ajunge cu o pătrare din nou. Trebuie să te întorci și să regândești doar această dovadă. Și veți vedea nicăieri nu a avut nevoie de o cantitate liniară de spațiu. Funcționează până la-- de fapt nu funcționează pentru mai puțin de log n. Log n este un fel de pragul inferior acolo. Și motivul este că trebuie să stocați și locația de intrare, iar asta ocupă deja spațiu în jurnal. Capetele de bandă -- capetele de bandă au deja un fel de aspect de spațiu pentru jurnal. Și așadar, dacă veți folosi mai puțin spațiu decât în ​​jurnal, atunci se întâmplă lucruri ciudate cu stocarea capetelor de bandă. Și astfel mai puțin decât spațiul de jurnal se dovedește de obicei a nu fi interesant, foarte specific mașinilor Turing și nu modelelor generale. Da, deci cineva întreabă, să presupunem că în reducerea la geografie generalizată din TQBF, dacă formula ar avea două Exist la rând, atunci ai face un fel de lucru natural în grafic. În loc să aveți acea margine de distanță între cele două diamante, puteți avea doar un diamant conectat direct la celălalt diamant fără o margine de distanță. Și asta ți-ar da efectul de a nu schimba cui este rândul. Cineva îmi pune doar o întrebare generală, oamenii se gândesc la aceste probleme deschise? Nu știu. Oamenii nu spun. S-a lucrat mult pe probleme legate, care păreau să fie legate de acele multe întrebări deschise, cum ar fi P versus NP, L versus NL sau L versus P și așa mai departe, P versus PSPACE. Vom mai vorbi puțin despre unele dintre acestea. Au fost dezvoltate niște lucruri foarte interesante . Cred că există un sentiment în cadrul comunității că oamenii sunt blocați și că vei avea nevoie de un fel de idee nouă majoră pentru a împinge chestia înainte. Deci nu știu câți oameni se mai gândesc la ele. Sper că oamenii sunt pentru că aș dori să văd răspunsul la un moment dat sau să obțin răspunsul. Mă gândesc uneori la ele, dar trebuie să recunoaștem că șansele de succes nu sunt mari. Deci am trecut puțin după sfârșitul orei aici. Dacă nu există alte întrebări, dacă nu ți-am răspuns la întrebare, poate că am ratat-o, așa că poți întreba din nou. Dar altfel, voi închide asta, închidem sesiunea aici. OK, la revedere tuturor. Un week-end bun să aveţi. Ne vedem săptămâna viitoare. Ai grijă.