[SCRÂȘIT] [FOSȘIT] [CLIC] MICHAEL SIPSER: Bună, tuturor. Sper că mă poți auzi. Dă-mi un degetul mare dacă poți. Bun. Îi văd trecând. Deci vom începe. Așa că revenim la ceea ce am făcut. Am vorbit despre complexitatea spațiului. Măsoară câtă memorie necesită algoritmul sau necesită diverse probleme. Și am definit clasele de complexitate spațială, spațiul f al lui n și spațiul nedeterminist f al lui n, spațiul polinomial și clasele spațiului nedeterminist și am dat câteva exemple și așa mai departe. Și astăzi vom relua de unde am rămas ultima dată. Unul dintre exemple, care va fi unul important pentru noi, se referă la această din urmă problemă DFA. Așa că voi trece din nou peste asta, voi pune un pic mai mult accent pe analiza spațiului, despre care am primit câteva întrebări data trecută. Și apoi vom trece de acolo și vom demonstra teorema lui Savitch și apoi vom vorbi despre o problemă completă pentru PSPACE și vom arăta că această problemă TQBF, pe care am introdus-o data trecută, este de fapt o problemă completă PSPACE. Dar toate la momentul potrivit. Un pic de recenzie. Așa că am definit ce înțelegem prin o mașină Turing care rulează într-o anumită cantitate de spațiu. Asta înseamnă că folosește cel mult f din n. Dacă rulează în spațiul f din n, folosește cel mult f din n celule, celule de bandă, pentru fiecare intrare de lungime n. Și, în mod similar, o mașină Turing nedeterministă face același lucru. Dar, în plus, mașina nedeterministă trebuie să se oprească în fiecare ramură a calculului său. Și fiecare ramură a calculului său trebuie să folosească cel mult acea cantitate limitată de celule de bandă. Deci vom vorbi și astăzi despre calculul spațial nedeterminist. Va fi relevant pentru noi. Deci am definit clasele, așa cum am menționat, și polinomul și clasele PSPACE și nedeterministe PSPACE. Și așa credem că se raportează unul la altul. Clasele coNP și NP, de asemenea. Și, bineînțeles, așa cum am menționat data trecută, există câteva probleme majore nerezolvate în acest domeniu. Deci totul s-ar putea prăbuși până la P, ceea ce, desigur, ar fi foarte surprinzător. Dar nu știm cum să dovedim contrariul. Și marea teoremă pe care o vom demonstra astăzi este că spațiul polinomial și spațiul polinomial nedeterminist se prăbușesc de fapt unul față de celălalt. Și fiind aceeași clasă. Așadar, spre deosebire de situația pe care credem că este cazul pentru complexitatea timpului, în care credem că conversia nedeterministului în determinist dă o creștere exponențială pentru complexitatea spațiului, dă doar o creștere la pătrat, așa cum vom vedea. Deci, vreo întrebare despre asta? Vom trece doar într-o mică revizuire a acestei ultime probleme. Deci, revizuind o parte din notație. Și permiteți-mi să subliniez asta. Deci marea teoremă pe care o vom demonstra astăzi este că PSPACE și NPSPACE sunt egale. Și, de asemenea, vom vorbi despre completitatea PSPACE. Dar ambele implică demonstrarea teoremelor. În primul caz, teorema lui Savitch conform căreia conversia spațiilor nedeterministe în spații deterministe este la pătrat. Și în al doilea caz, demonstrând că TQBF este PSPACE complet. Ambele teoreme pot fi considerate ca generalizări ale acestei teoreme aici că ultima problemă DFA poate fi făcută în spațiul polinomial determinist sau spațiu n pătrat . Așa că merită să încerci să înțelegi cum funcționează demonstrația acestei teoreme. Pentru că, într-un fel, această teoremă este o versiune mai concretă a ceea ce vom vedea în celelalte două teoreme într-o formă oarecum mai abstractă. Așa că îmi place să înțeleg lucrurile într-un mod mai concret mai întâi. Deci, acesta este un exemplu bun cu care să începeți. Dar, într-adevăr, în cele din urmă, este aceeași dovadă tocmai repetată pentru acele trei teoreme. Deci acestea sunt de fapt trei la prețul unuia. Trei teoreme, o dovadă aici. Deci veți vedea aceeași dovadă repetată de trei ori, dar în diferite niveluri de abstractizare. Deci, haideți să revizuim din nou. Știu că unii dintre voi l-ați înțeles, dar poate că unii dintre voi nu. Și să încercăm să fim clari cu privire la algoritmul pentru a rezolva problema DFA ladder. Deci, dacă îți amintești, în primul rând , lasă-mă să trec mai departe. Problema scarii este-- o scară, în primul rând, este o secvență de șiruri care schimbă un simbol la un moment dat, care poate se conectează, merg de la un șir la altul. Deci, vei trece de la serviciu la joacă, schimbând câte un simbol pe rând. Așa că am dat un exemplu în acest sens sau puteți veni cu ușurință cu un exemplu de a face acest lucru. Dar problema de calcul este că poți face asta? Puteți trece de la acest șir la acel șir și să rămâneți într-o anumită limbă? Deci, poate fi limba cuvintelor engleze sau poate fi limba tuturor șirurilor pe care le recunoaște anumite DFA. Deci ar putea fi tot din sfoară. Acestea ar putea fi toate șiruri pe care unele DFA le acceptă sau ar putea fi cuvinte în limba engleză sau o altă regulă. Și asta este ceea ce ne referim prin încercarea de a testa dacă există o scară. Și deci problema scării este, ei bine, nu cred că am notat problema scării în sine. Dar problema scarii delimitate este practic aceeași idee. Vi se dă DFA. Vi se dau șirurile u și v. Și acum aceasta este versiunea limitată a problemei în care vă voi da o limită a numărului de pași pe care îi puteți face. Așa că ilustrez asta aici. Deci vi se va da un b. Și vrei să spui, pot ajunge de la acest șir la acel șir în b pași? Și am avut o notație pentru a scrie asta. Trecând de la u la v, dacă există o scară care leagă u de v în cel mult b trepte. Și așadar, problema scarii mărginite, pe care o introduc pentru că voi viza un algoritm recursiv pentru a rezolva această problemă, este dacă pot ajunge de la u la v printr-o scară, schimbând câte un simbol pe rând, unde fiecare șir pe parcurs este acceptat de b, iar mie nu am voie decât b pași. B pași mici. Deci aceasta este problema de calcul pe care o voi rezolva cu algoritmul pe care îl voi descrie. Deci algoritmul pe care îl voi numi BL pentru problema scarii mărginite. Și aici este intrarea. Și algoritmul va căuta , în primul rând, să vadă dacă b este egal cu 1. Dacă doar încerc să ajung de la u la v într-un singur pas. În acest caz, este o problemă foarte simplă, pentru că doriți să testați, evident, că u și v sunt acceptate de automat. Și trebuie doar să difere într-un singur loc. Și apoi aveți o scară cu o treaptă foarte simplă, care vă duce la v. Deci, pentru cazul b este egal cu 1, este foarte simplu. Pentru valori mai mari ale lui b, vom rezolva problema recursiv în termeni de valori mai mici ale lui b. Deci, pentru b mai mare decât 1, vom testa recursiv. Dacă încercați să rezolvați problema, pot ajunge de la u la v, în schimb vom încerca fiecare dintre ele posibile la jumătate. Nu știm că e la jumătatea drumului. Deci vom încerca doar fiecare șir posibil. Și vom testa dacă putem obține de la u, șirul inițial, la acel șir nou, acel w, în jumătate din numărul de pași. Și pot ajunge la șirul final v în jumătate din numărul de pași? Dacă pot face asta, atunci pot obține de la u la v numărul total de pași b. Așa că voi încerca să fac asta una câte una pentru fiecare w posibil. Acest lucru va fi foarte costisitor din punct de vedere al timpului, dar nu ne facem griji în privința timpului în acest moment. Încercăm să reducem spațiul pe care îl folosim. Și aceasta va fi o mare economie în spațiu. Să nu ne facem griji în privința împărțirii, b peste 2 aici. Toate diviziile, vom vedea asta de mai multe ori în continuare în prelegere, ne vom gândi la rotunjirea lor. Dar nu voi face notația să pară greoaie scriind asta de fiecare dată. BINE. Deci iată-ne. Iată un șir candidat candidat, care este la jumătatea drumului. Testează recursiv. Pot trece de la șirul de început la acel w și de la w la acel șir de sfârșit? Dacă pot, dacă găsesc un astfel de w, atunci accept. Și dacă încerc tot posibilul w și nu reușesc niciodată să găsesc o modalitate de a face atât partea de sus, cât și cea de jos să funcționeze, atunci știu că nu pot trece de la șirul de început la șirul de sfârșit în b pași. Și așa resping. Și acum voi rezolva problema inițială a scării nemărginite punând pur și simplu cea mai mare limită posibilă în problema scarii mărginite. Și aceasta este această valoare t, care oferă limita foarte trivială a numărului total de șiruri posibile pe care le pot scrie în lungimea mea m cu care lucrez. Deci, dacă sigma este alfabetul acestor șiruri, este doar sigma la m. Sunt toate șirurile posibile. Desigur, aceasta va fi o dimensiune maximă pe scară. Deci acum cât spațiu ocupă asta? Și cred că aici oamenii s-au pierdut puțin în prelegere data trecută. Așa că o să încerc să animez asta. Nu știu dacă asta va ajuta sau nu. Dar la sfârșitul zilei, va trebui doar să vă gândiți cum să contabilizați costul acestei recursiuni. Dar principalul lucru, pentru a începe, trebuie să vă asigurați că înțelegeți algoritmul. Și dacă ajungeți de aici până acolo, vom încerca toate punctele de mijloc posibile și apoi vom rezolva recursiv partea superioară și cea inferioară, reutilizand spațiul. Așa vom obține o economie. Prin rezolvarea acestei probleme, reutilizarea spațiului pe care îl folosim pentru a rezolva această problemă. Așa că voi încerca să vă arăt asta despre cum este folosit spațiul pe mașina Turing. Vă puteți gândi într-un fel la aici intrarea și apoi după aceea va fi stiva pentru recursivitate. Dacă nu ești atât de familiarizat cu cum să implementezi recursiunea, nu contează cu adevărat. Dar vă puteți gândi doar la ce trebuie să țină evidența algoritmul. Și așa cum încearcă toate w posibile, așa că în ordine ca un contor de kilometraj, doar încercând fiecare șir posibil, în cele din urmă poate găsi un șir care este în limba care aude un cuvânt englezesc, unul dintre primele cuvinte englezești de lungime 4 pe care le- ați s-ar putea întâlni. Și așa că acum are sens, de fapt, să facem recursiunea. Deci asta e tot. De fiecare dată va trebui să aveți un registru sau o locație pe bandă în care veți nota acele w diferite. Deci, să spunem că e aici. Și doar o să trecem prin. Sper că nu este prea mic pentru a vedea. Acolo se întâmplă cu adevărat acțiunea. Și, în sfârșit, poate ai ajuns la șirul w. Acum vei încerca să faci recursiunea. Așa că aici, pe măsură ce faci din nou recursiunea în jumătatea superioară , vei tăia-- vei găsi un nou w pentru punctul intermediar doar rezolvând această problemă superioară în care testăm dacă eu poate ajunge de la muncă la capabil. Mai târziu va trebui să mă ocup de faptul că pot să joc. Bun. Deci, aici, din nou, vom remedia posibilitatea, reparăm primul w. Vom încerca toate modalitățile posibile de a ajunge de la șirul de început la șirul de mijloc. Așa că vom încerca aici orice lucru posibil. În cele din urmă, poate găsim un alt șir în limbaj. Ajungem la cartea cu șiruri. Și toate acestea vor fi stocate. Nu poți uita șirul capabil. Dar acum vom folosi ceva mai mult spațiu pentru a stoca acești candidați. Deci, aceasta este o a doua versiune a w mai profundă în recursivitate. Deci aici vom fi triunghi cu posibile șiruri aici. Din nou, în cele din urmă ajungem la o carte cu șiruri. Și dacă asta reușește să ne aducă de la serviciu la capabil prin carte, acum vom sări în jos pentru a face jumătatea de jos, pentru a vedea dacă pot ajunge de la capacitatea de a juca ca o problemă separată, care se rezolvă în același spațiu . Așa că acum, aici vom încerca toate aceste posibilități de a putea juca. Poate call este șirul intermediar potrivit acolo. Și așa că acum vom șterge cartea și acum vom rezolva problema secundară inferioară în aceeași locație. Sper că acest lucru este de ajutor. A fost multă muncă pentru realizarea acestor animații. Deci, scopul tuturor acestor lucruri este că de fiecare dată când coborâm nivelul recursiunii, este nevoie de un alt registru a cărui dimensiune este suficient de mare pentru a susține unul dintre șiruri. Și acel registru este reutilizat de ori pe tot parcursul, pe măsură ce trecem prin această recursivitate. Deci, oricum, sper că este de ajutor. Oricum. Deci, fiecare nivel al recursiei adaugă o altă ordine pentru a înregistra w. Și așa trebuie să faci... câte nivele avem. Ei bine, adâncimea recursiunii va fi de câte ori vom ajunge să împărțim această imagine în jumătate până când ajungem la 1. Și astfel, înălțimea acesteia atunci când începem va fi practic o exponențială în m . m este aproximativ dimensiunea lui n. Deci, când iei jurnalul , vei obține... vei trage în jos exponențialul. Deci va fi ordinul m sau, care este, din nou, aproximativ aceeași dimensiune ca și intrarea. m este ca jumătate din intrare, deoarece întreaga intrare este u și v. m este doar dimensiunea lui u. Și astfel, fiecare nivel necesită ordinul n, iar adâncimea va fi de ordinul n adânc. Jurnalul înălțimii inițiale a acestei scări. Și astfel spațiul total folosit va fi de ordinul n pătrat. Deci de ce nu ne luăm doar un minut? Mă bucur să petrec puțin timp trecând prin asta, fie corectitudinea algoritmului, înțelegerea recursiunii, fie înțelegerea analizei spațiale. Dacă există vreo întrebare pe care simțiți că o puteți pune și care ar fi clarificatoare pentru dvs., interveniți. Voi aloca câteva minute doar pentru a răspunde la întrebări aici. Deci am o întrebare aici. La pasul cinci, de ce respingem dacă toate eșuează în loc de doar unul eșuează? Ei bine, aici, așa că amintește-ți ce încercăm să facem. Încercăm să spunem pot ajunge de la u la v în b pași? Modul în care voi face asta este să încerc fiecare șir intermediar posibil w. Dacă găsesc unele w care nu funcționează, asta nu înseamnă că nu există alte w care ar putea funcționa. Tot ce am nevoie este o w pentru care pot ajunge de la u la w în jumătate din numărul de pași și de la w la v în jumătate din numărul de pași. Așa că voi încerca toate w posibile. Dacă vreunul dintre ei este bun, atunci pot accepta. Dacă vreunul dintre ei reușește acolo unde pot ajunge de la u la w în jumătate din pași și de la w la v în jumătate din pași, atunci știu că pot ajunge de la u la v în numărul întreg de pași. Deci trebuie doar să găsesc unul. Dacă unul anume nu funcționează, voi trece doar la următorul. BINE. Aceasta este o întrebare bună. Trebuie să salvăm cartea de cuvinte? Așa că, odată ce reușim să ajungem de la serviciu la capabil, să spunem prin intermediul unei cărți, trebuie să salvăm acea carte de cuvinte undeva? Nu. Tot ce trebuie să ne amintim este că am reușit să ajungem de la muncă la capabil. Nu mai trebuie să ne amintim de carte. Ne amintim doar că am reușit. Și asta în virtutea locului în care ne aflăm în algoritm. Dacă am reușit, atunci trecem la a doua recursivitate, a doua apelare, apel recursiv. Așa că am găsit o modalitate de a face asta. Așa că am găsit un punct intermediar care reușește pentru acesta. Deci trecem la acela. Nu trebuie să mai păstrăm nimic din acea muncă. Tot ce trebuie să faci este să-ți amintești, da, pot ajunge de la serviciu la capabil în jumătate din numărul de pași. Acum tot ce mai rămâne este să ajungi de la capacitatea de a juca în jumătate din numărul de pași. Nu contează cum am reușit în primul rând. Deci nu trebuie să ne amintim asta. A fost o întrebare bună totuși. Deci cred că înțeleg asta. Înainte de a înlocui valoarea pentru rezervare cu apel cu munca implicată pentru a găsi apel, da, trebuie să verificăm dacă putem merge de la serviciu la rezervare și putem rezerva. Așa că păstrăm cartea în timp ce lucrăm la jumătatea superioară. Și numai când am reușit în sfârșit să ajungem de la serviciu la capabil, să spunem prin carte, atunci poți arunca o carte. Dar în timp ce lucrezi la jumătatea superioară, încerci carte, încerci diferite șiruri de lungime patru până când unul dintre ele funcționează. Nu sunt sigur. Cineva mă întreabă despre lățimea prima căutare și adâncimea pentru căutare. Nu sunt sigur că o văd. Nu sunt sigur că va fi un mod util de a gândi la asta. Deci nu am de gând să răspund la asta chiar acum. Dar poți cere asta offline mai târziu, dacă vrei. De ce adâncimea recursiunii este log t în loc de log m? Ei bine, cât de sus este chestia asta? Inițial nu e mare. Dar de fiecare dată când facem un nivel, numim recursivitate, tăiem t la jumătate. Rezolv acest lucru în general pentru b, dar începem cu b egal cu t. t este dimensiunea maximă. Deci inițial acesta va fi t, apoi va fi t peste 2, apoi t peste 4. Deci, va fi log t niveluri înainte de a ajunge la 1. Da. Deci cineva întreabă, ne putem gândi la asta ca la o stivă de memorie? Da, așa e ca... așa este implementarea obișnuită a recursiunii cu o stivă, în care împingeți atunci când efectuați un apel și apăsați când vă întoarceți de la apel. Este posibil ca v să apară în timpul procedurii BL pe t? Este posibil ca v să apară? Nu sunt sigur ce înseamnă asta. Poate reapărea. Deci, încep cu u la v. Este posibil ca v să fie unul dintre aceste șiruri intermediare? Da. Veți încerca orice flux intermediar posibil orbește. Inclusiv v este unul dintre ele. Dacă poți ajunge la v mai repede, ei bine, grozav. Bănuiesc că nu m-am ocupat de problema a ceea ce se întâmplă dacă ajungi la... din punct de vedere tehnic, se va rezolva pentru că permit ca diferența să fie cel mult într-un singur loc. Așa că, chiar dacă ajungi acolo devreme, ai voie să nu schimbi nimic, iar acesta este totuși un pas legal pe scară. Da. Nu văd cum să fac asta dintr-o perspectivă de jos în sus. Cineva întreabă dacă există o versiune de jos în sus a asta. Eu nu cred acest lucru. Nu, nu cred. În regulă. De ce nu mergem mai departe? Deci acum vom vedea această dovadă din nou. Dar de data aceasta vom demonstra că puteți converti orice NFA într-un DFA doar cu o creștere la pătrat. Deci, într-adevăr, bine, lasă-mă să pun asta acolo. Deci aceasta va fi teorema lui Savitch, care, printre altele, demonstrează că PSPACE este egal cu NPSPACE. Deci spune că puteți converti o mașină nedeterministă într-o mașină deterministă doar pătratând cantitatea de spațiu. Deci ești confortabil cu această notație aici. Orice puteți face în f din n spațiu nedeterminist, puteți face în f pătrat din n bazat determinist. Și vom realiza asta transformând un NTM într-un TM determinist, dar doar pătratând spațiul folosit. Deci n îl va transforma într-un m. Și acum această dovadă va arăta foarte asemănătoare cu dovada din diapozitivul anterior. Este aceeași dovadă. Și faptul din slide-ul anterior despre scară este într-adevăr implicat de acest lucru, deoarece am avut un algoritm ușor pentru a arăta că această din urmă problemă este rezolvabilă în nedeterminist, în NPSPACE. Deci problema scarii s-a dovedit cu ușurință a fi aici. Dacă vă amintiți, practic doar ghiciți treptele scării. Deci, nedeterminist, puteți verifica cu ușurință, pot ajunge de la început până la sfârșit? Dar teorema lui Savitch ne spune că orice puteți face nedeterminist în spațiul polinomial, puteți face determinist în spațiul polinomial. Deci ceea ce am arătat în diapozitivul anterior rezultă din acest diapozitiv, dar acest diapozitiv este de fapt doar o generalizare a aceleiași dovezi. Poate am spus-o de prea multe ori acum. Deci vom introduce o notație foarte asemănătoare cu notația pe care am avut-o data trecută. Dar acum vom vorbi despre simularea acestei mașini nedeterministe cu o mașină deterministă. Și vom lua două configurații ale acestei mașini nedeterministe, ci și cj, și vom spune că pot ajunge de la ci la cj în cel mult b pași? O să am o notație. Foarte asemănătoare cu notația pentru scară, unde pot ajunge de la acest cuvânt la acel cuvânt în cel mult b trepte cu o scară. Aici pot ajunge de la acest cuvânt la acela-- pot trece de la această configurație la acea configurație cu cel mult b pași ai funcționării mașinii Turing? Deci acestea sunt două configurații acum ale lui n. Deci, nu poate trece de la această configurație ci la acea altă configurație cj, dar făcând doar b pași pe parcurs? Aceasta este acum problema de calcul pe care o voi rezolva pentru tine cu un algoritm. Și va fi o recursivitate exact ca cea anterioară. Deci n primește intrarea celor două configurații ci și cj și b legat și vreau să verific pot obține de la i la j în b? Deci acum imaginea este puțin diferită, dar foarte asemănătoare. Deci, în loc să apară o scară aici, este într-adevăr ceva care este practic un tablou pentru mașina n în care am o configurație inițială și o configurație finală. Acesta s-ar întâmpla să fie punctul de plecare pentru întreaga procedură dacă testați dacă n acceptă w. Dar am rezolva acest lucru în general pentru orice-- deci acest caz, deci am configurația de pornire a lui n pe w și configurația de acceptare sau o configurație de acceptare. Dar, în general, ceea ce voi rezolva este să încep cu orice configurație ci și să merg la orice configurație cj. Așa că vreau să testez dacă pot ajunge de la ci la cj în cel mult b pași. Deci, în primul rând, dacă b este 1, puteți verifica asta direct. Și acum, din nou, operăm determinist pentru a simula mașina nedeterministă. Deci aceasta este mașina deterministă m. Deci m poate cu ușurință, dacă i se oferă două configurații de n și spune, pot trece de la prima la a doua într-un singur pas? Ei bine, asta e o verificare ușoară. Doar așezați acele două configurații, uitați-vă la funcția de tranziție a lui n și spuneți că aceasta este o mișcare legală pentru n? Da sau nu? Și acceptați sau respingeți în consecință. Acum, dacă b este mai mare decât 1, veți încerca toate configurațiile intermediare posibile, numindu-le c mid. Acesta a fost ca w din teorema anterioară. Acestea sunt toate șirurile posibile c-- toate configurațiile posibile c mid. Și o configurație va fi doar o... până acum până acum... OK. Toate acestea sunt posibile. Părea că PowerPoint-ul meu s- a prăbușit, dar pare OK. Acestea sunt toate configurațiile posibile, care este doar un șir cu un șir de simboluri de bandă cu un simbol de stare care apare undeva. Asta e tot. Vom încerca toate configurațiile posibile ca configurații intermediare candidate. Și spuneți că pot ajunge de la cel de sus la cel de mijloc candidat și de la cel de mijloc la cel de jos în jumătate din numărul de pași de fiecare dată. Și rezolvarea acestei probleme în mod recursiv. Așa că am o întrebare aici despre posibilitatea de a face buclă pentru totdeauna. În primul rând, dacă n va fi în buclă, nu trebuie să-mi fac griji , pentru că încep, trebuie doar să simulez mașini care sunt decidenți. Pentru că încerc să arăt că orice limbaj de aici trebuie să fie acceptat, trebuie să fie decis de o mașină nedeterministă. Deci nu am de gând să-mi fac griji pentru mașinile care fac buclă. Dacă sunt în buclă, s-ar putea să mă comport prost într-un fel, dar asta nu va fi o problemă pentru mine. Deci haideți să păstrăm viața simplă. Gândiți-vă numai la cei care decid. Deci vom testa recursiv aici. Deci asta înseamnă că voi încerca fiecare mijloc posibil, să văd dacă pot ajunge de la început la mijloc și de la mijloc până la sfârșit. Dacă ambele funcționează după ce le testez recursiv, atunci voi accepta. Dacă nu, voi continua. Și resping dacă le încerc pe toate și niciunul nu a funcționat. Apoi știu că nu există nicio modalitate ca n să treacă de la această configurație la acea configurație în b pași. Și imaginea de ansamblu, testez dacă n acceptă w, așa cum am menționat, începând cu ci este configurația de pornire și cj este configurația de acceptare. Și acum cât de mare este? Pentru că trebuie să calculez o limită a cât de adânci vor fi recursiunile. Deci aici va fi numărul total de configurații posibile. Dacă aceasta este totul, nu repetă niciodată o configurație. Deci, acesta va fi o limită cu privire la câți pași pot fi făcuți. Și pur și simplu am calculat asta înainte. Este numărul de stări înmulțit cu numărul de poziții ale capului înmulțit cu numărul de conținut al benzii. Și aceasta va fi oricum considerația dominantă . Și acum, fiecare nivel recursiv, și poate ar fi trebuit să subliniez asta la început, cât de largă este această imagine? Este suficient de mare pentru a stoca o configurație. O configurație este în esență conținutul unei benzi. Deci va fi f din n lățime. Deci, fiecare nivel recursiv stochează o configurație. Acum w costă f din n spațiu pentru a scrie. Și numărul de niveluri va fi jurnalul înălțimii inițiale, care este acesta. Deci aceasta va fi partea dominantă a acesteia. Deci, logul acestuia va fi, din nou, ordinul f al lui n. Deci fiecare ia f din n spațiu pentru a scrie. Adâncimea recursiunii va fi de ordinul f al lui n. Deci, totalul va fi de ordinul f pătrat al lui n și atât spațiu folosește. Și aceasta este dovada teoremei lui Savitch. Deci da, deci acesta este un punct bun acolo. Cineva întreabă dacă există mai multe configurații de acceptare. Ar fi trebuit să fac... Am uitat să spun asta și tocmai îmi dădeam seama în timp ce o explicam. Unul dintre lucrurile pe care ar trebui să le am -- puteți impune că există doar o singură configurație de acceptare. Acesta este un fel de detaliu, așa că nu vă faceți griji dacă nu doriți. Dar vă puteți asigura că există o singură configurație de acceptare, spunând aparatului când acceptă, ar trebui să-și ștergă banda și să-și miște capul în celula cea mai din stânga din configurația de acceptare. Așa că va exista o singură configurație de acceptare de care să vă faceți griji în loc să încercați mai multe posibilități, ceea ce ați putea face în acest algoritm, dar ar fi pur și simplu enervant să trebuiască să scrieți asta în acest fel. Așa că adesea presupunem că va exista o singură configurație de acceptare pentru aceste mașini. De unde știi f din n? Deci, aceasta este de fapt o problemă puțin delicată. Adică, dacă ai putea calcula f din n, limita, care este, de exemplu, dacă va fi o legătură polinomială, poți doar să calculezi f din n. Este foarte ușor să calculezi n pătrat sau n cuburi. Și așa puteți doar să calculați asta și apoi să o utilizați ca dimensiune a registrelor pe care o veți nota. Dacă doriți să demonstrați acest lucru în general pentru f din n, este puțin tehnic să aveți de-a face cu asta. Și va trebui să te refer la cartea despre asta. Cartea vă spune cum rezolvați acest lucru pentru un f general al lui n. Practic, trebuie să încercați toate valorile posibile, de la una până când funcționează. Și mă tem că asta ne va deraia încercând să descifrăm asta. Deci, să nu ne facem griji în privința acestui aspect. Dar puteți gestiona generalul f din n aici. Nu trebuie să puneți condiții pe f din n. Putem trece peste acest termen aici? Așa că am mai văzut acest termen o dată când am vorbit despre LBA și văzând că LBA-urile întotdeauna-- putem rezolva problema ALBA. Acesta este pur și simplu numărul de configurații diferite pe care le poate avea mașina. Pentru că configurația este o stare. Este o poziție a capului și un conținut al benzii. Și acesta este numărul fiecăruia dintre cele pe care le puteți avea. Numărul de state. O poziție a capului, dimensiunea benzii de f din n este f din n. Deci acestea sunt atât de multe poziții diferite ale capului. Și acesta este numărul -- dacă d este dimensiunea alfabetului benzii, acesta este numărul de conținut de bandă pe care îl puteți avea. Cum este să vezi dacă n acceptă w cu acest algoritm să transformi o mașină Turing nedeterministă într-o mașină Turing deterministă? Ei bine, n este Turing nedeterminist. Deci n este că transformăm mașina Turing nedeterministă n la mașina Turing deterministă m. Deci m este un simulator determinist al lui n. Asta este tot acest m. Deci, dacă putem face asta pentru orice n, atunci ne-am demonstrat teorema. De ce nu amânăm. Cred că am trecut peste majoritatea întrebărilor de aici. Dacă mai sunt și alte lucruri, le putem păstra pentru pauza de cafea, care urmează în curând. Cred că mai avem un slide înainte de asta. Așa că voi defini completitatea PSPACE, cred. Da. Și apoi cred că după aceea avem pauză. Deci completitatea PSPACE este definită și foarte mult inspirată în mod similar cu caracterul complet al NP. Deci, o problemă este PSPACE completă dacă este în NPSPACE și orice alt membru al PSPACE este reductibil la ea în timp polinomial. Și vom spune puțin despre motivul pentru care alegem aici reductibilitatea timpului polinomial. Așadar, iată o imagine a modului în care PSPACE-- cât de complete se leagă problemele cu clasele lor de complexitate. Deci te gândești la o problemă completă pentru o clasă. Este oarecum cea mai grea problemă din acea clasă pentru că poți converti. Puteți reduce orice altă problemă din acea clasă la problema completă. Deci, aici sunt problemele NP complete. Un fel de cel mai greu pentru NP. Aveți problemele PSPACE complete, cam cele mai grele pentru PSPACE. Dacă o problemă NP completă intră în P, aceasta trage în jos tot NP la P. Dacă orice problemă PSPACE completă intră în P, aceasta trage în jos tot PSPACE în P urmând lanțul de reduceri, deoarece orice problemă PSPACE este reductibilă la problema completă. Care, la rândul său, dacă este în P, atunci totul intră în P. Deci, dacă aveți o problemă completă PSPACE care este în P, atunci tot PSPACE intră în P. Deci de ce folosim reductibilitatea timpului polinomial în loc de, să zicem, spațiul polinomial reductibilitatea atunci când definim această noțiune? Este un fel de întrebare foarte rezonabilă. Dar dacă te gândești bine, folosirea reducției spațiului polinomial ar fi o idee teribilă. Și am mai văzut că acest fenomen s-a întâmplat. Fiecare două probleme din PSPACE vor fi reductibile PSPACE una la alta. Nici măcar nu am definit încă această noțiune, dar vă puteți imagina care ar fi. Pentru că o reducere PSPACE poate rezolva problema pentru o problemă din PSPACE. Și apoi își poate direcționa răspunsul oriunde îi place. Deci, în general, când ne gândim la reduceri, reducerea ar trebui să nu fie capabilă să rezolve problemele din clasă. Pentru că dacă ar putea, atunci fiecare două probleme din clasă ar fi reductibile una la alta. Și atunci toate problemele din clasă ar fi complete, pentru că totul din clasă ar fi reductibil la oricare dintre celelalte probleme. Deci nu ar fi o noțiune interesantă. Ceea ce vrei să se întâmple este ca reducerile să fie mai slabe decât puterea clasei. Și dacă te uiți la reducerile pe care le-am definit până acum, ele sunt de fapt foarte simple. Singurul lucru este că trebuie să se asigure că pot face ieșirea suficient de mare. Dar, de fapt, construind rezultatul, sunt transformări foarte simple . De fapt, chiar și timpul polinom este mai mult decât aveți nevoie de obicei. Există chiar și clase mult mai limitate care sunt capabile să facă reduceri, după cum vom vedea. Deci, a avea reduceri puternice nu este într-adevăr în spiritul reducerilor. Vrei ca transformări foarte, foarte simple să fie reducerile. Oricum, sper să fie de ajutor. Deci, ceea ce vom urmări în a doua parte a prelegerii este să arătăm că TQBF este PSPACE complet. Și lasă-mă... iată check-in-ul. Deci acesta este primul nostru check-in, venind puțin târziu în prelegere. Să presupunem că am dovedit că, așa cum vom face, că TQBF este PSPACE complet. Ce putem concluziona dacă TQBF nu este de fapt neapărat în P, merge doar la NP? Și acest lucru este relevant pentru o întrebare care vine din chat, dar voi răspunde mai târziu. Deci, să presupunem că TQBF ajunge să fie un NP și nu în P. Ce putem concluziona? Amintiți-vă, dacă TQBF este în P, atunci PSPACE este egal cu P. Să presupunem că merge la NP. Ce se întâmplă atunci? S- ar putea să existe mai multe răspunsuri corecte aici. Bifați tot ce se aplică. Bine, deci suntem aproape de finalul sondajului. Așa că permiteți-mi să vă mai dau încă 10 secunde și apoi o vom opri. OK, suntem cu toții? Închizând-o. Iată rezultatele. Deci da, deci în primul rând, cea mai rezonabilă soluție, cel mai rezonabil răspuns este b, pe care cred că majoritatea dintre voi l-ați primit. Că, dacă o problemă completă PSPACE se reduce la NP, ei bine, NP este capabil să simuleze reducerea timpului polinomial . Și astfel orice altă problemă în PSPACE ar fi atunci și în NP. Și PSPACE ar fi egal cu NP. Dar rețineți că dacă PSPACE este egal cu NP, ele sunt, de asemenea, NP egal cu coNP, deoarece PSPACE însuși este închis sub complementare. Deci ăsta a fost un pic un fapt în plus pe care ai putea trage concluzia și din asta. Deci, să trecem apoi la pauza noastră de cafea și vom ridica dovada că TQBF este PSPACE complet după aceea. Deci a fost adevărat sau nu? D a fost P egal cu NP. Nu, nu putem concluziona că P este egal cu NP din PSPACE egal cu NP. Deci dacă TQBF este în NP, nu ne spune nimic. Din câte știm, P este egal cu NP. Dar din lucrurile pe care le știm până acum, nu putem concluziona că P este egal cu NP. Oh, și da, așa că poți trage concluzia... oh, îmi pare rău. B și d sunt ambele corecte aici. Lasă-mă să închid chestia asta. Deci b și d sunt corecte. Deci, dacă o problemă completă PSPACE ajunge la NP, atunci NP este egal cu PSPACE, N este egal cu conp. Deci răspunsul corect, b și d. Îmi pare rău. M-am încurcat. Dar c nu este ceva la care poți concluziona sau a. Deci cineva îmi pune o întrebare corectă. Eu spun că metoda de reducere ar trebui să fie mai slabă decât clasa. Dar, de exemplu, chiar și în cazul PSPACE, PSPACE ar putea fi egal cu P. Și atunci nu ar fi mai slab decât clasa dacă folosim reduceri de timp polinomiale. Dar cred că ar trebui să spun că aparent mai slab. Din câte știm, este mai slab. Dar credem că este mai slab. Este adevărat dacă P este egal cu PSPACE, atunci fiecare problemă din P va fi PSPACE completă. Va fi o lume ciudată dacă P este egal cu PSPACE. Același lucru pentru NP și NP. Așa că primesc o serie de întrebări și despre alte posibile reducbilități care sunt chiar mai slabe decât reducbilitatea în timp polinomial. Deci, vom vedea foarte curând clase de reducere-- complexitate mai slabe în P. Deci, în primul rând, PSPACE pare să fie mai mare decât P. Ne vom uita și la spațiul de jurnal. Dar asta va fi de fapt în prelegerea de joi. Acestea sunt clase care par să fie înăuntru. Ei bine, sunt în interiorul P. Credem că sunt în mod corespunzător în interiorul P. Dar vom vedea asta mai târziu. Lasă-mă să văd aici. Așa că aproape că nu mai avem timp. Lasă-mă să pun cronometrul înapoi. De fapt, cronometrul nostru ne afișează din timp. Deci de ce nu mergem? Lasă-mă să mut asta înapoi la... OK. Continuând. TQBF este PSPACE complet. Deci, în primul rând, să ne amintim de TQBF. Acestea sunt toate formulele booleene cuantificate care sunt adevărate. Deci, TQBF înseamnă Formule booleene cuantificate adevărate. Și amintiți-vă, am văzut aceste exemple din prelegerea anterioară că acestea sunt două cuantificate - acestea sunt două QBF-uri. Primul este adevărat. Al doilea este fals. Și va fi interesant de gândit. Aici sunt exact aceleași, cu excepția ordinii cuantificatorilor. Și ce se întâmplă cu adevărat aici? Cred că este bine să înțelegi aceste expresii. Ei apar peste tot în matematică, acești cuantificatori. În cea de sus, când spunem pentru fiecare x, există un y, că y poate depinde de alegerea lui x. Tu alegi să faci un alt x. Ai voie să alegi un alt y. Dar expresia inferioară spune că există un y universal. Există un anume y care funcționează pentru fiecare x. Deci, într-un sens, afirmația inferioară este o afirmație mai puternică. Orice ai în partea gratuită a cuantificatorului. Deci cel de jos îl implică pe cel de sus. Se întâmplă că cel de jos în acest caz este fals și cel de sus este adevărat. Dar, în general, atunci când aveți această schimbare de cuantificatori ca aceasta, cea de jos ar implica cea de sus. Oricum, asta e un fel de observație secundară. Deci, să revenim la dovada că TQBF este PSPACE complet. Acesta este scopul nostru. În regulă. Acum, așa cum am menționat, aceasta este aceeași dovadă. O să-l vezi pentru a treia oară astăzi. Dar există o anumită cantitate de... este un fel de schimbări de context în fiecare caz. Deci acum vrem să arătăm că TQBF este PSPACE complet. Deci, este una dintre aceste probleme cele mai grele acum, dar pentru PSPACE, unde satisfacabilitatea a fost cea mai grea problemă pentru NP. Deci vrem să arătăm că fiecare limbă din PSPACE este reductibilă la TQBF. Și așa vom oferi reduceri de timp polinomiale care mapează o anumită problemă a, care poate fi făcută în spațiul n la k. Este o problemă care poate fi rezolvată în PSPACE. Vom arăta cum f mapează a la TQBF. Trebuie să construim f. Deci f va fi o mapare care mapează șiruri care pot fi sau nu în a. Deci șirurile w, care pot fi sau nu în a, la aceste formule, aceste formule cuantificate. Deci w va fi mapat la o formulă phi sub mw. Avea exact aceleași simboluri pare pe care le-am folosit atunci când demonstrarea teoremei Cook-Levin despre SAT fiind NP completă. Aceasta este o dovadă foarte asemănătoare. Dar vei vedea că trebuie să facem ceva mai mult ca să funcționeze în acest caz. Deci w este într-un dacă și numai dacă această formulă va fi în TQBF. Cu alte cuvinte, dacă și numai dacă această formulă este adevărată. Deci această formulă va exprima într-un fel faptul că m acceptă w, ceea ce înseamnă că w este în a, deoarece m este mașina, este mașina PSPACE pentru a. Deci această formulă spune că m acceptă w și se realizează prin construirea unei simulări a lui m pe w. Descrie într-un fel o simulare pentru m on w care ajunge să accepte. Și dacă m nu acceptă w, acea descriere va fi inevitabil falsă. Deci haideți să vedem cum va arăta. Deci vom folosi aceeași idee pe care am folosit-o pentru teorema Cook-Levin că SAT este NP complet. Această noțiune de tablou. Deci, dacă vă amintiți, era practic un tabel care era doar o modalitate de a scrie un istoric de calcul pentru m on w. Deci rândurile sunt treptele mașinii. Rândul de sus este configurația de pornire. Rândul de jos este, să zicem, o configurație specială acceptată, așa cum tocmai am descris-o, unde aparatul își șterge benzile și își mișcă capul spre capătul stâng. Deci, există o singură configurație care acceptă de care trebuie să ne îngrijorăm. Și fiecare dintre rândurile de aici este o configurație a lui m. Deoarece m rulează în spațiu în k, tabloul într-un fel similar cu ceea ce am descris mai înainte are lățimea n la k. Deci acum vorbim despre mașini polinomiale a timpului. Deci f, care este limita, spațiul legat, va fi un polinom n la k. Deci, lățimea acestui tablou, dimensiunea acestor configurații vor fi de la n la k. Cât de înalt va fi acest tablou? Ei bine, asta va fi limitat de timpul posibil de funcționare al mașinii, care este similar cu ceea ce am văzut înainte. Va fi exponențial în spațiu. Deci, va fi de la d la n la k, unde d este în esență alfabetul de bandă al mașinii. Deci suntem toți împreună la asta? Acest lucru este foarte asemănător cu dovada SAT este NP completă. Diferența cheie acolo era m era nedeterministă, la care ar putea fi ceva la care să ne gândim mai târziu. Dar să nu ne concentrăm pe asta chiar acum. Acest m este determinist. Dar diferența importantă era forma tabloului. Mărimea tabloului era foarte diferită. În cazul în care SAT este NP complet, am început cu o mașină nedeterministă în timp polinomial. Deci ar putea rula doar pentru un număr polinom de pași. Iată o mașină spațială polinomială, care poate rula pentru un număr exponențial de pași. Aceasta va fi o diferență importantă aici. Deci, să vedem de ce. Reducerea trebuie să construiască această formulă phi sub a lui mw, care practic spune că acest tablou există. Acum, am văzut deja cum să facem asta când am demonstrat teorema Cook-Levin că SAT este NP complet. Amintiți-vă, am avut toate astea. Aveam variabile pentru fiecare celulă care ne spuneau care este conținutul acelei celule. Și atunci am avut multă logică aici. Aveam o grămadă de logică care spunea că toate acele cartiere erau corecte, ceea ce spune practic că tabloul corespunde unui calcul corect al mașinii. Deci de ce nu facem același lucru? De ce nu ne construim formula folosind exact același proces pe care l- am folosit pentru a construi formula când aveam SAT fiind NP complet? Ceva nu merge bine. Nu prea putem face asta. Problema este că, dacă vă amintiți, formula pe care am construit-o înainte era într-adevăr la fel de mare ca tabloul. Pentru că avea o logică pentru fiecare dintre celule. Avea un set de câteva variabile pentru fiecare dintre celule și avea o anumită logică pentru fiecare dintre acele cartiere, practic. Deci spune că fiecare dintre celule face ceea ce trebuie. Deci a fost o formulă destul de mare, dar era totuși polinom. Problema este că tabloul este acum n la k cu d la n la k. Acesta este un obiect exponențial de mare. Deci, dacă formula ta va fi la fel de mare ca tabloul, nu poți spera să produci acea formulă în timp polinomial. Și asta e problema. Formula va fi prea mare. Amintiți-vă, încercăm să obținem o reducere a timpului polinomial din acest limbaj a. Deci avem o intrare la a, un șir care ar putea fi un a, care simulează mașina. Și dimensiunea tabloului în raport cu w va fi ceva enorm. Și astfel formula este la fel de mare ca tabloul. Nu există nicio modalitate de a produce acea formulă în timp polinomial. Deci asta nu va funcționa. Hai sa incercam din nou. Deci acum avem aici-- acum, deci amintiți-vă această notație de la ci la cj în b pași. Deci vom oferi un mod general de a construi formule care exprimă acest fapt pe care îl pot obține de la configurația i a lui m la configurația j a lui m în b pași. Oricare ar fi acel b. b va fi oarecum legat. Și vreau să știu dacă pot trece de la această configurație la acea configurație. Și vreau să notez asta ca o formulă, care va exprima acest fapt. Și va fi fie adevărat, fie fals. Și vă voi oferi o construcție recursivă pentru această formulă. Deci voi construi acea formulă pentru o valoare b din formule pentru valori mai mici ale lui b. Deci acesta va fi o modalitate de a construi acea formulă în termenii altor formule pe care le voi construi. Și va exista o bază pentru recursivitate atunci când b este egal cu 1. Deci asta este imaginea de ansamblu. Deci, să vedem cum arată această formulă. Deci, să nu ne facem griji cu privire la cazul pentru b egal cu 1 chiar acum. Acesta este cazul valorilor mai mari ale lui b. Deci, faptul că pot ajunge de la ci la cj în b pași. O să scriu asta în acest fel. Și hai să încercăm să despachetăm asta și să vedem ce scrie. Fără să ne îngrijorăm cum vom duce acest lucru, să încercăm să înțelegem la un nivel înalt de semantică a acestui lucru ce încearcă să vă spună. O să spună, bine, pot ajunge de la ci la cj în b pași. Deci m poate ajunge de la ci la cj în b pași. Dacă există o altă configurație c mid, o altă configurație, o numesc c mid, foarte inspirată de demonstrația anterioară a teoremei lui Savitch , unde a existat c mid a fost acea configurație intermediară. Așa că acum, în loc să le încerc pe toate, spun că există unul în care să pot ajunge de la ci la c mid în jumătate din numărul de pași și de la c mid la cj în jumătate din numărul de pași? Deci, dacă pot construi aceste două formule, atunci le pot combina cu acest fel de chestii suplimentare aici și le pot pune împreună și să pun un cuantificator existent care spune, există o configurație, o modalitate de a găsi o configurație astfel încât funcționează așa cum cer aceste formule? Dacă pot face asta, atunci voi fi bun. Pentru că atunci pot... bine, bine. Cel puțin voi fi bun în ceea ce privește realizarea unui lucru care să funcționeze. Deci, în primul rând, să înțelegem ce vreau să spun prin a scrie dacă există c mid. Într- adevăr, dacă te gândești la modul în care am făcut teorema Cook-Levin, am reprezentat aceste configurații prin variabile care erau variabile indicatoare pentru fiecare dintre celule. Și vom face exact același lucru. Deci vom avea o grămadă de variabile booleene care vor reprezenta o configurație. Deci, mai formal, sau mai detaliat, ceea ce face acest lucru, există un c mid, într-adevăr este o atribuire tuturor acelor variabile care reprezintă conținutul celulelor acelei configurații. OK, deci acum să vedem cum să... cum va funcționa recursiunea? Deci, pentru a obține această valoare aici, voi face recursiunea în continuare. Deci, există un c mid? Și acum pentru a ajunge de la ci la acest c mid, mai există vreun alt c mid? Aceasta este ca o altă valoare a lui w din diapozitivul anterior în care primesc, din nou, reduc din nou numărul de pași la jumătate . Deci trec de la b peste 2 pași la b peste 4 pași. Și o să fac același lucru aici. Așa că dezvăluiesc construcția acestei formule în termeni de construcție - construind-o recursiv. Și apoi voi continua să fac asta până când ajung la cazul în care b este 1. Și dacă acum încerc să fac o formulă care va fi, să zicem că pot ajunge de la ci la cj doar într-un un singur pas. Deci, este vorba de fapt despre un tablou de înălțime 1 sau înălțime 2. Atunci pot doar să scriu direct asta în modul în care eu -- acum tabloul nu este foarte mare. Așa că acum pot scrie asta folosind cartierele și așa mai departe, ceea ce am făcut în demonstrația teoremei Cook-Levin. Și așa puneți totul împreună. Și acum, dacă vrei să vorbim despre obținerea de la accept w. Deci inițial spun, pot trece de la configurația de pornire la configurația de acceptare în t pași, care este timpul maxim de funcționare al mașinii? Deci din nou. Și dacă m-ai urmărit, ceea ce s-a întâmplat în teorema lui Savitch, sunt aceleași valori. Acum, chestia este că trebuie să înțelegem cât de mare este această formulă. Și dacă te gândești bine, e o problemă. Pentru că ce se întâmplă aici? Exprim această formulă în termeni de formule în care dimensiunea lui b este tăiată la jumătate. Dar acum sunt doi. Deci sunt două formule pe jumătate din valoarea lui b. Aceasta nu va fi o recursivitate care va funcționa în favoarea noastră. Deci, să vedem ce se întâmplă. Deci, fiecare nivel recursiv dublează numărul de formule. Aici avem două formule. Aici vom avea patru formule și așa mai departe. Deci numărul de formule se dublează de fiecare dată. Deci, lungimea obiectului pe care îl scriem se dublează de fiecare dată când coborâm recursiunea. Va fi în regulă dacă nu trecem la prea multe niveluri. Dar, din păcate, mergem la câteva niveluri, pentru că numărul de niveluri va fi log al acestui lucru cu dimensiunea exponențială inițială. Deci va fi n la k niveluri. Și așadar, dacă dublezi ceva de n la k ori, vei ajunge cu o formulă de mărime exponențială. Și din nou, am eșuat. OK, deci am o verificare. Dar poate că ar trebui să petrecem câteva minute doar încercând să înțelegem ce se întâmplă aici. Pentru că următorul diapozitiv este într-adevăr ultimul meu diapozitiv și va rezolva această problemă. Dar haideți să ne asigurăm că înțelegem care este problema înainte de a încerca să o remediem. De ce nu mai putem scrie peste fiecare strat al recursiunii așa cum am făcut în scară? Oh, asta e o întrebare grozavă. Ce înseamnă chiar să scrii peste diferite... ei bine, deci asta e o întrebare interesantă aici. Deci, într-un fel, asta va fi soluția. Vom reutiliza lucrurile într-un anumit fel. Dar vreau să înțelegeți că această metodă în sine nu funcționează, deoarece această recursivitate aici, unde scriu formula, construiesc formula pentru b din formule pentru valori mai mici ale lui b. Dacă o fac în acest fel, voi ajunge... dacă o fac așa cum este descris în această procedură aici, voi ajunge cu o formulă exponențial de mare. Și asta nu este suficient de bun. Deci, dacă tăiați formula în jumătate de fiecare dată, chiar dacă aveți două formule, lungimea nu va fi aceeași? Nu tai formula la jumătate. Reduc valoarea lui b la jumătate. Deci trebuie să spuneți că b este inițial o valoare exponențial mare. Așa că vom ajunge cu o formulă exponențial de mare. Deci nu înseamnă cu adevărat să tai formula la jumătate. Tăierea b în jumătate. b începe mare. Adică, b este inițial această valoare aici, d la n la k. Sunt ingrijorat. Nu prea multe întrebări aici. Am un sentiment că probabil nu este un semn bun. Ei bine, vreau să spun, dacă ești iremediabil confuz, poate că nu o pot rezolva repede. Deci, oricum, de ce nu mergem mai departe și vedem cum să reparăm asta, cum să remediam această problemă. Și asta va fi printr-un truc. De fapt, îi cunosc pe cei care au fost implicați în ideea asta. Aceasta a fost de fapt, această dovadă a fost făcută inițial la MIT cu mulți ani în urmă, în anii 1970. Iar cei care au fost implicați în asta l-au numit trucul de abreviere. Așa că asta vom face în următorul diapozitiv. Oh, nu, e un check-in mai întâi. De ce să nu fim surprinși că această construcție eșuează? A, ei bine, nu putem-- doar noțiunea de a defini o formulă booleană cuantificată prin utilizarea recursiunii nu este permisă. Deci nu poți defini formule așa. Nu folosește nicăieri cuantificatorul for all. Sau pentru că știm că TQBF nu este în P. Puteți vedea că facem... ce părere aveți? De ce să nu fim surprinși? Presupun că aș fi putut pune un d acolo. Nu e surprins pentru că nu știi ce se întâmplă. Acesta este un alt motiv pentru a nu fi surprins. Dar oricum, sper că aveți o licărire a ceea ce se întâmplă aici. Și de ce nu... aproape am terminat. Așa că o să închid asta într-o secundă. Ultimul apel. OK, se încheie. În regulă. Deci, de fapt, răspunsul corect este b. Adică, ar trebui să fie suspicios că dacă nu există pentru toți care apar în această construcție oriunde. Deci, de fapt, ceea ce facem este că construim o formulă care are doar calificatori existenți. Deci este o problemă de satisfacție. Deci, ceea ce tocmai am făcut a fost că am construit-- am făcut într-un mod mai complicat construcția Cook-Levin, pentru că ajungem cu o formulă SAT doar cu cuantificatori existenți. Și așa că încercați unul și încercați două au fost la fel. Așa că nu este surprinzător că ajungi cu o formulă exponențial de mare ca rezultat. Nu știu. Mulți dintre voi ați răspuns că știm că TQBF este în P. Nu este în P. Nu știm asta. Nu știu unde... ce se întâmplă cu voi băieți? Dar nu. Poate că a fost un vot de protest. Dar oricum, noi nu știm asta. Și, oricum, ce legătură are asta cu ceva? Deci oricum, sa vedem. Rezolvăm acest lucru în câteva minute rămase aici. Deci iată soluția. Amintiți-vă, această parte în care spunem că încercăm să găsim c mid, există un c mid astfel încât să pot ajunge de la ci la c mid în jumătate din numărul de pași și c mid la cj în jumătate din numărul de pași . Exprim o formulă în termeni de două formule. Acolo are loc lovitura. Pentru că acești doi sunt, atunci, în termeni, vor fi fiecare-- așa că acești doi vor deveni 4, vor deveni 8 și asta nu este bine. Pot exprima acest fapt în termenii unei singure formule? Și acest fel de puțin în spiritul sugestiilor tale. Putem reutiliza lucrurile într-un fel? Și asta o să facem de fapt. Deci, iată un alt mod de a spune același lucru, dar cu o singură formulă. Și folosește un pentru toți. Și ideea din spatele lui este că un și este un fel ca un pentru toți. Sau un pentru toți este un fel ca un și. La fel ca în există ca un fel de sau. Deci, când spui că există ceva, este acest lucru sau acel lucru sau acel lucru sau acel lucru? Și când spui pentru toți, are chestia asta și chestia aceea și chestia aceea și chestia aia. Și pentru toate sunt foarte legate. Și așa vom transforma asta și într-un pentru toți. Vom spune pentru toate configurațiile cg și ch care sunt fie setate la ci c mid sau la c mid cj, formula cg ch-- Pot ajunge de la cg la ch în jumătate din numărul de pași. Deci, trebuie să vă gândiți la ce înseamnă asta aici. Și vreau, de asemenea, să mă asigur că nu simți că te înșel, pentru că ei bine, în primul rând, așa că acum avem doar o singură formulă. Vom merge la cazul b egal cu 1, așa cum am făcut înainte. Trebuie să vă asigurați că a spune acest lucru restricționat pentru toți nu este o înșelăciune. Când aveți pentru tot x este în s, așa cum avem aici, este echivalent cu a spune pentru tot x dacă x se întâmplă să fie în s, atunci urmează celălalt lucru. Și această implicație poate fi exprimată folosind și și sau. Și ca și înainte, punctul de pornire inițial va merge de la c start la c accepta în t pași. Și astfel analiza pe care o obținem este că, deoarece nu mai există o explozie, fiecare nivel recursiv adaugă doar aceste lucruri aici în față. Există c mid și asta pentru toate părțile. Deci, asta va fi adăugarea ordinului n la formulă în loc să înmulțim, deoarece avem două formule. Și acum numărul total de niveluri este de ordinul n la k, ca înainte. Deci dimensiunea va fi n la k ori n la ordinea k n la 2k. De fapt, am avut o scurtă verificare aici, pe care aș vrea să o faci doar în câteva secunde rămase. Această construcție depinde de faptul că m este determinist? Așa că lasă-mă să lansez asta. Vreau să vă primiți cecul de credit aici. Dar, de fapt, trebuie să te gândești la asta. Formula spune că tabloul, obții un tablou. Va conta asta în funcție de faptul că este determinist sau nedeterminist? De fapt, ei bine, este cam 50/50 aici. De ce nu alegi ceva? Pentru că aș vrea să închid asta și să ajung la ultimul nostru slide. Așa că, dacă nu urmezi, nu-ți face griji. Dar este de fapt un punct interesant că faptul că asta... așa că voi încheia asta. Toate în? Deci, de fapt, răspunsul corect este că ar funcționa în continuare dacă este nedeterminist. Și asta ți-ar oferi o modalitate alternativă de a demonstra teorema lui Savitch. Deci, într-adevăr, totul se reduce la această demonstrație, care implică teorema lui Savitch și apoi, la rândul său, implică problema DFA ladder. Deci, oricum, aceasta este o notă secundară, care nu este critică pentru înțelegere, într-adevăr. Puteți să le luați ca toate separate, rezultatele și asta este suficient de bun. Bine, așa că revin. Hopa. Revenind. Asta am făcut. Și astfel, fiecare nivel recursiv, dimensiunea QBF nu este aceeași. Cineva întreabă dacă este același la fiecare nivel recursiv. Nu, a trebuit să adăugăm... să vedem. Fiecare recursivitate. Aceasta este construită recursiv aici, dar acum trebuie să adăugăm această parte în față și această parte aici în față. Deci, cuantificatorul care este cuantificat pe o mulțime de variabile reprezentând configurația, care se adaugă la fiecare nivel. Deci nu este doar că rămâne la fel. Sunt lucruri care se adaugă. Dar ceea ce este important este că nu explodează exponențial. Lucrurile sunt adăugate de fiecare dată, dar nu se înmulțesc. BINE. Deci am terminat aici. Deci oricine, toți puteți decola. Cred că mulți dintre voi aveți deja. Pa! Pa. Mulțumesc.