deci am vorbit despre p și np și despre clasele de complexitate a timpului și astăzi vom schimba treptele, vom vorbi despre complexitatea spațială sau complexitatea memoriei, deoarece complexitatea spațială este la care se referă de obicei teoreticienii complexității. așa cum știi că timpul și spațiul sunt cele două măsuri de bază ale complexității pe care le considerăm și așadar astăzi ne vom uita la a doua dintre aceste două, complexitatea spațiului, așa că vom defini multe dintre acestea vor fi prin analogie cu ceea ce am făcut pentru complexitatea timpului, vom defini clasele de complexitate, vom vorbi despre spațiu polinomial și spațiu polinomial nedeterminist, um vedem cum aceste clase se conectează cu clasele de complexitate temporală. pe care le-am definit deja și vom face câteva exemple care ne vor pregăti pentru discuția noastră ulterioară despre complexitatea spațiului săptămâna viitoare, așa că vom vorbi în primul rând despre ce înseamnă pentru o mașină de turnat să ruleze într-un o anumită cantitate de spațiu și asta va fi pur și simplu numărarea numărului de celule pe care mașina de turing le scanează pe banda sa în timpul calculului său, s-ar putea să citiți acea celulă ar putea fi scris pe acea celulă, dar numărul total de celule care de fapt, vizitează, desigur, vizitarea aceleiași celule de mai multe ori contează o singură dată, deoarece spațiul poate fi reutilizat, dar vom număra numărul de celule pe care mașina de turing le vizitează în timpul calculării sale și apoi vom defini utilizarea spațiului prin analogie cu ceea ce am făcut pentru timp, așa că vom spune că o mașină de turnat rulează într-o anumită cantitate de spațiu f n vom spune dacă mai întâi de toate trebuie să țină mereu, astfel încât toate mașinile să fie decisive și să folosească cel mult atât uh bandă atât de mult încât vizitează acel număr de celule pe toate intrările de lungime n, așa cum am spus pentru complexitatea timpului, mașina trebuie să ruleze în interval de t din n timp pe toate intrările de lungime n aici va trebui să folosească cel mult f din n celule pe toate intrările de lungime n pentru ca acesta să ruleze în spațiu f nu bine, o celulă de bandă este pur și simplu un pătrat mic al benzii în care puteți scrie un simbol, în regulă, răspunzând la o întrebare acea întrebare bună care a venit de la chat, așa că știi, uh, nu sunt sigur că avem o diagramă pentru asta, dar um din fiecare dintre pătratele mici de pe bandă vor fi celulele de bandă, în general, vom rămâne lipiți de o singură bandă. mașini, dar voi face o scurtă observație despre multi-bandă în timpul prelucrării mai bine să luați celule scuze uh pentru toate intrările de lungime n uh așa că reveniți acum bine, deci asta este pentru mașinile de turnare deterministe uh pentru mașini de turneu nedeterministe vom spune uh că rulează, de asemenea, într-o anumită cantitate de spațiu, astfel încât pentru o mașină nedeterministă trebuie să folosească cel mult atâtea celule de bandă pe fiecare ramură a calculului său separat, nu adunați numărul total de celule utilizate în toate ramurile. la fel cum nu adunăm timpul total pe care îl folosește mașina în toate ramurile sale pentru ca mașina să ruleze în spațiu, să zicem în spațiu n pătrat, trebuie să le folosească cele mai multe n celule pătrate sau să comande n celule pătrate pe fiecare dintre ramurile sale nedeterministe, separat, ar putea exista exponențial multe ramuri, dar este în regulă, dar pe fiecare ramură va folosi cel mult n pătrat sau va ordona n celule pătrate, deși este important, totuși, mașina trebuie să fie un hotărâtor, nu este suficient să fie buclă pentru totdeauna și folosind o cantitate mică de spațiu, ar putea face asta, dar asta nu va conta pentru ca mașina să contribuie la complexitatea sa spațială a acelui limbaj, așa că pentru ca mașina să ruleze într-o anumită cantitate de spațiu, spunem că mașina ține. pe toate ramurile sale și fiecare dintre ramurile sale folosește cel mult atât de mult spațiu, bine din nou, pot vedea o mulțime de greșeli de scriere aici, mulțumesc, am încurcat toate astea azi, ceva bun nedeterminist. Mulțumesc, bine, așa că suntem Vom defini clasele de complexitate spațială analoge cu aceste clase de complexitate temporală, astfel încât acestea sunt limbaje pe care le puteți face cu mașini care rulează în acel spațiu limitat, deci um spațiu f n vă puteți gândi la spațiu n pătrat um este toate limbajele care sunt deterministe mașina de curățat bandă um poate face în interiorul uh poate decide în interiorul utilizând în majoritatea celulelor cu bandă n pătrată sau comanda celule cu bandă n pătrată, în mod similar, clasa de complexitate spațială nedeterministă sunt toate limbajele care sunt nedeterministe. decideți să rulați în acea cantitate de spațiu bine și, în sfârșit, avem un spațiu polinomial, astfel încât aceasta este uniunea peste toate limitele spațiului polinomial ale clasei de complexitate spațială și spațiului polinomial nedeterminist, este aceeași pentru toate clasele de spațiu polinomial nedeterministe. deci cred că am o verificare pe acest umhoops care vorbește despre mașinile de turnat cu mai multe benzi, astfel încât să putem defini complexitatea spațiului pentru mașinile de turnat cu mai multe benzi, așa cum am făcut, adică pentru o singură bandă. mașini și apoi definiți clasele de complexitate a spațiului asociate și apoi definiți spațiul clasei p, dar asta ar fi pentru mașinile multi-turing acum, uh, amintiți-vă că clasa p pe care ați obține-o de la mașinile de turnat cu mai multe benzi este exact aceeași cu clasa p că am luat pentru o mașină de turnat bandă um, asta făcea parte din calitatea plăcută a clasei p este robust în acest sens un firesc, deci ce zici pentru p spațiu um ce crezi că obținem aceeași clasă um nu poate sau da pentru că putem converti o mașină de strunjit cu mai multe benzi într-o singură mașină de strunjire a benzii doar prin pătrarea cantității de spațiu, um, asta a fost ceea ce s-a întâmplat cu timpul, după cum vă amintiți sau poate putem face și mai bine convertind o mașină de turneu cu mai multe benzi într- o singură bandă. o crește cu mai puțin, să zicem un factor constant aici. Amintiți-vă cum definim astfel complexitatea spațiului pentru mașinile de turnat cu mai multe benzi, luăm în regulă suma tuturor celulelor utilizate pe toate benzile, așa că hai să lansăm asta Sondaj și vedeți ce credeți, sper că nu este prea greu, da, cred că majoritatea dintre voi au înțeles ideea, deși unii dintre voi sunteți, uneori îmi fac griji pentru unele dintre răspunsurile pe care le primesc, nu știu dacă vorbiți serios sau ești într-adevăr foarte confuz, dar oricum hai să încheiem asta încă 10 secunde sau așa, hai să sunăm bine, o voi termina, da, vreau să spun, cred că răspunsul b este un răspuns rezonabil, de fapt, răspunsul c este răspunsul corect uh, poți dacă te uiți la aceeași simulare de la multi-bandă la o singură bandă și la cât spațiu deasupra capului acea simulare introduce, um este doar liniar, practic iei toate benzile mașinii cu mai multe casete și le scrii lângă unii pe alții, evident că știți, ignorând toate infinitele infinite de spații libere, luăm doar porțiunea activă a benzilor notându-le una lângă alta, astfel încât suma totală folosită va fi doar suma de pe banda unică a ceea ce a fost folosit pe fiecare dintre benzile multiple individuale din mașina originală, astfel încât există doar un cost general liniar prin conversia de la multi-bandă la o singură bandă atunci când vă uitați la spațiu, cantitatea de memorie folosită pentru timp. să actualizăm unde erau capetele virtuale și asta a costat timp suplimentar pentru a ne mișca singur capul pentru a face asta, dar pentru spațiu, cantitatea de timp introdusă nu este la fel de irelevantă, ne uităm doar la cantitatea de memorie și așadar ăsta este un link care merge la doar uh, știi că cheltuielile generale sunt foarte scăzute, mi-aș face griji pentru oamenii care răspund, de exemplu, la această întrebare, ar trebui să te regândești la ce se întâmplă cu adevărat aici um uh, așa că bine, acum haideți să trecem aici de la acela la următorul nostru diapozitiv și să comparăm clasele de complexitate în timp și spațiu pe care le cunoașteți sau complexitatea timpului și spațiului cum se relaționează una cu cealaltă și, în primul rând, vom analiza subliniază um hai să începem de aici t din n va fi reprezentat de o anumită limită fie pe timp, fie pe cantitatea de spațiu și, în general, cel puțin până în acest punct, um și majoritatea în continuare, deși va exista o variație despre asta puțin mai târziu, dar ne vom concentra asupra limitelor uh care sunt cel puțin suficient de mari pentru a citi intrarea sau cel puțin pentru a menține intrarea, de aceea ne referim la t din n fiind cel puțin n um, deci acum dacă ne uităm la clasa de complexitate a timpului t din n gândiți-vă la acel t din n ca, de obicei, ar fi să spunem n pătrat poate și lucrurile pe care le puteți face în n timp pătrat susțin că le puteți face și în n spațiu pătrat um și, practic, um folosește exact aceeași mașină să presupunem că aveți o mașină care rulează în timp n pătrat, cum ar putea folosi să spunem n pătrat n spațiu cub dacă rulează numai în n timp pătrat, chiar dacă încearcă să folosească cât de mult ar putea cât de multe celule de bandă ar putea și știi, trimițându-și capul în porțiunea oarbă a benzii, mestecând cât mai multe celule de bandă, în n timp pătrat, va putea fi folosit doar n spațiu pătrat, așa că aceeași mașină care rulează în t din n timp va rula și în t spațiu de evenimente um, așa că această limitare de aici urmează, știi cu adevărat fără a face um nicio treabă um, așa că reafirmă asta aici um a uh mașina de transformare care rulează în t din n pași nu poate folosi mai mult de t din n celule de bandă, bine, așa că acum ne concentrăm asupra am putea dovedi câteva afirmații analoge despre complexitatea nedeterministă, dar haideți să ne concentrăm aici pe complexitatea deterministă acum să ne uităm dacă mergem în cealaltă direcție să presupunem că avem o mașină de turnare care folosește t din n spațiu, asta înseamnă imediat că folosește doar t din n și timp și asta nu este atât de clar și, de fapt, probabil că nu este adevărat, deoarece un spațiu pare a fi mult mai mult puternic decât timpul și într-o anumită cantitate de spațiu, poți rula mult mai mult decât aceeași perioadă de timp, deci cât timp ai putea alerga, așa că ceea ce poți arăta este că dacă rulezi într- o anumită cantitate de spațiu t spațiu de evenimente să spunem n spațiu pătrat, de exemplu, timpul pe care l-ați putea folosi va fi exponențial în n pătrat a 2 la ordinul n pătrat uneori scriem că, ca uniunea lui c cu um n pătrat printr-un fel de tragere coborâți acea constantă aici, dacă doriți bine, este, de asemenea, să înțelegem ce înțelegem prin ordinul t al lui n în sus în exponent, înseamnă că uniunea dintre c cu t din n pentru toate c oricare dintre acestea sunt complet echivalente, deci oricare dintre ele. te simți mai confortabil, dar de ce va fi acest lucru adevărat de ce o mașină de turnat care rulează spune um uh spune n spațiu pătrat folosește cel mult două la ordinea n timp pătrat și asta pentru că dacă te uiți la câte posibilele configurații pe care le poate avea aparatul Amintiți-vă că o configurație este, în esență, conținutul benzii, aceasta este și poziția capului și starea, dar aspectul dominant al unei configurații este banda și, deci, câte conținuturi diferite de bandă puteți Ei bine, va fi exponențial în ferăstrău pe lungimea acelei benzi, pentru că știi că fiecare celulă poate avea un număr fix de simboluri în ea dacă o mașină repetă o configurație, va rămâne pentru totdeauna, ceea ce interzicem în tine. știți în aceste mașini, deoarece toți vor fi hotărâtori, astfel încât să poată rula doar pentru o perioadă de timp, care este limitată de numărul de configurații pe care le poate avea mașina și astfel mașina poate avea să știți dacă este rulează în t din n spațiu, atunci perioada de timp în care ar putea rula va fi cel mult o constantă la t din n sau două de ordinul t evenimente care spun același lucru uh uh știi dacă nu se va repeta o configurație și se termină în buclă, deci acestea sunt cele două conexiuni fundamentale dintre timp și spațiu. Timpul este conținut în aceeași cantitate de spațiu. conținut în spațiul p, în mod similar, np va fi conținut într-un spațiu np din același motiv um ok este de înțeles știi că acesta este un loc bun sau într-o clipă să mai avem o linie la to to să-ți spun despre dar duce la următorul diapozitiv, așa că dacă înțelegeți definițiile a ceea ce am făcut până acum, toate acestea, aceasta este o teoremă destul de simplă, iar corolarul este imediat în regulă, deci tot ce puteți face în timp n pătrat poți face un spațiu n pătrat și deci, dacă poți face ceva în timp polinomial, poți face și în spațiu polinomial da c mă întreabă cineva, știi care este c c va fi în esență dimensiunea benzii alfabetul um pentru că asta va guverna câte configurații diferite aveți, există un factor uh în plus, parcă știți un factor în plus pentru bandă um locația capului și, de asemenea, starea um, dar principalul lucru va fi numărul de simboluri de bandă și lungimea benzii sunt în regulă, dar ceea ce va urma este că vom demonstra ceva mai puternic decât acest corolar că p este conținut în spațiul p, deoarece nu numai p este conținut în spațiul p, dar np este și el. conținute în spațiul p și pentru asta va trebui să facem mai multă muncă, așa că cineva mă întreabă despre numărul de stări de care se va stabili numărul de stări depinde de independent, în funcție de mașină, așa că ei o face. nu depind de uh, depinde de n, așa că ar putea afecta în cea mai mare parte configurațiile numerelor printr-un factor constant și acești factori constanți vor fi absorbiți în definițiile acestor clase de complexitate, pentru că așa i-am defini ca fiind uh. știi să ignori factorii constanti, dar știi de ce nu luăm doar un știi că acesta poate fi un loc bun pentru a face o pauză pentru o secundă și a vedea dacă există întrebări, deoarece știi că cred că pentru unii dintre voi acest lucru poate fi simplu. dar știi, cred că este mai puțin obișnuit să măsori gândindu-te la cantitatea de memorie ca măsură de complexitate, așa că poate este puțin mai puțin familiar, unii dintre voi ați văzut măsurând timpul și alte clase, dar amintiți-vă că măsurați cantitatea de spațiu care algoritmul folosit este probabil un pic mai puțin familiar și poate că merită să petrec un moment sau două răspunsuri la întrebări despre asta, așa că nu sunt sigur că am înțeles întrebarea care tocmai a apărut, dar o voi citi acolo. este posibil ca o mașină de turing să poată face bucle pentru totdeauna, dar o mașină de turing care face bucle pentru totdeauna nu contează ca una care rulează în spațiul limitat să ruleze în spațiul limitat, mașina trebuie să se oprească la fiecare intrare, trebuie să fie un hotărâtor doar că suntem luând în considerare factorii de decizie aici, este posibil ca mașina de întoarcere să arate pentru totdeauna, da nu este mașina de turnat despre care vorbim despre un membru al spațiului și, prin urmare, un decident, nu sunt complet sigur că înțeleg întrebarea, dar dacă o mașină de turnat nu se oprește toate intrările nu este un hotărâtor care este definiția noastră, suntem buni și nu primim foarte multe întrebări aici, așa că presupun că sunteți cu mine sau atât de rătăciți încât nici nu știți ce să întrebați, ceea ce nu este bine um, fiți îndrăzneț dacă sunteți confuz, aruncați întrebarea noastră acolo, pentru că nu vreau să parcurg această prelegere, deoarece poate este un pic mai puțin familiară pentru unii dintre voi, bine, așa că hai să mergem mai departe, așa cum am promis. Îți voi arăta acum că np nu numai p așa cum este se întâmplă imediat, dar np este conținut ca un subset al unui spațiu p, așa că oh, nu am primit o întrebare la care am continuat înainte de a răspunde la această întrebare. Pot să explic o parte două din dovada din nou partea a doua, bine, să o facem, umh, dacă ceva rulează într-o anumită cantitate de spațiu, trebuie să te gândești la câte configurații diferite poate avea mașina în acea cantitate de spațiu ține minte configurațiile pe care le-am definit cu mult timp în urmă la lbas um, deci numărul de configurații pe care le poate avea mașina depinde de cât spațiu este alocat, ca și lbas-ul, aveau un număr fix de configurații și am dat un calcul pentru acel um, care este practic un exponențial în cantitatea de spațiu care este câte configurațiile pe care le poate avea mașina, așa că, dacă mașina nu este o buclă, dacă este un decident, nu poate repeta niciodată o configurație și asta ne va spune cât timp poate funcționa mașina, pentru că știi că este o este important să înțelegem. Nu sunt sigur dacă știam cum să spun că în vreun fel să fie atât de diferit de ceea ce am spus înainte, dar um, bine, mă întorc acum să demonstrez că np este un subset al spațiului p, așa că acum va trebui să facem ceva care este într-un fel diferit de ceea ce am făcut în diapozitivul anterior, deoarece acum nu va fi suficient să lucrezi cu aceeași mașină înainte, când facem conversie, arătăm că o anumită perioadă de timp clase de timp conținute într-o clasă spațială a fost în virtutea aceleiași mașini, arătând doar că, dacă rulează într-o anumită perioadă de timp, atunci trebuie să ruleze în aceeași cantitate de sp în aceeași cantitate de spațiu um sau în ceea ce privește spațiul în care se afla x, având o anumită cantitate de spațiu, trebuie să ruleze aceeași mașină într-o anumită perioadă de timp, aici vom amesteca non-determinism și determinism, așa că va trebui să luăm o mașină care este într-un np tastați mașină o mașină a timpului polinomistă nedeterministă și convertiți-o într-o mașină deterministă care nu folosește mult spațiu, așa că există o diferență în caracterul acestei teoreme, deoarece trebuie să introducem o nouă mașină și modul în care vom" Voi dovedi că voi profita de unele dintre lucrurile pe care le-am arătat deja pentru a demonstra că acesta ar putea dovedi, de asemenea, un pic mai direct și poate că merită înțeles, asigurându-vă că înțelegeți ambele dovezi, astfel încât Primul lucru pe care îl voi observa este că în limbajul nostru complet np, limbajul de satisfacție în sine este un membru al spațiului p și motivul este atunci când vi se dă o formulă și acum doriți să testați dacă acea formulă este o modalitate satisfăcătoare de a o face, cea mai evidentă modalitate de a o face este să încerci toate sarcinile una câte una și să vezi dacă vreuna dintre ele satisface formula acum, asta va dura mult timp, dar cât spațiu folosește am în minte reutilizarea spațiul de fiecare dată când încercăm următoarea temă, gândiți-vă să parcurgeți toate sarcinile așa cum ar funcționa un odometru, încercând doar toate sarcinile posibile, dar reutilizand spațiul în care veți scrie acea sarcină, um fel de incrementând-o ca pe un numărul um scris în binar dacă doriți să parcurgeți toate sarcinile posibile de fiecare dată când intrați în următoarea temă, îl conectați la formulă și vedeți dacă formula este satisfăcută dacă este, atunci puteți accepta imediat dacă nu treceți la următoarea sarcină și numai când ați parcurs toate sarcinile în acest fel și niciuna dintre ele nu a îndeplinit formula, atunci puteți respinge, așa că cât spațiu folosește acel spațiu care nu folosește mult spațiu pentru că sunteți reutilizarea spațiului um pentru a nota o sarcină după următoarea, bine, va folosi doar o cantitate de spațiu suficient de mare pentru a susține o sarcină care este practic liniară, deoarece este dimensiunea numărului de variabile ale formulei, așa că va merge. a fi o cantitate liniară de spațiu pentru a rezolva problema de satisfacție și astfel problema de satisfacție este cu siguranță în spațiul p um pasul unu pasul doi este vom profita de ceea ce știm despre reductibilitate um deci dacă a este timp polinomial reductibil la b am comentat deja că nu am spus acest lucru exact în acest fel, dar știți că va urma în continuare că orice puteți face într-un anumit interval de timp, puteți face și în acel spațiu, deoarece există aceeași mașină um nu poate folosi mai mult spațiu decât timpul care i-a fost alocat, așa că, dacă a este timpul polinomic reductibil la b, va fi, de asemenea, reductibil în spațiu polinomial, o mașină spațială polinomială ar putea face reducerea, așa că înseamnă că dacă a este timp polinomial reductibil la b și b este în spațiu polinomial, atunci a este și în spațiu polinomial, dar știm, deoarece satisfacibilitatea este np-completă, fiecare limbaj al lui np este reductibil la sat, așa că puneți sat în locul lui b fiecare limbaj np este polinom timp reductibil la sat și acum știm că sat este în spațiul p, așa că, prin urmare, fiecare limbă din np este în spațiul p, deoarece toate sunt reductibile în timp polinomial pentru a seta bine, deci doar folosind o parte din tehnologia pe care am dezvoltat-o și anume noțiunea de completitudine ne arată cumva o parte din puterea sa că, dacă doriți să concluzionați ceva despre o întreagă clasă, o întreagă clasă de complexitate, dacă aveți o problemă completă pentru acea clasă de complexitate, de multe ori este suficient să lucrați cu problema completă și apoi cu toate celelalte prin virtutea reductibilității va moșteni aceeași proprietate, nu funcționează în toate cazurile, dar în multe dintre cazuri atâta timp cât um cunoașteți, reductibilitatea poate fi calculată de um după tipul de procedură la care lucrați cu um, atunci poți, apoi urmează, uh, știi că ai putea demonstra asta mai direct, cred că este, în anumite privințe, puțin stângaci sau puțin mai puțin elegant, dar poți spune bine, lasă-mă să-mi iau o limbă care este în np are un algoritm de timp polinomial nedeterminist și apoi oferă un algoritm de spațiu polinomial determinist simulează acel algoritm np doar parcurgând toate ramurile diferite, dar asigurându-vă că, trecând prin toate acele ramuri diferite, reutilizați spațiul și nu folosiți spațiu nou de fiecare dată când treceți printr-o ramură diferită și puteți aranja lucrurile dacă sunteți puțin atent să o faceți astfel, astfel încât să puteți oferi o simulare directă în spațiu polinomial a oricărei mașini de turnat uh np, astfel încât înseamnă că este, de asemenea, complet satisfăcător, dar cred că este puțin mai elegant, așa că acum haideți și asta, în plus, ne va permite să concluzionăm că unele limbi suplimentare sunt în spațiul p, să definim o clasă pe care nu am văzut-o încă, deși poate ați văzut asta Cred că am vorbit despre asta această noțiune de uh co înainte de um cred că am vorbit despre co-turing reduceb co touring recognoscible um, deci clasa, acestea sunt clasa de limbi ale căror complemente devin recognoscibile și la fel pentru co și p aceasta este clasa de limbi ale căror complemente sunt în np, așa că luați complementul fiecărei limbi care este în np și acum obțineți toate limbile care sunt în această clasă co np complement de np um, deci, de exemplu, complementul problemei handpath deci toate graficele care nu au căi hamiltoniene de la uh, știți estetică, deci graficul non-hamiltonian uh problema căii non-hamiltoniene este o problemă cohen p um ei bine, aici este o limbă pe care nu o avem, nu sunt Vom defini uh ca în ceea ce privește complementul său, este o problemă de tautologie, deci acestea sunt limbajul problemei, acestea sunt toate formule sau acestea sunt formulele în care toate sarcinile satisfac formula, toate atribuțiile fac formula adevărată, deci o tautologie este o afirmație care este întotdeauna adevărat, deci indiferent de modul în care conectați variabilele, limbajul tautologiei este în co-np um, deoarece este complement, care sunt non-tautologiile, acestea sunt formulele pentru care um, există o atribuire care o face falsă, așa că va fi să fie în mod clar un limbaj np, deci tautologia este un limbaj co și p bine, acum un lucru pe care îl obținem imediat din teoremă ca corolar ar trebui să scriem asta ca corolar este că cohen p este, de asemenea, un subset al spațiului p și motivul pentru adică și acesta este ceva despre care știi că este din nou ușor, dar asigură-te că înțelegi că spațiul p în sine este închis sub complement, deoarece este definit în termeni de mașini deterministe și mașini deterministe, poți oricând să răstoarne răspunsul și să obții o mașină. de același tip, care um uh uh va decide limbajul complementar, așa că pentru mașinile deterministe decidenți determiniști ar trebui să spun um, puteți oricând răsturna răspunsul um acum, așa că aici avem orice este în spațiul p are un timp polinom determinist un spațiu polinomial uh mașină și deci linia sa complementară care va fi, de asemenea, în spațiul p, astfel încât p spațiu și baza cos p co p spațiu sunt egale și de aceea coen p uh va fi în spațiul p va fi o submulțime a spațiului p Bine, sper că asta nu se amestecă cu toate diferitele supe cu alfabet de aici, dar uh, aici este poate o imagine, poate care va fi de ajutor, uh, despre cum arată lumea pentru timpul și condimentul orei de complexitate până acum. avem p este un submult al lui np este, de asemenea, un submult al lui conp um din nou din același motiv pentru care p și co p sunt egali, nu vorbim niciodată cu adevărat despre copie, deoarece este la fel ca p um uh, dar np și cohen p asta Acestea sunt două clase în care nu știm dacă sunt egale sau nu, pentru că o mașină np um, știi că nu poți completa neapărat comportamentul unei mașini np și ajunge la o mașină np, așa că o întrebare cum facem Știți că cohen p este o clasă completă de probleme, nu am spus că există ceva despre completitudine și cohen p este doar o colecție de limbi, nu spun că este ceva anume, de fapt, are o problemă completă. cum np are o problemă completă completă, complementele și nu voi dovedi acest lucru chiar aici, dar, deși este destul de simplu, completările tuturor limbilor np-complete vor fi limbi co-np-complete um și um, deci uh așa că Sunt atât de bine, așa că hai să răspund la câteva dintre întrebările despre sau despre posibilele lumi alternative, așa credem că arată lumea, fiecare dintre aceste regiuni fiind separate una de cealaltă, inclusiv acest mic colț de lume aici, np și intersectează co-np care nu este um ar putea exista limbi aici care nu sunt în p și de fapt credem că există astfel de limbi, dar din nou toate acestea sunt conjecturale um și chiar dacă spațiul p și p sunt la fel sau diferit este un ONU este o întrebare deschisă, nici nu știm răspunsul la ceea ce este poate și mai șocant că nu știm cum să rezolvăm pnn știi dovedit p diferit de np că nu știm cum să dovedim p diferit de p spațiu, care pare a fi o clasă mult mai mare, uh, ar fi incredibil că orice puteți face cu o cantitate polinomială de spațiu, uh, puteți face și cu o cantitate polinomială de timp, dar nu știu cum să demonstrez că sunt diferit și, de fapt, așa ar putea arăta lumea, totul s-ar putea prăbuși p ar putea fi egal cu p spațiu și apoi toate aceste clase ar fi aceleași și ar trebui să menționez, de asemenea, că nu am asta ca o altă diagramă aici, dar doar pentru a răspunde, știi că există și o altă poziție, există alte posibilități, de exemplu, um p ar putea fi egal cu np fără să fie egal cu p spațiu și atunci ai avea o diagramă Venn cu aspect diferit aici, unde ar fi doar două clase p np și co np ar fi toate aceleași p spațiul ar fi diferit, ceea ce este posibil, cel puțin nu avem idee, a avut un cap de m. Multe dintre aceste lucruri se pot prăbuși în diferite moduri și trebuie doar să vă asigurați că știți că există unele prăbușiri că, evident, nu s-ar putea întâmpla ca p dacă p este egal cu np, de asemenea, va fi egal cu cohen p um, așa că nu puteți obține unele, există evident niște prăbușiri nebunești care nu s-ar putea întâmpla ca p să se prăbușească p și np să fie la fel, dar diferit de cohen b asta nu se poate întâmpla, dar evitând unele situații contradictorii evidente, totul este posibil, așa că cineva a spus atât de bine, iată o întrebare, permiteți-mi să răspund la câteva dintre acestea, dacă am folosit completitatea co np pentru a arăta că cohen p este un submult de spațiu co-p nu, nu am făcut-o așa, am arătat că uh co-np um uh bine hai să vedem nu suntem așa de corect um bine presupun că știi că np de submulțime de p spațiu implică imediat pentru că el completează ambele părți, că cohen p este un subset al spațiului de copiere, astfel încât nu trebuie să vă ocupați de problemele complete de pe cealaltă parte, care este prea complicat pentru a intra aici, dar nu trebuie să vorbiți despre co-vid probleme complete um, deși din nou, acestea sunt foarte simplu de obținut de la np probleme complete um hai să vedem ce altceva este aici uh există probleme complete np care sunt în co-np, așa că răspunsul la asta este nu, nu atât de departe, vreau să spun acolo ar fi dacă ar exista o problemă np completă în co-np, atunci toate np ar fi în cohen p și ar fi egale, așa că bănuim că problemele np complete nu sunt în co și p, dar nu știu cum să demonstrăm asta de ce este tautologia în cohen p, deci aici este tautologia se află în această clasă aici motivul este că limbajul său complementar este un np complementul tautologiei sunt limbile în care există o anumită atribuire care face formula falsă, așa că cu a cu o mașină np pot doar să ghicească acea sarcină și să verifice dacă face formula falsă, astfel încât complementul tautologiei este un limbaj np și deci tautologia este un limbaj co-np, bine, așa că cineva întreabă despre spațiul p și spațiul np și cum se leagă acestea cu unul pe celălalt, așa că ne uităm la ceea ce vom face săptămâna viitoare, dar vă voi oferi o previzualizare o teoremă veche, dar surprinzătoare la acea vreme, a fost că baza piesei și spațiul np sunt de fapt egale, așa că există această analogie cu timpul se defectează, astfel încât spațiul polinomial și spațiul polinomial nedeterminist se dovedesc a fi egale, cea mai evidentă modalitate de a demonstra că încercarea de a simula un np o mașină spațială np ar fi să vă oferim un algoritm de spațiu determinist exponențial, așa că vom trece prin asta dar există un algoritm care prăbușește spațiul polinomial nedeterminist până la spațiu polinom determinist, care din nou la acea vreme era oarecum surprinzător, uh, așa că ultima întrebare pe care o voi lua aici există un concept echivalent cu ideea unui certificat pentru co- np da, există o noțiune de certificat, dar acum va fi un certificat că nu ești în limba în loc de un certificat că ești în limba și apoi funcționează din nou din același motiv pentru care am avut certificate pentru np limbi în care ați avut certificat de apartenență la cohenp aveți un certificat de non-aderare. Vom privi câteva exemple importante, acestea sunt exemple pe care le vom vedea, am să vă dau două exemple, primul numit tqbf și apoi vom avea un al doilea exemplu, ambele pe care le vom merge pentru unul dintre ele va fi un exemplu de problemă în spațiul p, celălalt va fi un exemplu de problemă în spațiul np și acestea vor fi limbi importante pentru noi, așa că nu vor fi doar pentru a servi drept exemple pentru astăzi, dar știți că vor fi limbi utile pentru noi mai târziu, așa că țineți cont de asta pe măsură ce trecem prin asta, așa că pentru a înțelege tqbf trebuie să înțelegeți ceea ce se numește cuantificat formule booleene sau qbfs, deci acestea sunt formule booleene la fel ca cele pe care le-am văzut despre care am vorbit cu variabilele booleene și și-urile sau și și variabilele negate, dar acum vei adăuga cuantificatori, cuantificatori existenți pentru toți cuantificatorii dacă nu ați văzut cuantificatori, trebuie să vă întoarceți și să le revedeți, știți, cred că am cam introdus am vorbit despre ele pe scurt mai devreme în termen, dar asta face parte din matematica de bază care trebuie să știți că poate nu vă veți simți confortabil cu ele, o veți relua oarecum în cursul prelegerilor de astăzi și al următoarelor câteva, dar oricum uh, așa că, dacă aveți o formulă booleană, vă voi da câteva exemple care au există și pentru toți cuantificatorii, una dintre cerințele pentru ca acesta să fie un qbf este ca toate variabilele să fie în domeniul de aplicare al unuia dintre cuantificatori, astfel încât toate variabilele formulei trebuie să fie cuantificate de unul dintre cuantificatori. și vom presupune că cuantificatorii sunt în față sunt un fel de cuantificatori principali în fața restului uh a restului expresiei, așa că, pentru că toate variabilele au fost cuantificate, se va desfășura o formulă booleană cuantificată. să fie adevărat sau fals, urmând semnificația cuantificatorilor um și, din nou, unele dintre acestea pot deveni clare pe măsură ce facem câteva exemple, uh, bine, deci iată câteva exemple, deci aici este unul aici este un qbf, deci toate variabilele care sunt doar x și y apar amândoi în fața uh lângă un cuantificator, așa că asta va fi o cerință uh dacă avem un qbf și deci asta spune că pentru tot x există un y această expresie este valabilă, așa că trebuie să despachetăm asta. și înțelegeți ce înseamnă că spune pentru fiecare x pentru fiecare pentru fiecare mod de a atribui o valoare booleană lui x, așa că uh x va fi fie adevărat, fie fals, există o modalitate de a atribui o valoare booleană pentru y pentru a determina ca acest lucru să fie adevărat. pentru ca restul expresiei să fie adevărat, um și vom trece prin asta, dar haideți să o contrastăm cu al doilea exemplu în care inversez ordinea cuantificatorilor pentru că asta va fi important pentru sensul formulei, așa că dacă am spuneți că pentru fiecare x există un y, ceea ce face ca restul să fie adevărat, care spune bine, indiferent de modul în care am stabilit x, va exista o modalitate de a seta y pentru a face acest lucru adevărat, astfel încât să spună bine dacă setez x la adevărat, trebuie să fi o modalitate de a seta y să facă ca expresia rămasă să aibă um, așa că dacă am spus x la adevărat, ce ar trebui să setez y să fie um bine uh dacă am spus că x este adevărat și poate am spus că y este adevărat bine atunci această clauză este satisfăcută, dar această clauză nu va fi satisfăcută, așa că setarea y ca fiind adevărată nu este că nu va funcționa, dar pentru fiecare x trebuie doar să arăt că există un y, așa că dacă aleg x să fie Adevărat, pot spune că este fals și acum acesta este acesta este valabil și acesta este valabil și formula este valabilă, dar trebuie să mă asigur că acesta va fi cazul pentru ambele setări ale lui x pentru că spun pentru toate x deci dacă am spus că x nu este fals pentru că am arătat deja că funcționează pentru x egal cu adevărat dacă setez x la fals dacă setez acum y ca adevărat, aceasta va fi valabilă, deci această expresie este adevărată pentru că este cazul că pentru fiecare mod de a seta x există o modalitate de a seta y, astfel încât această parte să fie valabilă, să ne uităm, să comparăm asta cu acest caz, există o modalitate de a seta y astfel încât, indiferent cum am spus x, asta va fi valabil și nu este va fi adevărat, indiferent de ceea ce alegeți pentru y um, va exista o modalitate de a seta x pentru a face acest lucru fals, așa că rezistă unui y astfel încât fiecare x ne face adevărate nu dacă încercați x egal cu adevărat, nu va fi adevărat. funcționează dacă încerci x egal cu fals, nu va funcționa, așa că această a doua expresie fi2 cuantificată qbf este falsă, bine ne vom juca foarte mult cu acestea, așa că este important să înțelegem cum funcționează această cuantificare, deci tqbf este problema de a testa dacă unul dintre aceste qbfs este adevărat sau exprimat ca o limbă este colecția de qb adevărat qbfs și de aici obținem um uh acronimul uh tqbf nu acronimul abrevierea tqbf pentru formulele booleene cuantificate adevărate, așa că revenind înapoi la acel exemplu p1 este o formulă booleană cuantificată adevărată și v2 nu este o formulă de construcție cuantificată adevărată, de aceea p1 este în limbajul v2 nu este în limbaj acum problema noastră de calcul este să testăm dacă formulele booleene cuantificate sunt adevărate sau nu și acum putem face în spațiu polinomial oh, există o verificare în primul rând, susțin că sat este un caz special al tqbf de ce așa putem să ne gândim la sat ca un caz special dacă vă dau o formulă sat, cum pot să văd și asta o problemă tqbf dacă doriți să testați dacă acea formulă este adevărată, ce ați spune că eliminați toți cuantificatorii sau adăugați câțiva cuantificatori și ce fel de cuantificatori poate um uh cum se află doar să testăm o formulă satisfăcătoare un caz special al acestui lucru susțin că este o problemă mai generală de rezolvare a acestor probleme tqbf bine închiderea să numim da, într-adevăr, știți satisfacția, deci c este corect când vorbiți despre o problemă de satisfacție, spuneți dacă există o sarcină satisfăcătoare, o altă modalitate de a o nota este să luați Formula booleană reprezintă luați acea formulă booleană și puneți există în fața tuturor variabilelor spunând că există o există există există o modalitate de a seta x1 și x2 și x3 și x4 pentru a face formula adevărată, faceți ca formula să fie valabilă, deci um sat este un caz special prin adăugarea de cuantificatori existenți ai unei probleme tqbf, deci c este corect um bine, deci de ce este această problemă în spațiul p așa cum am susținut și pentru asta vom oferi un algoritm recursiv simplu um în orice uh o formulă booleană cuantificată acum, dacă doriți să testați dacă este adevărat sau nu, știți că, practic, vom elimina cuantificatorii principali, așa că, dacă este un cuantificator existent, îl vom elimina și vom introduce adevărat și fals asociat variabilei sale și apoi vom rezolva acele probleme. recursiv bine, deci aceasta va fi doar o procedură recursivă pentru rezolvarea problemelor tqbf care operează prin eliminarea cuantificatorilor din față și obținerea de formule din ce în ce mai mici, dar acum vom introduce valorile adevărate și false în loc de bazându-ne pe cuantificator uh to um uh to to to uh, dă-ne sensul formulei bine, deci, în primul rând, dacă nu există cuantificatori, atunci nu există variabile, deoarece toate variabilele trebuie să fie legate în cuantificatori și, în acest caz, uh asta formula booleană cuantificată trebuie să fie pur și simplu afirmația adevărată sau afirmația falsă și, prin urmare, veți scoate în mod corespunzător pentru că asta este tot ce poate fi dacă nu aveți variabile um dacă formula începe cu un cuantificator existent ceea ce veți face deci aici psi este restul formulei după ce eliminați acel cuantificator existent, așa că veți evalua psi acum, dar luați acea variabilă care a fost legată de exist și conectați adevărat um sau și, respectiv, fals, astfel încât să mergeți pentru a obține două, acum noi probleme um și uh rulați-le uh și evaluați-le folosind aceeași procedură recursiv uh, dar acum cu x conectat pentru adevărat conectat pentru x și, de asemenea, apoi cu plug-in fals pentru x și obțineți răspunsurile pentru cele două cazuri și dacă unul dintre ei a ajuns să accepte, atunci vei accepta pentru că știi că există o valoare uh pentru x care face ca totul să fie adevărat, pentru că tu tocmai ai arătat recursiv că a existat o astfel de valoare, știi fie că este adevărată. sau fals lucrul este acceptat și dacă ambele eșuează, atunci vei respinge și aceeași idee, dacă ai un cuantificator pentru toate, vei evalua din nou restul formulei cu x egal cu adevărat și false, deci două subprobleme, dar acum le veți cere să accepte ambele, deoarece acesta este sensul pentru tot ceea ce ambele atribuiri la x trebuie să facă formula adevărată, așa că le veți evalua recursiv și le veți accepta pe ambele. adevărat, așa cum este determinat de recursivitatea dvs., bine, deci cât spațiu folosește asta, nu voi trece prin asta în detaliu, dar fiecare nivel recursiv folosește doar o cantitate constantă de spațiu, așa că de fiecare dată când faceți o recursivitate aveți să vă amintiți că uh acea valoare uh acea atribuire a acelei variabile pe care doriți să vă gândiți la recursivitate ca fiind implementată pe o stivă, așa că veți doar să apăsați pe stivă acea valoare a acelei variabile care este atât de adevărată sau falsă, deci practic, este o bucată de memorie pe care o vei avea nevoie de fiecare dată când renunți la recursivitate, trebuie doar să-ți amintești ce știi în ce caz la care lucrezi dacă x este adevărat sau x egal cu fals uh și um, deci fiecare nivel recursiv implică doar spațiu constant și profunzimea recursiunii, știi cât de mult ar trebui să-ți amintești bine, va fi cel mult unul pentru fiecare cuantificator, um, pentru că știi că le eliminați ca mergi în jos recursiunea, astfel încât aceasta va fi cel mult lungimea formulei care spune cea mai mare parte a numărului de cuantificatori pe care îl poți avea și, deci, cantitatea totală de spațiu folosită de aceasta va fi um doar n ordine n bine, deci această problemă este rezolvată în uh în spațiu n și de aceea este în spațiu p bine, cred că asta este tot ce am vrut să spun despre asta, bine dacă avem banda și o mașină de strunjit ca memorie într-un computer modern ce face controlul finit corespunde controlului finit corespunde doar unei memorii suplimentare finite, um banda este o cantitate nelimitată de memorie uh sau dacă punem limite, știți că cantitatea de bandă va fi să spunem n memorie la pătrat unde n este lungimea lui n n este lungimea intrării, deci um da, ambele sunt amintiri, dar controlul finit este că nu crește cu n, așa că va fi doar o cantitate constantă de memorie care ar fi complexitatea timpului complexitatea timpului acestui album ar fi proastă, va fi exponențială, așa că ar trebui să verificați asta, dar va fi ceva de genul 2 la numărul de variabile pe care le aveți două la numărul de cuantificatori plus o mică suprasarcină pentru evaluând formula de mai multe ori, dar va fi exponențial, um, care va răspunde pentru tine, așa că cineva cere să se întoarcă din nou la co-np și de unde știm că există o problemă în cohen p care este co și p complet am făcut-o nu definesc nici măcar ce înseamnă asta, dar co-np-complete înseamnă că vom începe să vedem alte exemple de completitudine pentru diferite clase de complexitate, în special unul dintre lucrurile care se vor întâmpla marți, vom vedea o problemă care este completă pentru p space, de fapt, va fi tq tqbf un fel de a privi înainte va fi o problemă completă bazată pe piese, dar chiar trebuie să avem noțiunea a ceea ce înțelegem prin uh complet pentru aceste alte clase și în cazul co np a problema este co și p completă dacă este în co np și orice altă problemă co np este redusă în timp polinomial la ea, așa că exact la fel ca și pentru np, doar conectați conexiunea în schimb și trebuie doar să lucrați prin logica, dar este destul de simplu, complementul oricărei probleme np complete va fi o problemă co-np-completă folosind acea definiție, uh, așa că nu vreau să trec prin acești pași simpli, dar poți să verifici offline. că asta va fi adevărat și cred că probabil vom vorbi despre asta mai târziu în semestru, deci o altă întrebare cum funcționează algoritmul tqbf ah, aceasta este o întrebare bună aici, de ce este algoritmul tqbf pe care tocmai l-am descris în p spațiul nu face lucrul de fiecare dată când fac recursiunea nu se ramifică, astfel încât ajung să folosesc spațiu exponențial lucru critic, ceea ce nu cred că de fapt nu cred că am menționat ceea ce cred că este important. Observați este că atunci când efectuați acele două apeluri recursive când setați x egal cu adevărat și setați x egal cu fals după ce ați stabilit că răspunsul pentru atunci când setați x egal cu adevărat acum reutilizați acel spațiu la fel. spațiu pentru a testa ce se întâmplă când ai x egal cu fals, așa că asta este puterea spațiului care îl face diferit de timp este că poate fi reutilizat, așa că după ce ai răspunsul pentru când ai x egal cu adevărat, acum te eliberezi susține acel spațiu care nu mai este necesar, îți amintești doar răspunsul și acum vezi ce se întâmplă când ai x egal cu fals folosind același spațiu, așa că nu există o explozie exponențială, acesta este un punct important. Mă bucur că mi-ai dat șansa de a spune asta, astfel încât cineva întreabă despre definirea timpului unei mașini de turnat nedeterminat la timpul maxim al fiecărei ramuri, asta este un fel de ceea ce am făcut, poate nu vă înțeleg întrebarea, dar va trebui să o întrebați după după um după aceea, pentru că vreau, nu vreau să amân mai mult decât avem, așa că ne vom întoarce și mergem mai departe aici, bine, al doilea exemplu și acesta este un fel de exemplu distractiv, dar va fi, de asemenea, unul important pentru noi, um se numește ultima problemă acum, așa că este posibil să fi văzut ceva numit cuvântul scară, dar în general o scară este o secvență de șiruri care au toate aceeași lungime, dar sunt consecutive. șirurile diferă într- un singur simbol um, așa că, de exemplu, dacă aveți o literă de cuvânt pentru engleză, va fi o scară în care toate cuvintele sunt englezești, toate șirurile um sunt cuvinte în engleză, așa că iată un exemplu, am crezut că am rezolvat bine aici Este aici o scară de cuvinte pentru engleză și poate le-ați văzut pe acestea presupun că vreau să încerc să merg de la muncă la joacă, dar toate șirurile intermediare uh ar trebui să fie cuvinte în limba engleză cu patru litere care diferă de cea anterioară doar într-o singură. litera și vreau să schimb cumva cuvântul lucru cu cuvântul joc, așa că nu știu dacă știți, de exemplu, pot schimba munca cu carne de porc, așa că iată doar o diferență de literă, um, care se pare că este o îmbunătățire pentru că acum am Sunt de acord cu un acord cu privire la joc, dar uneori știi că s-ar putea să o schimbi, s-ar putea să ai o schimbare bună și apoi trebuie să o anulezi mai târziu, ceea ce cred că de fapt se întâmplă aici, așa că porc, apoi acest port, dar apoi am renunțat la asta progres am făcut port pentru a se potrivi în funcție de slot înțelegeți din nou înțelegeți ce fac aici, în fiecare caz, schimb doar o singură literă, dar toate aceste cuvinte, toate acestea trebuie să fie cuvinte legitime în limba engleză de lungime patru intrigi. și apoi jucați bine, așa că așa ar fi un cuvânt mai ușor în engleză, desigur că o puteți face în diferite limbi și voi vorbi despre asta în mod abstract, unde în loc să am orice limbaj uman natural ca fiind testul uh pentru un cuvânt b pentru că un șir de caractere fiind legitim, voi defini a um orice limbă veche uh hai să spunem că este o limbă va fi un anumit set de șiruri și acestea vor fi șirurile legale care pot fi în scară, deci o scară într-o este o mulțime de șiruri care sunt toate membre ale unui um și acum ultima problemă dfa este a va fi limba unor dfa așa că vă dau b um și așa vreau și apoi un șir de început și un șir n, deci acesta este ca work and play u și v sunt ca work and play, deci unde b este un dfa și limbajul său are o scară care merge de la u la v aici sunt șirurile intermediare bine și în regulă um deci am să vă arăt că această din urmă problemă DFA este în spațiul np bine și nu este, nu este foarte greu, pentru că, practic, ei bine, să ne uităm de fapt la diapozitivul de aici, cum va funcționa este că nu merge determinist. să ghicesc acea secvență de la u la v, așa că, dacă încerc să trec de la serviciu la joc, imaginează-i pe cei pe care îi voi folosi asta așa cum știi tu în loc de limbajul automatului meu artistic. doar pentru că este mai ușor de vorbit despre asta, dar imaginează-ți că acestea sunt șiruri care sunt acceptate de acel dfa um, așa că acum încerc să trec de la șirul meu u la șirul v și vreau să testez pot ajunge acolo prin unii schimbând câte o literă, dar rămânând ca șiruri care sunt acceptate de dfa um, voi doar să ghicesc acea secvență în mod nedeterminist, dar trebuie să mă asigur că am grijă la două lucruri, nu vreau să ghicesc. secvență solidă în avans, deoarece acea secvență ar putea fi exponențial lungă, trebuie să calculați cât de lungă ar putea fi, dar s-ar putea să știți că ați putea schimba la un simbol, apoi o schimbați la un alt simbol, apoi o schimbați înapoi la acel simbol original sau cam așa ceva singura limită pe care o puteți nota este numărul de șiruri posibile pe care le puteți avea de acea lungime, um, așa că ar putea fi exponențial, uh, nu doriți să scrieți totul pentru că va depăși spațiul dvs., dar ceea ce nu ai nevoie, le vei ghici pe rând, uitând de cele anterioare, continuă să ghicești pe următorul uh din secvență și să-ți amintești doar de aceea și să vezi dacă ai ajuns vreodată la șirul dvs. sunteți șirul țintă, dar atunci când faceți asta, trebuie să vă asigurați că nu veți ajunge pentru totdeauna, um, pentru că asta nu este permis în algoritmul dvs. de spațiu np, uh, așa că veți trebuie să păstrați un contor pentru a vă asigura că, dacă depășiți limita care va fi numărul maxim de șiruri pe care le-ați putea avea, atunci veți elimina acea ramură a non-determinismului pe care o veți face. respingeți pe acea ramură, bine, așa că iată că voi scrie pentru a spune asta, aici iată procedura mea nedeterministă, uh, știți procedura de spațiu polinomial, am primit limbajul meu dfab și șirurile mele de început și de sfârșit pe care le las să fie egal șirul de început scrieți lungimea șirurilor mele pe care va trebui să o țin cont pe tot parcursul și apoi voi repeta doar următoarele t ori, unde t este lungimea maximă, care este dimensiunea alfabetului acestor lucruri la a n-a putere, unde m este lungimea acelor șiruri și doar nu voi schimba în mod determinist un simbol la un moment dat, asigurându-mă că rămân în limba, așa că resping imediat dacă acea schimbare a introdus un șir în afara limbii și acceptând dacă acel șir pe care îl obțin schimbând acel simbol unic este acum ținta mea și dacă am trecut prin limita și nu am reușit să ating acea țintă, atunci eu Voi respinge și trebuie doar să observăm că acest algoritm nu folosește prea mult spațiu, așa că, dacă vă imaginați de ce avem nevoie, aici este intrarea mea unv, care are lungimea n și cantitatea totală de spațiu, trebuie doar să-mi amintesc actual y um și um și, de asemenea, contorul meu, contorul meu până la t, deci, fiecare dintre ele poate fi notat cu el cu uh, în esență, în spațiu, astfel încât suma totală va fi ordină n spațiu um, astfel încât să arate că uh aceasta din urmă Problema dfa este de fapt într-un spațiu nedeterminist și nu în spațiu liniar determinist și ceea ce vom arăta în continuare este că acest limbaj este de fapt rezolvabil în spațiul determinist și aceasta este poate un pic o surpriză, bine, deci ce este dimensiunea intrării dimensiunea intrării va fi ceea ce este necesar pentru a scrie uh dfa și uh cele două șiruri u și v um deci uh um aici uh da, vreau să spun că ar fi trebuit să le includ și ca parte a intrării este descrierea lui b în sine, dar um uh, dar asta va funcționa chiar în favoarea mea, deoarece um, deci acest lucru este ușor incorect, deoarece b însuși trebuie să apară ca parte a intrării, așa că scuze pentru asta, dar totuși cantitatea de uh, spațiul folosit va fi ordinul n um, deoarece acestea vor fi de fapt mai mici decât n um, așa că lasă-mă să trec, ca să nu rămânem fără timp pentru prelegere, putem salva întrebări suplimentare pentru care apoi voi rămâne pentru câteva minute, mai am un diapozitiv aici și asta demonstrează această teoremă că scara poate fi făcută în mod determinist în spațiu polinomial și asta va fi important ca un fel de previzualizare a ceea ce vom face. marți și știi dacă asta merge puțin repede, voi trece peste asta din nou marți, așa că hai să vedem cum merge, așa că o să arăt că problema dfa cu aceeași scară este rezolvabilă determinist în spațiul polinomial și de data aceasta este va fi în spațiul pătrat în loc de nedeterminist în spațiul final, așa că va fi un cost, dar va fi doar un pătrat, așa că amintește-ți care este problema, știi că îți dau acel DFA și îți dau două șiruri în limba acelui DFA și vreau să știu pot trece de la primul șir la al doilea șir schimbând câte un simbol pe rând, dar asigurându-mă întotdeauna că șirurile sunt acceptate de acel DFA, bine așa că sunt voi introduce notația care spune că pot ajunge de la șirul u la v printr-o scară, dar acum limitez câți pași pot face, așa că scriu de la u la v, dar o fac numai în șirurile intermediare b b pași, deci există a scara de la u la v de lungime de cel mult b asta înseamnă să scrieți această notație, așa că vă voi oferi o procedură recursivă pentru a rezolva problema scarii mărginite în care este la fel ca înainte, dar acum voi face spuneți că nu numai că există o scară de la u la v, dar există o scară de cel mult lungime b ok, așa că asta îmi va permite să rezolv recursiv această din urmă problemă, micșorând dimensiunea b um uh bine deci haideți cum va fi aceasta. funcționează uh um bine, aici va fi ideea, așa că iată u-ul meu și v um-ul meu și procedura va funcționa în loc să ghicesc nedeterminist pașii care mă duc de la serviciu la joacă pentru că nu am non- determinism mai trebuie să operez determinist ceea ce voi face este să lucrez în loc de eu, în loc să mă uit la primul lucru care decurge de la tine, o să sară chiar la mijloc și Încercați fiecare șir din mijloc posibil, oh, habar nu am nici măcar cum ar trebui să arate acel șir din mijloc, așa că voi încerca toate posibilitățile din secvență, dar apoi voi folosi odată ce voi avea una dintre acele posibilități pe care o voi face Încercați recursiv să rezolvați problema împărțind-o acum, dar acum voi împărți acea valoare b la jumătate, bine, așa că iată valoarea maximă pe care o putem avea, aceasta este t din diapozitivul anterior, care este lungimea maximă um și i uh aici o să încerc toate intermediarile posibile, să începem cu toate a um și acum am tăiat problema la jumătate. toate a sunt de fapt un șir de caractere uh în limbă și dacă ne gândim la limbile, știți cum se potrivesc, este ca și cum engleza, toate a nu sunt un cuvânt legitim, așa că încercați următorul aab și așa o să funcționeze dar acum vei fi, în loc să folosești engleza, o vei introduce în automatul finit, una după alta, încercând toate posibilitățile până când vei ști ca un ceas ca un contor de parcurs, încercând-le pe toate până când în cele din urmă vei găsi un șir care este în limba, reprezint asta printr-un cuvânt în limba engleză capabil, poate acesta este primul cuvânt pe care l-ați fi găsit și apoi, odată ce aflați că veți putea ajunge de la muncă la capabil și să pot juca recursiv reutilizand spațiul din nou, dar acum, unde limita este tăiată în jumătate, bine, așa că acesta este întregul album, așa că parcurg-l repede și vom face asta din nou, um uh, aici este Dfa mea care merge de la u la v în b pași în primul rând oh, asta este rău uh nu ar trebui să fie unul b acesta ar trebui să fie b dacă b este unul um pot repara rapid asta uh, deci aceste t-uri ar trebui să fie b scuzele mele um, deci dacă t este una dacă b este una, atunci trebuie să d atunci mi se permite doar o scară de lungime acum doar verific la media direct dacă tu și v diferit doar într-un singur loc, dacă da, atunci accept altfel resping uh dacă este mai mare de unu acum voi face această procedură pe care l-am descris, voi încerca pentru fiecare posibil w uh la mijloc, um, voi încerca acel w test dacă 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 și cu excepția cazului în care amândoi acceptă um și dacă încerc tot posibilul w nu funcționează niciunul dintre ei, atunci știu că nu există nicio modalitate de a trece de la pașii u la v și b și atunci resping bine și apoi să fac problema inițială care nu a fost problema scarii delimitate fac doar linia delimitata fac problema scarii delimitate unde am introdus t care este lungimea maxima posibila pe care ar putea-o sa ajungi de la serviciu la joc pentru a ajunge de la u la v bine, deci analiza spatiului um Ei bine, nu am mai mult timp aici, așa că vom trece prin asta din nou data viitoare când avem o foarte rapidă, așa că lasă-mă să omit această analiză, o voi revizui data viitoare când am un check-in foarte rapid. vreau doar să ajung la tine, ajung aici, găsește o literă de cuvânt în engleză care leagă cuvântul trebuie de cuvântul vot, te poți gândi la asta, adică nu este atât de greu să găsești o astfel de scară de cuvinte, așa că te încurajez să o faci Gândiți-vă la asta și să vă gândiți la vot, ceea ce este, de asemenea, important, că urmează încă cinci secunde aici. Ok, voi termina asta, așa că asigurați-vă că aveți creditul pentru check-in. Ok, așa că suntem la sfârșit. din oră până la sfârșitul nopții, sfârșitul celor 80 de minute oricum, așa că asta am făcut astăzi și se pare că am trecut peste un minut, așa că scuzele mele, dar voi rămâne aici dacă vreunul dintre voi mai am întrebări, dar în caz contrar, prelegerea s-a terminat, ne vedem, băieți, știm ceva despre scară pentru alte tipuri de limbi. problemă în alte cazuri, în alte cazuri, nu știu bine de ce este aici această valoare a t sigma la m lungimea maximă a um a unei litere de cuvânt, deci ce a făcut ceea ce în primul rând trebuie să m poate ar fi trebuit să scriu acest m jos este lungimea cuvintelor uh sigma este alfabetul cuvintelor um, deci numărul de cuvinte diferite posibile este sigma la m acestea sunt toate cuvintele posibile care ar putea exista, așa că nu există niciun motiv într-un cuvânt ca sau vreodată să repetați cuvântul, deoarece puteți găsi doar o scară de cuvinte mai scurtă care încă face treaba de a conecta la un început la sfârșit, astfel încât să puteți tăia partea din mijloc și partea repetată, astfel încât, în acest caz, cel mai lung posibil cuvântul literă va fi numărul total de cuvinte posibile pe care le puteți avea, care va fi sigma de dimensiunea sigma pentru a explica din nou de ce cohen p este un subset al spațiului p um ei bine, poate o voi spune așa luați de ce este de ce fiecare limbă co np este și în spațiul pd. Luați bine complementul limbajului dvs. co-mp, care este o limbă np, un limbaj np este în spațiul p, pentru că am demonstrat că asta am dovedit, uh, dar dacă o limbă este în spațiul p complementul său este, de asemenea, în spațiul p, deoarece pentru o procedură deterministă puteți doar răsturna răspunsul mașinii um, așa că acum veți afla dacă da dacă limbajul b b este în cohen p complementul său b complementul este un np care este în spațiul p, dar acum deci complementul b este în spațiul p, așa că acum spațiul p poți inversa răspunsul și acum b este și în spațiul p. Sper că asta ajută, cineva îmi dă răspunsul pentru a obține de la uh, trebuie să votez, dar știi Am văzut un răspuns și știi că există instrumente online care vor răspunde la literele cuvintelor um, așa că trebuie doar să conectezi cele două, știi unde începe și sfârșitul și îți va da scara cuvântului și apoi cea care această persoană care mi-a fost trimisă este cea pe care o primiți de la acel instrument, așa că bănuiesc că nu a găsit-o el însuși. De fapt, uh, înainte de prelegere, am văzut asta pe cont propriu, în afară de cel pe care îl știu pe cel care este instrumentul îți va da astfel încât instrumentul să ofere unul în uh, cred că sunt cinci pași și am găsit unul singur din șase pași, nu este atât de greu, dar da, cel mai mult trebuie să pierzi, Rose a scris și votat, cred că poate sunt șapte pași, oricum vezi că poți rezolvă cuvintele scurte, le poți rezolva, în general, destul de repede pe cont propriu um ce altceva pot face pentru tine um trebuie să ne facem griji să revenim la un cuvânt vizitat anterior cuvânt vizitat în construcția de pe această pagină nu facem nu trebuie să vă faceți griji că vă întoarceți la un cuvânt vizitat anterior, tot ceea ce trebuie să vă faceți este să vă asigurați că ați legat cât timp veți merge și acolo apare problema vizitată anterior, știți dacă um [Muzică ] dacă litera cuvântului pe care ați găsit-o repetă bine un cuvânt, atunci ar fi existat o scară de cuvinte mai scurtă care ar fi funcționat, dar uh, știți, încă arată că este posibil să obțineți de la uh cuvântul de început până la cuvântul de sfârșit. dacă tu dacă ai dacă ai unul repetat între ele, astfel încât să nu conteze, nu trebuie să ne facem griji pentru asta, dacă ai făcut-o, atunci ar fi o problemă, așa că cred că o voi face, sunt patru sau cinci cred Vreau să plec, uh, să ne vedem pe toți și mă voi alătura echipei mele la întâlnire în curând, așa că la revedere, vă mulțumesc că sunteți aici