[SCRÂȘIT] [FOSȘIT] [CLIC] MICHAEL SIPSER: Așa că bine ați venit, tuturor. Bine ai revenit. Să începem cu prelegerea de astăzi. Unde rămăsesem? Marți, am abordat, subiectul principal a fost teorema recursiunii, care permite programelor să se auto-referenți. Și am văzut și câteva aplicații ale acestui lucru. Așa că am dat o nouă dovadă că ATM-ul este indecidibil. Ne-am uitat la acest limbaj al descrierilor minime ale mașinii Turing . Și am avut o scurtă digresiune în logica matematică, în care ne-am uitat la modul în care se arată că există afirmații adevărate, dar nedemonstrabile, în orice sistem formal rezonabil. Așa că astăzi, vom schimba vitezele complet. Și trecem în a doua jumătate a cursului, unde începem un studiu al teoriei complexității computaționale . Și vom spune puțin despre asta în cursul prelegerii, desigur. Dar principalele lucruri pe care le vom acoperi în ceea ce privește conținutul de care veți avea nevoie este definirea claselor de complexitate și a clasei P. Și vom demonstra câteva teoreme pe parcurs. Dar acesta este obiectivul principal al prelegerii de astăzi. Teoria computabilității, care a fost subiectul primei jumătate a cursului și care este ceea ce urmează să acopere examenul intermediar, a fost un subiect care a fost un domeniu activ de studiu matematic în prima parte a secolului al XX-lea. A ajuns cu adevărat... datează cu adevărat de la sfârșitul secolului al XIX-lea, de fapt, când oamenii încercau să-și dea seama cum să oficializeze raționamentul matematic. Dar a început cu adevărat în anii 1930, cu lucrările lui Godel, Church și Turing, care au oficializat pentru prima dată ceea ce înțelegem prin algoritm. Și asta a permis studiul algoritmilor să înceapă cu adevărat. Și a avut impactul său, așa cum am menționat, asupra designului real, construirii și gândirii la computere reale. Întrebarea principală, dacă rezumați într-un fel subiectul la o singură întrebare, este un limbaj determinabil sau nu. În teoria complexității, care a început cam atunci când teoria computabilității s-a încheiat mai mult sau mai puțin ca subiect, în mare parte pentru că au răspuns la multe dintre întrebările pe care ei-- au răspuns aproape la toate întrebările pe care le puneau. Deci, chiar nu au rămas întrebări interesante nerezolvate în acest domeniu. Și chiar ai nevoie de întrebări matematice pentru a menține un subiect în viață, întrebări nerezolvate. Așadar, teoria complexității a început în anii 1960. Și continuă ca un domeniu activ de cercetare până în prezent. Și bănuiesc că dacă ați putea reduce, ar fi un limbaj care poate fi decidat, cu anumite restricții asupra resurselor, cum ar fi cantitatea de timp, sau memorie, sau alte tipuri de resurse pe care le-ați putea oferi, aleatorie și așa mai departe? Toate acestea sunt în domeniul teoriei complexității computaționale . Deci, să începem cu un exemplu. Iată limba la care ne-am uitat în trecut, de la a la k, b la k. Și să ne uităm la asta acum din perspectiva complexității. Toate limbile pe care le vom studia în complexitate vor fi toate limbi determinabile. Deci problema indeciziei în teoria complexității nu este cu adevărat de interes. Toate sunt limbi decidebile, dar întrebarea este cât de decidabile. De ce fel de resurse ai nevoie pentru a lua decizii? Deci, pentru această limbă A, de câți pași sunt necesari? Ei bine, vom petrece puțin timp doar pentru a stabili definițiile subiectului și pentru a le motiva. Deci, pentru această limbă A, când întreb de câți pași sunt necesari, ei bine, va depinde de ce intrare aveți în vedere. Unele intrări ar putea necesita mai mulți pași decât altele. Așadar, modul în care vom stabili subiectul, care este modul standard în care oamenii din acest domeniu îl privesc, și cred că se aplică și pentru multe exemple din afară, este că vom face un fel de grup toate intrările de aceeași lungime împreună. Și uitați-vă la costul maxim, numărul maxim de pași de care aveți nevoie, pentru a rezolva oricare dintre acele intrări de o anumită lungime. Și vom face asta pentru fiecare lungime. Și modul în care îl vom încadra este în termeni de a oferi un maxim, sau ceea ce se numește o limită superioară, pentru cantitatea de timp de care aveți nevoie pentru a rezolva toate acele intrări de lungime n. Aceasta este ceea ce uneori se numește complexitate în cel mai rău caz. Sunt sigur că mulți dintre voi ați văzut deja asta. Dar doar pentru a vă asigura că suntem cu toții împreună în această privință, ați putea contrasta asta, de exemplu, cu ceea ce se numește complexitate medie a cazului. Unde, în loc să priviți cel mai dificil caz dintre toate intrările de lungime n, luați media tuturor intrărilor de lungime n. Și atunci trebuie să-- atunci este puțin mai complicat, pentru că atunci trebuie să aveți o distribuție a probabilității pe acele intrări și așa mai departe. Nu o vom privi , în acest curs, din această perspectivă. Ne vom uita doar la ceea ce se numește cel mai rău caz de complexitate. Deci, să începem, atunci, analizând acest lucru mai detaliat și luând ca punct de plecare teorema care spune că pe o mașină Turing cu o bandă, care decide acest limbaj A, a la k, b la k, puteți fă asta pe o mașină Turing cu o bandă, M, o numim. În cel mult unii timpi constanți n pași pătrați, pentru orice intrare de lungime n, unde constanta va fi fixată independent de ea. Deci, acesta va fi... a avea un factor constant în... complexitate va apărea des. Și așadar, în loc să spunem asta iar și iar, vom folosi o notație care m folosește ordinea n pași pătrați. Sunt sigur că mulți dintre voi ați văzut și această terminologie. Dar doar pentru a ne asigura că suntem cu toții împreună, există această notație mare O și o mică. Mă aștept să fii familiarizat cu asta. Big O este atunci când aplicați la funcții, așa cum este gata. Spuneți că f este O mare pentru g, ca și pentru două funcții f și g. Practic, este dacă f este mai mic sau egal cu g, dacă ignorați factorii constanți. Și spui f este mic o din g dacă f este strict mai mic decât g dacă ignori factorii constanți. Acesta este un fel de mod informal de a privi lucrurile. Definiția precisă este dată acolo pe diapozitiv. Și dacă nu l-ați văzut până acum, asigurați-vă că îl priviți în carte, unde totul este descris și definit cu atenție. Pentru a fi confortabil cu aceste noțiuni. Pentru că este într- adevăr... vom folosi asta fără alte discuții de aici încolo. Deci, să ajungem la demonstrația acestei teoreme că poți face limbajul A în ordinea n pași pătrați. Nu foarte greu. Cred că dacă ți-aș cere să vii cu un algoritm pentru a rezolva A, acesta ar fi algoritmul pe care l-ai găsi practic. În primul rând, veți începe prin a scana intrarea w pentru a vă asigura că are forma corectă. Deci o serie de a urmată de o serie de b de anumite lungimi. Și dacă nu este de această formă, atunci vei respinge imediat. Următorul lucru pe care îl veți face este apoi să mergeți la o buclă repetată în mașina Turing. Și dacă vă imaginați, aici este mașina dvs., aici este intrarea w, veți trece prin repetarea acesteia în mod repetat. Desigur, puteți face acest lucru în mai multe moduri diferite. Dar iată modul pe care îl am în minte pentru tine, pe acest slide, oricum. Vom scana întreaga bandă, tăind un singur a și un singur b la o scanare. Și apoi vei continua să faci asta până când vei șterge totul. Dacă nu rămâi fără a sau rămâi fără b. În acest caz, vei respinge. Dacă rămâneți fără a sau b înainte de a rămâne fără celălalt tip, atunci știți că ați început cu un număr inegal. Și astfel mașina va respinge. Dacă ai reușit să le tai pe toate fără a rămâne fără una înainte de alta, atunci vei accepta. Știu că acest lucru este cam evident. Dar cred că este important să ne unim pe toți la început. Deci, iată o mică animație a mașinii Turing care face asta. Nu arăt mișcarea capului. Dar îți imaginezi capul scanând înainte și înapoi, tăind aceste a și b, câte un a și un b la fiecare trecere, până când sunt tăiate toate. Și apoi acceptă. Cu excepția cazului în care, desigur, rămâne fără a sau b înainte de celălalt tip, apoi respinge. OK, acum haideți să facem o analiză foarte rapidă și informală a cât timp a durat. Deci, chiar prima etapă, numesc fiecare dintre aceste lucruri stadii ale mașinii Turing pentru a le distinge de pașii mașinii Turing, care sunt mișcările individuale ale funcției de tranziție. Deci aceasta este întreaga etapă a mașinii. Prima etapă are ordine în n pași, deoarece trebuie să faceți o scanare peste intrare. Și atunci nu dau toate detaliile. Desigur, veți scana și apoi veți readuce capul înapoi în poziția inițială. Nu sunt... acesta va fi doar un factor suplimentar de n, un n suplimentar. Și de aici vorbim despre ordinea n pași pentru prima etapă. Și apoi, pe măsură ce treceți prin bucla de repetare, de fiecare dată când treceți prin bucla de repetare, veți tăia unul a și unul b. Deci asta va însemna că va trebui să faceți această ordine aproximativă - va trebui să faceți această ordine de n ori pentru a tăia toate a și b. Deci, vor exista ordine n iterații ale acestei bucle repetate. Fiecare dintre ele va necesita, din nou, o scanare. Deci, aceasta este ordinea n pași pentru fiecare dintre iterații. Deci, adăugând toate acestea, rândul de sus ne dă ordinea n și apoi avem ordinea n iterații ori ordinea n pași este ordinea n pași pătrat. Și astfel suma acestor două este de ordinul n pași pătrați datorită naturii aritmeticii atunci când aveți notația mare O. Termenul dominant îi depășește pe toți ceilalți. Așadar, pe scurt, noi... ei bine, acesta este primul nostru exemplu de analiză a algoritmului mașinii Turing pentru o limbă. Așa că permiteți-mi să vă întreb acum dacă există o altă mașină Turing, o altă mașină Turing cu bandă care poate face mai bine decât această mașină Turing în ceea ce privește timpul necesar. Deci o idee pe care ați putea-o avea, în loc să tăiați un singur a sau un singur b, poate că puteți tăia două a și două b, sau 10 a și 10 b. Ei bine, asta va reduce timpul de rulare cu un factor de 10. Dar din punctul de vedere al acestei teoreme, va fi încă un algoritm de ordin n pătrat. Și astfel încât asta cu adevărat nu schimbă cantitatea de timp folosită din perspectiva... din perspectiva noastră, unde vom ignora factorii constanti ai timpului de rulare. Așa că vă întreb aici, puteți face mai bine decât să îmbunătățiți lucrurile printr-un factor constant? Iată-ne. OK, deci iată o verificare a acestei probleme, a problemei A, hotărârea A pe o mașină Turing cu o bandă. Putem face mai bine decât ordinea n pătrat, așa cum tocmai am descris în acea teoremă în acel algoritm pentru acea teoremă? Sau îl poți reduce la n log n? Sau poate îl puteți obține la comanda n? Ce crezi? Evident, abia am început. Dar doar fă-ți cea mai bună presupunere. Și lasă-mă să postez asta pentru tine ca sondaj. Ceea ce este cel mai important pentru mine este că înțelegeți terminologia pe care o folosim și modul în care discutăm -- felul în care vorbim despre asta. Pentru că asta ne va pregăti pentru definițiile pe care le vom veni puțin mai târziu în prelegere. Așa că o să închid sondajul. Suntem cam peste tot pe el. Dar asta e bine. Deoarece încă nu am acoperit acest material cu adevărat. De fapt, B este răspunsul corect. Putem îmbunătăți acest algoritm până la ordinea n log n, dar nu până la ordinea n. Așa că, permiteți-mi să vă arăt cum o faceți în ordinea n log n în următorul diapozitiv. Și deci iată o mașină Turing cu o bandă care poate decide A utilizând numai ordinea n log n pași în loc de ordinea n pași pătrați. Deci aceasta este o îmbunătățire semnificativă. Așa că voi descrie mașina Turing. Iată, din nou, imaginea mașinii pe o intrare. Și primul lucru pe care trebuie să-l spun este că vom scana pentru a ne asigura că intrarea are forma corectă. Și acum, vom-- din nou, va fi să facem treceri repetate peste intrare. Dar acum o vom face puțin diferit. În loc să tăiem un singur a și un singur b, sau un număr fix de a și un număr fix de b, vom tăia toate celelalte a și toate celelalte b. Și astfel, în esență, vom reduce numărul de a și b la jumătate. Și de aceea numărul de iterații va fi doar un log, în loc de liniar. Așa că vom tăia toate celelalte a și toate celelalte b. Și, în același timp, vom urmări paritatea, paritatea pară/impară a numărului de a pe care le-am văzut și paritatea numărului de b pe care le-am văzut care nu au fost încă tăiat. Și vom compara acele parități pentru a ne asigura că sunt de acord. Dacă vreodată nu sunt de acord, știm că am început cu numere diferite de a și b. Și voi ilustra acest lucru într-o secundă, doar pentru a ne asigura că înțelegem acest algoritm. Așa că am de gând să notez ca un mic tabel al parităților pe care le-am văzut. Și o să ilustrez algoritmul cu puțină animație. Deci, din nou, acum vom scana, tăind fiecare a, și apoi fiecare b. Dar înainte de a ajunge la B, observăm, în timp ce le-am tăiat, că aveam șase a. Acum, nu spun că le numărăm. Ținem doar evidența parității par/impar. Acest lucru se poate face în controlul finit al mașinii. Numărarea lor ar fi mai complicată. Dar doar urmărirea parității este ceva ce ar putea face automatul finit. Deci, paritatea în acest caz, pentru că au fost șase, va fi egală. Acum, tăiem b-urile. La fel, chiar și paritate, acum vom întoarce capul înapoi la început, evident că nu arăt capul care se mișcă aici. Revenim capul înapoi la început. Și acum, scanăm din nou, tăind toate celelalte a rămase și numărând paritățile a rămase. Așa că aici, acum, va fi acesta și acesta va fi eliminat. Și au fost trei a, deci era o paritate ciudată. Și același lucru pentru b, trei b, paritate impară. Și acum ne întoarcem capul înapoi la început, încrucișăm din nou, de pe fiecare a și pe fiecare b. Deci a fost o paritate ciudată, a fost doar una. Trimiterea b, paritate impară pentru că doar unul. Toți sunt de acord. Deci mașina va accepta. Pentru că totul este acum tăiat. Și parțile au convenit pe parcurs. Permiteți-mi să spun doar pentru o secundă, evident, dacă veți avea vreodată dezacord cu privire la parități, atunci numărul de a și numărul de b trebuie să fie în dezacord. Dar de unde știm că dacă paritățile sunt întotdeauna de acord că am început de fapt cu același număr de a ca și b? Și asta, ai putea vedea asta în mai multe moduri diferite, dar poate un mod drăguț de a-l vedea este de fapt, dacă te uiți la aceste parități, iată secvența de parități, de fapt invers. Deci, dacă spui impar, impar, par și te uiți la reprezentarea binară a numărului lui a , care este șase, deci reprezentarea binară ar fi 110. Faptul că obții impar, impar, par și 110 nu este un coincidență. De fapt, succesiunea de parități inversă pe care o obțineți este exact aceeași cu reprezentarea binară. Ar trebui să confirmi asta cu o mică dovadă. Nu este greu. Dar că, odată ce ați confirmat acest lucru, puteți vedea că dacă succesiunea parităților este de acord, atunci numerele trebuie să fie aceleași, pentru că reprezentările binare au fost de acord. OK, deci acum ajungând la analiză aici, din nou, comandați n pași pentru a face verificarea. Log n iterații. Fiecare scanare ia ordine n pași. Deci, timpul total de rulare aici va fi ordinul n log n. Va fi jurnalul de n ori n. De aici provine n log n. Acum, întrebarea pe care ați putea-o pune, aș putea să fac și mai bine decât atât? Pot învinge n log n cu mai mult decât orice factor constant? Deci pot face puțin o din n log n? Și răspunsul este nu. Aceasta este cea mai bună mașină Turing cu bandă posibilă pentru această limbă. Deci, o mașină Turing cu o bandă nu poate decide A folosind o mică parte din n log n pași. Nu vom demonstra asta. Nu o să-ți cer să fii responsabil pentru dovezi. Dar, de fapt, ceea ce puteți arăta este că orice limbă pe care o puteți face pe o mașină Turing cu o bandă în cei mici o din n log n pași se dovedește a fi obișnuită. Deci, puteți dovedi o temă destul de puternică aici. Nu foarte greu de dovedit. Dar nu vreau să petrec mult timp pe terenuri de probă pentru mașinile Turing. Deoarece, într-adevăr, întregul scop al instalării acestui lucru folosind mașinile Turing este de a vorbi despre algoritmi în general, despre algoritmi în general, nu mă voi concentra pe esențialul mașinilor Turing. OK, deci care este... da, așa că am vrut să mă opresc și să mă asigur că suntem împreună aici. Deci o scurtă pauză. Și nu ezitați să- mi trimiteți orice întrebări. OK, aceasta este o întrebare bună. Dacă putem ține evidența parităților, de ce nu putem urmări doar numărul de a sau b? Ei bine, ai putea ține evidența parității în memoria finită. Și astfel poți face asta fără nicio muncă. Dar memoria finită nu este suficientă pentru a face o numărare până la un număr arbitrar de mare. Acum, puteți stoca numărătoarea pe bandă. Dar asta te va costa timp pentru a menține acel contor. Și așa că nu va fi atât de simplu ca să ținem evidența parității în memoria finită. Cineva întreabă dacă o stea b este obișnuită. Da, o stea b este obișnuită. Şi ce dacă? Dar a la k, b la k, care este limba noastră, nu este regulat. Aceasta este limba la care ne uităm. Așa că primim întrebări despre ce se întâmplă cu mai multe benzi. Vom vorbi despre asta într-o secundă. Da, am putea face o comandă n pași pe un computer obișnuit, sigur. Dar pentru acest slide, oricum, ne uităm la mașinile Turing cu o bandă. Primesc întrebări despre O mare și o mică. Pentru ca ceva să fie mic o înseamnă că este mai mic decât orice factor constant înmulțit cu funcția. Așa că trebuie să te uiți la definiția din carte. Cred că destui oameni din clasă probabil știu asta și au văzut asta deja, nu vreau să petrec timpul tuturor cu asta. Dar vă rugăm să o revizuiți în carte. Cineva vă întreabă dacă trebuie să stocați paritatea pe bandă. Nu, îl poți stoca doar în memoria finită. Adică, stocarea în memoria finită mi se pare cel mai simplu lucru. De ce nu mergem mai departe? Vă rugăm să nu ezitați să adresați întrebări și AT-urilor. Avem cel puțin doi AT care participă cu mine. Atât de bine, bine, bine, așa că nu putem face mai bine decât o mașină Turing cu o bandă... pe o mașină Turing cu o bandă decât comanda n log n. Și asta e ceva ce putem dovedi, deși nu o vom face aici. Cu toate acestea, dacă schimbați modelul, de exemplu, utilizați o mașină Turing cu două benzi, atunci da, așa cum sugerați mulți dintre voi în chat, puteți face mai bine decât atât. Deci, dacă acum avem o mașină Turing cu două benzi sau o mașină Turing cu mai multe benzi , o puteți face în ordinea n pași. Și acesta este de fapt punctul pe care chiar încerc să-l subliniez aici. Deci, dacă aveți aici mașina dvs. de Turing cu două casete, atunci două casete, aceeași limbă. Acum, ceea ce vom face este să copiem a- urile pe a doua bandă. Asta putem face cu o singură trecere. Și apoi, odată ce a-urile au fost copiate pe a doua bandă, putem continua să citim b-urile și să le potrivim cu a-urile care apar pe a doua bandă. Deci, în ordinea n pași, puteți face comparația, în loc de ordinea n log n pași. Și bineînțeles, dacă se potrivesc, vei accepta, în caz contrar, vei respinge. Deci, să vedem, iată o mică animație care demonstrează asta. Desigur, este foarte simplu. Așa că iată-- iată-- dacă ai putea vedea asta, poate a venit puțin prea repede. Iată, hai să o arătăm din nou. Iată capete care se mișcă peste și a coboară în jos. Și acum, capul, capul de sus va continua să citească b-urile. Capul inferior se va întoarce la început pe a și se va potrivi între b cu a. Și așa putem verifica sau verifica dacă sunt același număr. Deci acum, în acest caz, au fost același număr. Deci mașina ar accepta. Dacă ar fi un număr diferit, aparatul nu ar accepta. Și analiza este foarte simplă. Fiecare etapă de aici va lua un număr liniar de pași, ordinea n pași, deoarece constă doar dintr-o singură scanare. Nu există... nu există bucle în această mașină, nici bucle repetate. Deci întrebare despre asta? Bine, atunci de ce nu mergem mai departe? Acum, observă... și ideea pe care încerc cu adevărat să-l subliniez este că pe o mașină Turing cu o bandă, poți face asta în n log n, dar nu mai bine. Dar pe o mașină Turing cu două benzi, o poți face în ordinea n. Deci, există o diferență în ceea ce privește cât timp trebuie să petreceți, câți pași trebuie să petreceți, în funcție de model. Și asta este semnificativ pentru noi. Deci numărul de pași depinde de model. O mașină Turing cu bandă a fost comanda n log n, multi-bandă a fost comanda n. Numim asta dependență de model. Dacă comparați asta cu situația din complexitate, în secțiunea de calculabilitate a cursului, am avut independență de model. Alegerea modelului nu a contat. Și asta a fost frumos pentru noi. Deoarece teoria decidebilității nu depindea dacă ai o mașină Turing cu o bandă sau o mașină Turing cu mai multe benzi , totul era același set de limbi decidabile și recunoscute . Deci nu a trebuit să ne îngrijorăm cu ce model vom lucra de fapt . Am putea lucra cu orice model, chiar și doar un model informal de algoritm ar fi suficient de bun. Pentru că vom ajunge cu aceeași noțiune până la urmă. Acum asta dispare în teoria complexității. Acum, avem o diferență, în funcție de model. Și din punct de vedere matematic, asta e puțin mai puțin frumos. Pentru că cu ce model lucrezi? Dacă vrei să înțelegi complexitatea unei probleme pe care o ai la îndemână, acum trebuie să faci o alegere. Vei lucra cu o mașină Turing, sau cu câte benzi, sau te vei uita la alt model și vei obține rezultate diferite. Deci, este ceva mai puțin firesc din punct de vedere matematic doar să vorbim despre complexitatea unei probleme. Dar vom readuce ceva destul de aproape de independența modelului observând că, deși nu avem independență de model, așa cum am făcut-o în teoria computabilității, putem limita cât de multă dependență există. Deci, gradul de dependență va fi scăzut, așa cum vom vedea, cu condiția să rămâneți cu o clasă rezonabilă de modele deterministe. Deci dependența, deși există, nu va fi atât de mare. Va fi dependență polinomială. Și vom spune exact ce înseamnă asta într-o secundă. Și din punctul nostru de vedere, aceasta va fi o mică diferență, o diferență neglijabilă pe care o vom ignora. Deci ne vom concentra pe întrebări care nu depind de alegerea modelului dintre aceste modele deterministe rezonabile . Acum, puteți spune, ei bine, asta nu este interesant din punct de vedere practic, pentru că diferențele polinomiale, să spunem că diferența dintre n pătrat și n cub face cu siguranță o diferență în practică. Dar depinde cu adevărat de ce fel de întrebări te concentrezi. Deci, dacă doriți să priviți ceva care este o distincție foarte precisă, să zicem între n pătrat și n cub, atunci s-ar putea să doriți să vă concentrați asupra modelului cu care doriți să lucrați. Și acesta va fi mai mult domeniul unei clase de algoritmi. Dar din punctul nostru de vedere, ne vom uita la alte întrebări, încă importante. Dar sunt întrebări care nu depind de exact ce polinom vei avea. Ne vom uita mai mult la distincțiile dintre polinom și exponențial. Și totuși, există întrebări practice importante care apar în acel cadru oarecum diferit. Deci, având în vedere asta, vom continua să folosim mașina Turing cu o bandă ca model de bază al complexității. Întrucât modelul dintre modelele deterministe rezonabile în cele din urmă nu va conta din perspectiva tipului de întrebări pe care le vom pune. Deci, cu asta, așa că vom continua, atunci, este important să ne amintim că de la viitor, vom rămâne cu modelul de mașină Turing cu o bandă. Poate că asta e ceva la care te-ai fi așteptat să facem oricum. Dar încerc să justific asta prin această mică discuție pe care am avut-o până acum, până acum. Așa că acum, vom începe să definim lucrurile cu un model de bandă în minte. Deci, în primul rând, dacă aveți o mașină Turing, vom spune că funcționează într-o anumită perioadă de timp. Deci, dacă t este un fel de funcție legată de timp, cum ar fi n pătrat sau n log n, vom spune că mașina rulează în acea perioadă de timp, cum ar fi n pătrat sau n log n. dacă acea mașină M se oprește întotdeauna în acel număr de pași pe toate intrările de lungime n. Deci se oprește întotdeauna în t din n pași pe intrările de lungime n. Apoi vom spune că mașina rulează în t din n timp. Deci, cu alte cuvinte, dacă mașina rulează în timp n pătrat, atunci mașina, atunci când îi dați o intrare de lungime 10, trebuie să fie garantat să se oprească în 100 de pași, 10 pătrați, 100 de pași, pentru fiecare intrare de lungime. 10. Asta înseamnă ca mașina să funcționeze în atât de mult timp. Și trebuie să facă asta pentru fiecare n, pentru fiecare lungime de intrare. Și la lățime, vom ajunge la următoarea definiție, care este evidențiată în culoare, pentru că va fi-- vom folosi această definiție pe tot parcursul semestrului. Deci este important să înțelegeți. Aceasta este definiția a ceea ce se numește clase de complexitate temporală . Și ceea ce voi face este să iau o limită, t din n, și din nou, să mă gândesc la t din n ca o limită ca n pătrat. Deci, dacă aveți timpul t de n sau ca timpul n pătrat, aceasta va fi colecția tuturor limbilor pe care le puteți decide în timpul n pătrat sau în timpul t din n. Deci, cu alte cuvinte, este o colecție de toate limbile B, astfel încât există o mașină Turing cu bandă, aici ne concentrăm din nou pe mașina Turing cu o bandă, există o mașină Turing cu bandă deterministă care decide B. Și acea mașină rulează în acea perioadă de timp. Deci aceasta este o colecție de limbi. Clasa de complexitate a timpului este un set de limbaje. O să-l desenez acum sub formă de diagramă. Deci, dacă luați din nou limbajul pe care l-am folosit ca exemplu standard, a la k, b la k, acesta este n timp n log n, așa cum am observat două diapozitive la diapozitive înapoi sau trei diapozitive înapoi . Deci, pe o mașină Turing cu o bandă, puteți face acest limbaj A în timp n log n. Deci este în clasa de complexitate a timpului n log n. Această regiune surprinde aici toate limbile pe care le puteți face în ordinea n log n timp. De exemplu, aceasta include și toate limbile obișnuite. De ce este asta? Ei bine, orice limbaj obișnuit poate fi făcut pe o mașină Turing cu o bandă în ordinea de timp n, deoarece mașina Turing trebuie doar să scaneze. Nici măcar nu trebuie să scrie, trebuie doar să scanezi de la stânga la dreapta pe bandă. Și în n pași, are răspunsul. Deci, toate limbajele obișnuite sunt de fapt în timpul n, cu siguranță un subset de timp n log n. Și toate acestea formează un fel de ierarhie. Deci, dacă creșteți limita, vă puteți imagina că clasa de limbi crește pe măsură ce permiteți mașinii să aibă din ce în ce mai mulți pași pentru a-și face calculul. Deci, acestea sunt toate limbajele pe care le puteți face în n pătrat, comanda n pătrat timp pe o mașină Turing cu o bandă, n timp cub pe o mașină Turing cu o bandă și așa mai departe, 2 timp exponențial, 2 până la n timp pe un o mașină Turing cu bandă. Acestea sunt toate colecțiile de limbi care devin din ce în ce mai mari pe măsură ce creștem limita. Așa că cineva întreabă cam... să vedem, lasă-mă să ajung la câteva dintre aceste întrebări aici. Voi încerca să ajung la ei în ordine. Deci cineva spune că dacă ai... o întrebare bună, dacă ai un computer obișnuit, deci un fel obișnuit de computer cu acces aleatoriu, despre care vom vorbi despre asta într- o secundă, o poate face în ordinea n, poți să o faci pe o mașină Turing cu mai multe benzi, de asemenea, în ordinea n timp? De fapt, nu știu răspunsul la asta. Bănuiesc că răspunsul este nu. Că computerele obișnuite au o capacitate de acces aleatoriu pe care mașinile Turing nu o au. Și astfel încât vor exista câteva exemple de probleme pe care le puteți face cu un computer obișnuit, pe care nu le puteți face cu mașina Turing cu mai multe benzi în ordine de timp. Ar trebui să verific asta, totuși, ca să putem... este, de asemenea, o întrebare despre ce credem că este adevărat și ce putem dovedi că este adevărat. După cum vom vedea, există o mulțime de lucruri despre care credem că sunt adevărate în acest subiect și pe care nu știm cum să le dovedim. Cineva pune un fel de întrebare interesantă mai avansată. Există vreo funcție f, vreo funcție t unde este atât de mare încât timpul t din n vă oferă toate problemele decidabile? Ar fi un t foarte mare. Dar, de fapt, răspunsul la această întrebare este da. Dar asta e puțin exotic. Deci, să nu petrecem mult timp aici. Dar bucuros să vorbesc despre asta offline. Este o întrebare bună aici. Cineva mă întreabă dacă înseamnă că nu există limbi între ordinul n și ordinea n log n, pentru că am subliniat că orice sub n log n va fi obișnuit. Și așa, de îndată ce ajungi sub n log n, o poți face în ordinea n. Și da, există ceea ce se numește un decalaj între ordinea n și ordinea n log n pe o mașină Turing cu o bandă. Nu primești nimic nou de la comanda n până când sari în sus. Deci, de la ordinea n la ordinea n log log n, nu apare nimic nou. Așa că vom vorbi despre astfel de lucruri puțin mai departe , când ne uităm la relația dintre aceste diferite clase și la ceea ce numim o teoremă a ierarhiei, care arată-- cât de mare trebuie să faceți legat pentru a fi sigur că vei primi ceva nou? În regulă, cineva întreabă dacă există un model care are aceeași complexitate temporală ca un computer normal? Ei bine, vreau să spun, există modelul de acces aleatoriu, care ar trebui să captureze un computer normal. Așa că permiteți-mi... toate acestea sunt întrebări grozave, mai mult dezbinate de asta în direcții mai avansate. Sa trecem peste. Iată un alt check-in. Să presupunem că luăm -- aceasta este o mică verificare pentru a vedea cât de bine -- cât de bine vă simțiți cu noțiunile pe care tocmai le-am prezentat și dacă vă puteți gândi la unele dintre argumentele pe care le-am formulat și le puteți aplica. un nou limbaj. Deci, luați limbajul ww invers, șirurile urmate de lor-- urmate de ei înșiși înapoi. Acest limbaj B sunt palindromurile de lungime egală, dacă vreți. Care este cea mai mică limită de care aveți nevoie pentru a putea rezolva limbajul B? Și o voi pune ca o... pune asta ca o întrebare pentru tine. Deci, în ce clasă de complexitate oră se află limba B? Este ordinul de timp n, ordinea n log n, n pătrat și așa mai departe? Ce crezi? Așa că suntem pe cale să venim la pauza de cafea. Deci de ce nu... Voi răspunde la orice întrebări care apar. Cred că avem un răspuns tuturor. Așa că o să închei sondajul. OK, asigurați-vă că sunteți acolo dacă doriți să intrați. Deci răspunsul corect este, de fapt, ordinea n pătrat. Ar fi greu-- o presupunere rezonabilă aici ar fi ordinea n log n. Adică, puteți veni cu aceeași procedură ca cea pe care am arătat-o la început, procedura de ordine n pătrat pentru a la k, b la k funcționează și pentru ww inversă. Puteți doar să tăiați, să treceți înainte și înapoi, tăind un simbol din w și mergând pe partea cealaltă, tăind un simbol din w invers. Și această procedură vă va oferi un algoritm n pătrat și ordine n pătrat. Vă puteți imagina că îl puteți îmbunătăți pentru a comanda n log n. Dar nu poți. Puteți demonstra că ordinea n pătrat este cea mai bună posibilă. Sunt puțin nemulțumit că mulți dintre voi au venit cu comanda n, sincer. Pentru că ți-am spus deja că ordinea n este... acestea sunt doar limbi obișnuite. Orice puteți face în mai puțin de-- un pic de n log n va fi obișnuit. Și știm că acest limbaj nu este obișnuit. Deci acesta nu a fost un răspuns bun. Așa că vă rog să fiți atenți. Și OK, așa că haideți să nu mai împărtășim. Mă voi întoarce acum la pauză de cinci minute. Și mă bucur să încerc să răspund întrebărilor pe parcurs, în timp ce așteptăm să se încheie timpul. Deci, să vedem, lasă- mă să pun asta aici. Lasă-mă să încerc să răspund la câteva dintre întrebările tale. Așa că cineva mă întreabă despre computerele cuantice ca modele rezonabile de... ați putea spune că un computer cuantic este un model rezonabil de calcul. Și asta e bine. Nu aș spune că este un model rezonabil de calcul determinist, cel puțin din punctul nostru de vedere. Să nu ne disputăm cu cuvintele. Nu includ calculatoarele cuantice în colecția de mașini pe care o am în minte acum când vorbesc despre modelele rezonabile de calcul determinist pe care le vom discuta. Să vedem. Oh, pentru că se pare că o grămadă de oameni întreabă AT de ce toate limbile obișnuite pot fi făcute în ordinea n. Deci, dacă vă gândiți la un DFA, care procesează o intrare de lungime n cu n pași, și un DFA este, voi fi un tip de mașină Turing care nu scrie niciodată pe bandă, așa că dacă un DFA o poate face în n pași, mașina Turing o poate face în n pași. Prin urmare, fiecare limbaj obișnuit poate fi făcut în ordinea n pași pe o mașină Turing. Nu sunt sigur unde este confuzia. Așa că vă rog să-mi trimiteți un mesaj dacă tot nu îl primiți. OK, cineva spune de ce folosim mașini Turing cu o bandă în loc de acces aleatoriu? Nu ar fi mai bine să folosiți mașinile cu acces aleatoriu? Dacă foloseai... dacă încerci să faci algoritmi, da. Acesta este un model mai rezonabil. Încercăm să dovedim lucruri despre calcul. Și din acest punct de vedere, dorim să folosim un model cât mai simplu posibil. Este posibil să încerci să dovedești lucruri folosind computere cu acces aleatoriu . Ar fi foarte dezordonat. Deci, de aceea, nu folosim mașini cu acces aleatoriu pentru a demonstra tipurile de lucruri pe care le vom demonstra despre calcul și care sunt cu adevărat carnea și cartofii acestui curs. Deci, vreau să spun, există motive convingătoare pentru care ai dori să folosești un model simplu precum o mașină Turing, dar nu un model puternic precum un computer cu acces aleatoriu . Deci cineva mă întreabă, ordinul orar al clasei n log log n are elemente? Da, are toate limbile obișnuite, dar nimic altceva. Jurnalul de ordine și jurnal este că sunt doar limbile obișnuite. Trebuie să mergi până la n log n înainte de a obține ceva neobișnuit. Cineva mă întreabă dacă vom vorbi despre cum funcționează modelul de acces aleatoriu? Nu. Asta depășește scopul acestui curs, în afara a ceea ce vom face. Vom vorbi despre mașinile Turing. Nu pentru că ne pasă atât de mult de mașinile Turing. Dar încerc să demonstrez lucruri despre calcul. Iar mașinile Turing sunt un vehicul convenabil pentru a face asta. Lumânarea noastră s-a ars. De ce nu ne întoarcem, atunci, la următorul slide. Deci toată lumea se întoarce. Deci asta răspunde la una dintre întrebările pe care le-am primit pe chat. Care este de fapt dependența dintre mașinile Turing cu mai multe benzi și mașinile Turing cu o bandă? Putem lega asta în general? Da putem. Vom arăta că transformarea unei mașini Turing cu mai multe benzi într- o mașină Turing cu o bandă poate, cel mult, să arunce în aer timpul necesar prin pătrat. Nu, recunosc că sunt multe. Dar încă îți permite... dar este încă mic în comparație cu o creștere exponențială. Și ne vom concentra, în acest curs, pe lucruri precum diferența dintre polinom și exponențial, nu între diferit-- nu între diferența de-- nu diferența dintre n pătrat și n cub. Acesta va fi mai puțin un factor, mai puțin o problemă pentru noi. Deci, modul în care arăt această teoremă este că, dacă aveți o mașină Turing cu mai multe benzi care poate face un limbaj într-o anumită perioadă de timp, atunci este în clasa de complexitate a timpului acelui timp legat la pătrat. Și felul în care spun asta este pentru că aceasta este limita care utilizează modelul cu o bandă. Deci, un alt mod de a spune că este conversia mai multor benzi într-o bandă pătrată cât de mult timp aveți nevoie. Deci, modul în care vom demonstra acest lucru este pur și simplu să ne întoarcem și să ne amintim de conversia pe care am prezentat-o ​​deja de la casetă multiplă la o singură bandă. Și observați că, dacă analizăm acea conversie, ajunge doar la pătrarea timpului pe care a folosit banda multiplă. Deci de ce este asta? Deci, dacă vă amintiți, să ne asigurăm că suntem cu toții împreună în acest sens, felul în care aparatul cu bandă unică S simulează mașina Turing cu mai multe benzi M este că duce conținutul fiecărei benzi ale lui M, până la locul în care există infinit. multe spatii libere. Evident că nu stocați partea infinită. Dar porțiunea activă a fiecăreia dintre benzile lui M, le vei stoca consecutiv în blocuri separate pe banda lui S, pe singura bandă a lui S. Și acum, de fiecare dată când M face o mișcare, S trebuie să-și scaneze întreaga bandă pentru a vedea ce se află sub fiecare dintre capete și pentru a face toate actualizările. Deci, pentru a simula un pas al calculului lui M, S va folosi ordinea t din n pași, unde t din n este timpul total de rulare pe care M îl va folosi. Deci de ce urcă t din m trepte aici? Ei bine, asta pentru că trebuie să măsori cum... S va face o scanare pe bandă. Cât de mare poate fi banda lui? Ei bine, M, dacă încearcă să folosească cât mai multă bandă posibil, poate folosi, cel mult, t din n bandă pe fiecare din-- t din n celule pe fiecare dintre benzile sale. Deci, în total, vor fi doar un număr constant de ori t de n celule pe banda lui S. Vezi asta? Deci fiecare dintre acestea va fi, cel mult, t de n lungime. Deci toate acestea împreună vor fi de ordinul t de n lung. Pentru că ce poate face M? Ar putea să-și trimită capul afară, spune capul de pe această bandă aici, mișcându-se cât mai repede posibil spre dreapta, folosind cât mai multă bandă. Dar puteți utiliza numai t din n celule în t din n timp. Deci acesta va fi ordinul t din n. Deci un pas de calcul va fi t din n pași pe calculul lui S. Dar M însuși are t din n trepte. Deci, va fi t de n ori t de n pentru numărul total de pași pe care S îl va folosi. Și de aici vine pătratul. Rezultate similare, nu voi face multe simulări ale unui model cu altul. Cred că vei înțelege ideea. Și poți, dacă ești interesat, le poți studia pe cont propriu. Dar puteți converti mașini Turing multidimensionale în mașini Turing cu o bandă, o bandă liniară obișnuită - o bandă, mașini unidimensionale. Și concluzia este că, printre toate modelele rezonabile, toate sunt ceea ce se numesc legate polinomial, dacă fiecare îl poate simula pe celălalt cu, cel mult, un polinom. Deci, dacă una dintre mașini poate folosi acest t de n timp, cealaltă mașină care o simulează ar folosi t la k de n timp pentru unele k. Asta înseamnă ca cele două mașini să fie legate polinomial. Și toate modelele deterministe rezonabile sunt legate polinomial. Așadar, așa cum am văzut deja, mașinile Turing cu o bandă și cu mai multe benzi sunt legate polinomial, deoarece conversia benzilor multiple într- o singură bandă te aruncă în aer prin, cel mult, pătrat. Deci k este egal cu 2 în acest caz. Mașini Turing multidimensionale, din nou, legate polinomial, mașina cu acces aleatoriu, pe care nu o voi defini, dar este mașina pe care v-ați putea imagina - ați face, sunt sigur că trebuie să o definească într-o anumită formă în clasele de algoritmi , înrudit polinomial. Automate celulare, care sunt doar rețele de automate finite care pot comunica între ele, în mod similar. Toate modelele deterministe rezonabile, din nou, modelele clasice, nu vorbesc despre calculul cuantic, sunt legate polinomial. Deci suntem... asta justifică alegerea noastră de a alege unul dintre ele, atâta timp cât vom pune întrebări care nu depind de polinom. Să vorbim atunci despre clasa P. Deci clasa P, aceasta este o definiție importantă pentru noi. Aceasta este colecția tuturor limbilor pe care le puteți face în timp n la k pentru niște k pe o mașină Turing cu o bandă. Sau, așa cum am scris-o aici, nu știu dacă această notație vă este necunoscută, dar aceasta este ca doar o sumă mare. Dar aici, este un mare simbol sindical. Este unirea tuturor valorilor lui k din clasa de timp n cu k. Deci acesta este timpul n, timpul de unire n pătrat, timpul de unire n cub, timpul de unire n până la a 4-a și așa mai departe. Acestea le numim limbaje determinabile în timp polinomial. Deci vom depune un anumit efort pentru a explora această clasă P și alte clase similare. Cineva mă întreabă de ce este un sindicat. Nu sunt sigur cum altfel l-ai scrie. Deci, dacă cineva... dacă ai o propunere pentru un alt mod de a scrie, e în regulă. Dar acesta este k, acesta este pentru toți k. Nu știu... dacă ai avea doar un număr limitat limitat de k, ai putea să-l iei pe cel mai mare. Dar, deoarece este pentru toți k, trebuie să-l scrieți ca unire. Acum, vreau să argumentez că clasa P este o clasă importantă. Și de ce a avut atât de mult impact asupra subiectului și în ceea ce privește aplicațiile? Deci un lucru este că clasa P este invariantă pentru toate modelele deterministe rezonabile. Ce vreau să spun prin asta? Deci am definit clasa P în termenii acestor clase de timp aici, care, la rândul lor, sunt definite în termeni de modelul unei benzi. Deci am definit P folosind mașini Turing cu o bandă. Acum, dacă am fi definit P în termeni de mașini Turing cu mai multe benzi, obținem exact aceeași clasă, deoarece mașinile Turing cu o bandă și mai multe benzi sunt legate polinomial unele de altele. Și din moment ce luăm uniunea peste toate polinoamele, acea diferență de polinoame se va spăla. În mod similar, am putea defini P folosind oricare dintre celelalte modele deterministe rezonabile. Și obținem exact aceeași clasă. Deci, într-un fel, revenim ceea ce am... situația pe care o aveam în teoria computabilității, când clasa de limbaje decidabile nu depindea de alegerea modelului. Aici, clasa P nu contează în funcție de alegerea modelului determinist rezonabil. Și, de asemenea, chiar și în cazul teoriei computabilității, trebuie să rămânem cu modele rezonabile care nu pot face o cantitate infinită de muncă într-un singur pas. Nu voi defini ce înseamnă a fi rezonabil. Aceasta este, într-un fel, o noțiune informală. Dar, printre toate aceste modele rezonabile, veți obține aceeași clasă P. Celălalt lucru care face ca P să fie important este că P corespunde aproximativ problemelor pe care le puteți rezolva într-un sens practic rezonabil. Acum, nu tocmai, problemele care necesită n până la a suta oară, ați putea susține că nu pot fi rezolvate în niciun sens rezonabil. Dar dacă te gândești , de exemplu, din perspectiva criptografiei, codurile criptografice pe care oamenii le vin sunt de obicei concepute pentru a le solicita, sau speranța este că ar necesita un efort exponențial pentru a se sparge. Dacă cineva ar găsi chiar și un algoritm de la n la o sută de spart, acesta ar sparge un cod, oamenii ar simți că codul nu este sigur, chiar dacă n la o sută este încă mare. Deci este un fel de test dur. Dar este încă folosit ca un fel de test de turnesol pentru solubilitatea practică, dacă îl puteți rezolva în timp polinomial. Practic, v-ați dat seama cum să evitați căutările mari dacă puteți rezolva probleme în timp polinomial. Vom spune mai multe despre asta mai târziu. Dar ceea ce vreau să scot aici este că am combinat, aici, în clasa P, ceva care este frumos din punct de vedere matematic, elegant din punct de vedere matematic cu ceva care este practic relevant. Și când ai o combinație a celor două, atunci știi că ai un câștigător. Atunci știi cum ai un concept care va face diferența. Și asta a fost adevărat pentru clasa P. Acest lucru a fost foarte influent în cadrul și fără teoria calculului. Deci, să ne uităm la un exemplu. Să definim un nou limbaj pe care nu l-am văzut până acum, deși este similar cu procedurile pe care le-am analizat înainte. Limbajul PATH, care este locul în care vă voi oferi un grafic G, două noduri în grafic, s și t, unde mă gândesc la G ca un grafic direcționat. Deci direcționat înseamnă că conexiunile dintre nodurile din G vor fi direcționate. Și că au săgeți pe ele. Nu sunt doar linii, ci au o orientare cu o săgeată. Deci G este un grafic direcționat care are o cale de la s la t care respectă direcțiile. Deci o astfel de... Cred că aș putea chiar să am o poză aici, da. Așa că imaginează-ți aici, aici este graficul tău. Dacă îl puteți vedea, există mici săgeți care leagă nodurile. Și vreau să știu dacă există o cale de la nodul s la nodul t. Deci aceasta este o imagine a unei probleme, o instanță a unui grafic al unei probleme PATH. Și vreau să găsesc un algoritm pentru asta. Și pot arăta că există un algoritm care funcționează în timp polinomial pentru această problemă PATH. Și algoritmul, oricare dintre algoritmii standard de căutare ar funcționa aici. Dar să includem, de dragul caracterului complet, algoritmul de căutare pe lățimea întâi pe care l-am explorat anterior când vorbim despre automate finite. Deci vom marca s. Și vor continua să repete până nu se va marca nimic nou. Și vom marca toate nodurile care au fost accesibile printr-o singură săgeată de la un nod marcat anterior. Și apoi este marcat CFT, După ce ați marcat tot ce puteți ajunge. Așa că o să marcați... să vedem, ilustrat, aici cred că am acest lucru indicat. Da, vei marca toate lucrurile la care se poate ajunge de la început-- de la nodul s. Și apoi vezi, după ce nu poți marca nimic nou, dacă nodul G este marcat. Și dacă este, vei accepta. Dacă nu este, respingi. Acum, putem analiza și asta. Și nu voi petrece mult timp analizând algoritmi aici. Dar haideți să facem asta o singură dată. Facem o grămadă de iterații aici. Așa că vom repeta până nu se marchează nimic nou. Așa că de fiecare dată când notăm ceva nou, putem face doar asta, de cel mult, de n ori. În acel moment, am marcat totul. Deci numărul de iterații aici va fi, cel mult, n. Și acum, de fiecare dată când marchem ceva, trebuie să ne uităm la toate nodurile marcate anterior și să vedem spre ce lucruri indică pentru a le marca și pe ele. Deci aceasta va fi o buclă interioară, care, din nou, are, cel mult, n iterații, deoarece trece prin toate nodurile marcate anterior. Și apoi, odată ce avem asta, putem scana G pentru a vedea-- pentru a marca toate noile-- toate nodurile pe care nu le-am marcat încă, indiferent dacă sunt conectate cu un nod marcat anterior printr-o margine. Și sunt generos aici, pentru că nu prea îmi pasă. Acest lucru se poate face în cel mult n pași pătrați pe o mașină Turing cu o bandă. Nu am de gând să descriu implementarea. Dar ți-o las ca exercițiu. Dar acest lucru este simplu. Deci numărul total de pași aici ar fi de n iterații ori n iterații ori n pătrat. Deci vei fi, cel mult, de la n până la a 4-a treaptă necesară. Deci acesta este un algoritm polinom. Și dacă am ajuns cu până la al 4-lea, sau cu n la al 5-lea, sau cu n cub, nu prea îmi pasă. Pentru că doar încerc să ilustrez că totalul este polinom. Și asta este tot ceea ce îți voi cere de obicei să faci. Deci, pentru a arăta timpul polinom, ceea ce vă voi cere să faceți este să arătați că fiecare etapă, fiecare etapă a acestui algoritm, ar trebui să fie clar polinom. Și că numărul total de etape, îmi pare rău, aici ar trebui să spună etape , ar trebui să fie polinom. Deci fiecare etapă este polinom. Și după ce faci toate iterațiile, numărul total de etape care sunt executate este polinom. Și așadar, toate împreună, timpul total de rulare, numărul total de pași, va fi polinom. Deci, așa am scrie algoritmi polinomi în această clasă. Deci, să vedem dacă există întrebări aici. Nu vreau să ajung prea mult înaintea oamenilor. Să vedem. Da, în această teoremă, vorbesc despre mașini Turing cu o bandă , pentru că definim totul în termeni de mașini Turing cu o bandă. Dar acum, în acest moment, când vorbim despre timpul polinomial, analiza mea se bazează pe mașinile Turing cu o bandă. Dar, în general, puteți folosi orice model determinist rezonabil pe care să vă efectuați analiza, deoarece toate sunt echivalente polinomial. Deci, din perspectiva de a arăta că o problemă este în timp polinomial, este în P, puteți utiliza oricare dintre modelele pe care le doriți pentru a fi convenabil. Oh, asta e o întrebare bună. Ce este n, mulțumesc că ai pus această întrebare. n va fi întotdeauna rezervat pentru a indica lungimea intrării. Deci aici, n va fi atunci când codificăm G, s și t. Și aici, de asemenea, nu am spus asta, dar presupun că codificarea pe care o utilizați este, de asemenea, cumva rezonabilă. Cred că vom vorbi puțin mai mult despre asta în următoarea prelegere, care va avea loc după semestrul. Dar puteți provoca probleme dacă ați încercat intenționat să veniți cu codificări urâte, care vor reprezenta lucruri cu multe caractere inutil. Dar dacă încerci să fii rezonabil, atunci folosește oricare dintre acele codificări și vei fi bine. Deci da, deci n este lungimea reprezentării intrării. Să vedem. Cineva încearcă să afle cum se desfășoară asta aici. Scanați G pentru a marca tot y unde xy este o muchie. Spun că o poți face în n pași pătrați. Dacă aveți x, îl puteți marca într-un anumit loc pe bandă. Și apoi, pe măsură ce te duci la fiecare alt nod, la fiecare altă margine, poți să te întorci și să compari x cu x-ul marginii și apoi să vezi-- și apoi să găsești y. Adică, va fi prea dezordonat să vorbim aici. Adică, ți-l las ca un exercițiu. Nu voi încerca să- mi fac drumul explicând de ce poți face asta în n pași pătrați. Dar nu e greu. Voi sunteți cu toții niște algoritmi intenționați. Vrei să știi algoritmii pentru asta, nu o să fac asta, îmi pare rău. Poza la nivel înalt aici. Dacă vrei... dacă vrei să te uiți la analize detaliate, acesta nu este cursul potrivit pentru tine. Poate k egal cu n? Ce este k? Nu, dacă vorbiți despre acest k aici, k nu poate fi egal cu n. Nu ne uităm la n la n. Acestea sunt toate k fixe, este ca n pătrat, n cub, dar nu n la n va fi o limită exponențială. Și deci asta nu va fi inclus în această uniune. Deci suntem aproape de sfârșitul orei. O să introduc aici o ultimă limbă, numită HAMPATH. Și problema HAMPATH este -- voi cere acum, din nou, o cale de la s la t, dar acum un alt fel de cale, una care trece prin fiecare nod al lui G de-a lungul drumului. Așa că caut o cale care să meargă, care să lovească fiecare nod al lui G, nu doar calea cea mai scurtă și cea mai directă. Dar într-un sens, calea cea mai indirectă, cea mai lungă cale care trece de la s la t care vizitează orice altceva de-a lungul drumului. O cale de acest fel, care lovește fiecare nod al graficului, se numește cale hamiltoniană. Pentru că matematicianul Hamilton le-a studiat și a făcut niște definiții despre asta. Nu am de gând să... Nu cunosc istoria de acolo. Dar știu doar că se numesc căi hamiltoniene. Deci iată o poză. Vreau să ajung de la s la t. Dar vreau să iau totul pe parcurs. Deci, după cum vă amintiți, problema PATH în sine poate fi rezolvată în P. Și ceea ce aș dori să știu, poate această modificare simplă, în care vă cer să vizitați orice altceva de-a lungul drumului, este acea problemă și în P? Și o să prezint asta ca un check-in pentru tine. Dar de fapt, înainte de a ajunge la asta, permiteți-mi să vă dau un algoritm pentru HAMPATH care nu funcționează pentru a arăta că este în P, pentru că este exponențial. Deci, iată un algoritm pentru HAMPATH, unde să fim m numărul de noduri din G. Și ceea ce voi face este să încerc fiecare cale posibilă în G și să văd dacă funcționează de fapt ca o cale hamiltoniană și să accept dacă este. Și apoi, dacă toate căile eșuează, atunci voi respinge. Așa că voi încerca fiecare rutare posibilă prin G. Dacă doriți să vă gândiți la asta, gândiți-vă la m ca la fiecare posibilă permutare a nodurilor lui G. Și apoi veți vedea dacă aceasta constituie de fapt o cale în G. care te duce de la s la t și trece prin toate nodurile. Deci acest algoritm ar funcționa. Acest lucru vă va oferi un algoritm corect pentru problema HAMPATH. Problema este că dificultatea este că există atât de multe căi posibile încât îți va lua un număr exponențial de pași pentru a executa acest algoritm. Nu este un algoritm de timp polinomial, pentru că există multe căi posibile pe care le-ați putea parcurge. Dacă îl priviți cu o limită foarte brută, dar într-adevăr nu puteți îmbunătăți acest lucru în mod semnificativ, ar exista m factorial, care va fi mult mai mare decât 2 la m căi de lungime m. Deci algoritmul va rula pentru timp exponențial, și nu pentru timp polinom. Deci întrebarea mea pentru tine este că o voi pune ca o problemă de check-in, este dacă ai putea face de fapt această problemă în timp polinomial. Deci, de ce nu te gândești la asta în timp ce eu pun întrebarea? Deci, luați problema HAMPATH, la fel ca problema PATH, pe care am descris-o cu acel algoritm de marcare, dar acum doriți să atingeți fiecare nod de-a lungul drumului, puteți arăta acea problemă ca fiind rezolvabilă în P? Și există o gamă întreagă de posibilități aici, în care fie răspunsul este da, puteți vedea care este algoritmul de timp polinomial cu siguranță nu, unde puteți demonstra că nu există un astfel de algoritm de timp polinomial . Și o să pun asta pentru tine și să vezi... Sunt curios să văd cu ce ai venit. Majoritatea oamenilor înțeleg greșit. Ei bine, greșit, nu știu... Nu sunt clar ce este greșit aici. OK, am terminat? Te rog verifica ceva. Văd că câțiva dintre voi nu ați răspuns. Dar sondajul se epuizează. OK, timpul a trecut. Deci, de fapt, după cum cred că mulți dintre voi știți, dar nu toți, aceasta este o problemă nerezolvată. Aceasta este o problemă nerezolvată foarte faimoasă, care este echivalentă cu problema P versus NP despre care vom vorbi foarte curând, care, printre altele, ar valora un milion de dolari dacă o rezolvați. Așa că pentru cei dintre voi care au răspuns a sau e, vă rugăm să vorbiți cu mine după prelegere. Și poate putem lucra împreună la asta. Nu, deci da, cred că majoritatea oamenilor ar crede că răspunsul este nu. Dar nimeni nu știe cum să demonstreze asta în acest moment. Așa că sunt interesat de cei care au venit cu ceea ce cred ei că sunt soluții. Și ar trebui să spun că există unii oameni care cred că ar putea exista și alte rezultate în afară de un simplu nu. Ceea ce ar putea fi dovedit în cele din urmă. Deci vom vorbi mai mult despre asta. Dar acesta este răspunsul la întrebare, doar pentru dvs. pentru a vă asigura că înțelegeți că este o problemă nerezolvată în acest moment. Deci nu știm. Cu siguranta da si categoric nu, cel putin dupa starea cunostintelor de care stiu, nu sunt raspunsuri corecte. Dar oricare dintre ceilalți, ei bine, cine știe? Așa că cred că acesta este sfârșitul a ceea ce am avut de spus pentru azi. Am acoperit teoria complexității ca o introducere, am analizat diferite modele posibile, ne-am concentrat pe modelul cu o bandă, am introdus, pe baza modelului cu o bandă , aceste clase de complexitate, clasa P. Și am arătat un exemplu al acestei probleme PATH în P. Am vorbit și despre această problemă HAMPATH, despre care vom vorbi mai multe după jumătatea mandatului. OK, așa că voi rămâne câteva minute dacă mai aveți întrebări. Altfel, lasă-mă să răspund la întrebări aici. Cineva mă întreabă despre părerea mea personală despre P versus NP. Opinia mea personală despre P versus NP este că P nu este egal cu NP și că o vom dovedi cândva. Când eram student absolvent, la mijlocul anilor '70, am crezut că se va rezolva până acum. Și, de fapt, am făcut un pariu cu Len Adleman, care ulterior am ajuns să devină A al codului RSA, că o vom rezolva până în anul 2000. Și am pariat pe ceea ce atunci era o mulțime de bani pentru mine, care era o uncie de aur, pe care nu am ajuns-- pe care am ajuns să o plătesc lui Len în anul 2000. Așa că nu mai fac pariuri. Dar tot cred că se va rezolva. Sper că voi avea ocazia să văd soluția. Petrec mult timp gândindu-mă la asta. Evident, nu am rezolvat , altfel am ști. Dar să sperăm că cineva o va face. Mi se pune o întrebare aici, care este un fel de întrebare interesantă, dar nu știu cu adevărat că sunt sigur că o înțeleg. Care este cea mai mare durată posibilă de rulare a unei probleme determinabile? Care este cel mai mare timp de rulare determinabil? Deci orice pot descrie poate fi... vor exista algoritmi care rulează mai mult timp. Puteți defini un algoritm. Puteți defini un timp de execuție, care, într-un fel, ar depăși toate celelalte timpi de execuție. Astfel încât orice timp de rulare va fi dominat de acel timp de rulare extrem de lent. Dar nu este ceva ce se poate descrie. Vă pot descrie prin procedee matematice. Dar nu va fi ceva de genul 2 la 2 la n. Cineva propune aici o soluție la problema HAMPATH presupunând timp polinomial. De ce este defectuos următoarele? Dacă s trece prin toate nodurile și termină la t, Ei bine, s nu suntem... vrei să spui, presupun că vrei să spui că începe cu s, dacă ajungem să trecem prin toate nodurile și terminăm la t, propunerea este puțin complicat aici. Practic, dacă pot încerca să o reformulez, vrei să încerci să-- din fiecare nod posibil, vrei să încerci să calculezi o cale către t și, de asemenea, o cale de la s la acel nod. Și puteți face asta pentru toate nodurile posibile. Dar nu există nicio modalitate de a le combina cu adevărat într-o singură cale care le vizitează pe toate. Rezolvarea pentru fiecare nod separat nu va face truc, pentru că trebuie să combinați cumva toate acele informații într-o singură cale, doar o cale care merge de la s la t și vizitează toate celelalte noduri de-a lungul drumului. Și că asta nu este... Nu văd care este propunerea ta, cum va funcționa asta de fapt. PUBLIC: Profesorul Sipser. O întrebare despre... despre care vorbeam mai devreme, despre ce am vorbit astăzi a fost definit pentru mașinile Turing cu o bandă , corect? MICHAEL SIPSER: Da PUBLIC: Deci și ați spus că am putea aplica pentru cele cu mai multe casete , dar sunt... Nu știu dacă am vorbit mai devreme, dacă ceva este acceptat de aparatul cu bandă cu o singură bandă, se poate aplica la mașina Turing cu benzi multiple și invers? Sunt interschimbabile așa? MICHAEL SIPSER: Ei bine, ele sunt interschimbabile doar în sensul că timpul de care ai avea nevoie... este o altă mașină. Dacă aveți o mașină Turing cu mai multe benzi pentru o anumită limbă, o puteți converti într-o mașină Turing cu o bandă utilizând procedura pe care am descris-o mai devreme în termen. Și vei primi o altă mașină. Va rula pentru o perioadă diferită de timp utilizând această procedură. Ideea este că timpul pentru care va rula mașina Turing cu o bandă nu este cu mult mai rău decât timpul mașinii Turing cu mai multe benzi . Deci, dacă timpul mașinii Turing cu mai multe benzi a fost n cuburi, cea a mașinii Turing cu bandă va fi pătratul. Deci va fi n la 6. Dar nu va fi-- trecerea de la mai multe casete la o singură bandă nu te va converti de la polinom la exponențial. Acesta este singurul punct pe care încerc să îl fac. Se va transforma dintr-un polinom într-un polinom ceva mai mare. Dar tot o să vă lase polinom. Eu nu... tu nu pari... Nu-ți pot vedea fața. PUBLIC: Nu, cred că părerea mea este doar, mai ales când vorbeam despre asta mai devreme, când ai adus-o în discuție, părea că ai putea transforma orice într-o mașină Turing cu mai multe benzi și ai reduce complet timpul . Dacă mi-ar plăcea ceva în n log n, dacă l-am făcut în aparatul Turing cu mai multe benzi, îl am în O mare din n, știi ce vreau să spun? Părea doar că banda multiplă era mult mai puternică. Dar atunci bănuiesc că nu, cu explicațiile și modelele despre care vorbeam astăzi. MICHAEL SIPSER: Da, nu aș spune... mașinile Turing cu benzi multiple sunt încă destul de limitate în capacități. Și nu uitați, atunci când aveți un aparat Turing cu mai multe benzi, aveți doar un număr fix de benzi. Adică, puteți defini și variante ale mașinilor Turing cu mai multe benzi care au un număr tot mai mare de benzi ca intrare, fie sub controlul programului, fie pot lansa benzi noi. Sau ar putea avea mai multe benzi în funcție de dimensiunea intrării, asta ar fi, de asemenea, o posibilitate. Acesta nu este modelul pe care l-am definit. Dar ai putea defini un astfel de model. Dar atâta timp cât cantitatea totală de muncă efectuată de mașină la orice pas va fi o cantitate de muncă polinomială, atunci o puteți converti într- o mașină Turing cu o bandă, cu doar o creștere polinomială a limitei. Vrei să fii atent la mașini – un lucru pe care am vrut să spun, dar nu l-am spus, așa că aici ar fi un model nerezonabil, pe care l-ai putea considera un model plauzibil. Dar nu va fi un model rezonabil din punctul nostru de vedere. Și acesta ar fi un model, de exemplu, care poate face o precizie completă, să zicem, aritmetică cu numere întregi cu un cost unitar pe operațiune. Deci fiecare operațiune contează ca costuri 1. Dar am să vă permit să faceți, de exemplu, adunări și înmulțiri. Lucrul care este rău în asta, în ceea ce privește faptul că este nerezonabil, este că după k pas, de fiecare dată când faci un pas, poți dubla dimensiunea întregului prin pătrat. După k pași, puteți avea un număr întreg, care are lungimea de 2 la k . Și acum, a face operațiuni acolo va implica o cantitate exponențială de muncă, chiar și în orice sens rezonabil. În sens teoretic, dar și în sens practic. Un model care funcționează așa nu se va putea converti într-o mașină Turing cu o bandă doar cu o creștere polinomială, deoarece efectuează o cantitate exponențială de lucru potențial într-un număr polinom de pași. Deci, acesta este într-un număr liniar de pași, în n pași. Deci acesta este un exemplu de model determinist nerezonabil . PUBLIC: Da, mulțumesc. MICHAEL SIPSER: Sigur. PUBLIC: Așa că sunt doar curios, tocmai mi-a trecut prin cap o idee. Bănuiesc că dacă ai o mașină Oracle Turing, practic doar ca să te uiți la descrierea unei mașini Turing și să decizi dacă este un decident sau nu, atunci ar fi puțin interesant să te gândești la ce se întâmplă dacă te uiți la toate. -- dacă aveți o descriere a unei perechi a mașinii Turing și un șir de intrare, atunci puteți căuta toate descrierile de dimensiunea n ale unei perechi, care sunt cei mai mulți pași pe care îi trebuie pentru ca o astfel de mașină să o convertească. Așadar, ai fi combinat mașina Turing și descrierile șirurilor de intrare , unde ai putea să te uiți la ceea ce este cel mai lung necesar pentru conversie. Nu știu. Este doar un gând întâmplător care a avut loc. MICHAEL SIPSER: Da, deci de fapt... vom vorbi despre mașinile Oracle Turing mai târziu în termen. Acestea sunt mașini care au acces la un fel de informații gratuite. Și asta se dovedește a fi... există câteva lucruri interesante pe care le poți spune despre ceea ce se întâmplă atunci când oferiți unei mașini, într- un fel, informații gratuit. Că altfel ați dori să-l taxați pentru calcularea efectivă a informațiilor respective. Dar să presupunem că îi vom permite să obțină acele informații fără a fi taxat. Și atunci cum afectează asta complexitatea altor probleme, de exemplu? Și așa vom vorbi despre asta mai târziu. Dar prea mult, cred, de o digresiune în acest moment pentru a încerca să definesc toate acestea. Dar bucuros să discut cu tine despre asta pe Piazza dacă vrei să ridici o întrebare acolo. PUBLIC: Mulțumesc. MICHAEL SIPSER: Sigur, nicio problemă. Cineva mă întreabă despre strategiile de rezolvare a problemei P versus NP. Vom vorbi și despre asta puțin mai târziu în termen. Dar în mod clar, pare dincolo de îndemâna tehnicilor noastre actuale să putem demonstra că unele probleme durează într-adevăr mult timp. Asemenea problemei cu calea hamiltoniană, se pare că nu poți face nimic cu asta semnificativ mai bine decât să încerci toate posibilitățile așa cum am descris în acel algoritm exponențial de pe ultimul diapozitiv. Dar cum demonstrezi asta? Nimeni nu stie. Așa că mulți oameni au încercat, inclusiv pe al tău cu adevărat. Adică, mi-am petrecut mult timp gândindu-mă la asta. Nu am reusit cu el. Dar există cineva, cred că, într-o zi, cineva va veni cu noua idee care este necesară pentru a o rezolva. Dar în mod clar va fi nevoie de un fel de descoperire, de o idee nouă. Nu va fi doar o combinație de idei existente, metode existente. Cred că am trecut de vreo 10 minute. Câțiva dintre voi sunteți încă aici. Am să-mi iau rămas bun de la voi, oameni buni. Și în scurt timp, mă voi alătura TA pentru întâlnirea noastră săptămânală de AT . Deci ne vedem. Mulțumesc că ești aici.