[DĂ CLIC] [FÂNĂ CLIC] [FÂNĂ CLIC] [FĂCÂND] [FĂCÂND] [ CLIC] MICHAEL SIPSER: OK. Buna tuturor. Să începem. Deci, a trecut ceva timp de când ne-am întâlnit într-o prelegere. Săptămâna trecută am avut vacanța. Am avut la jumătatea mandatului. Deci, cu asta, ce am făcut? Am terminat prima jumătate a cursului acum vreo două săptămâni, unde am vorbit despre... vorbeam despre teoria computabilității. Am trecut în a doua jumătate, vorbind despre teoria complexității. Așa că întoarce-ți mintea la asta. Am discutat despre diferitele modele și modalități de măsurare a complexității pe diferite modele - cel puțin în ceea ce privește durata de timp utilizată. Și în cele din urmă, ne-am stabilit pe mașina Turing cu o bandă, care este același model cu care lucram în prima jumătate a cursului și am susținut că, deși măsurile de complexitate vor diferi oarecum de la model la model. , nu vor diferi cu mai mult de o cantitate polinomială. Și așadar, din moment ce tipurile de întrebări pe care le vom pune vor fi, practic, dacă problemele sunt polinomiale sau nu, nu va conta cu adevărat ce model alegem dintre modelele deterministe rezonabile. Și astfel, mașina Turing cu o bandă este o alegere rezonabilă. Având în vedere asta, am definit clase de complexitate temporală, clasele TIME[T(n)]. Am definit clasa P, care era invariantă între toate acele modele deterministe diferite, în sensul că indiferent de modelul pe care îl alegem, urma să ajungem cu aceeași clasă P. Așa că asta pledează pentru naturalețea ei. Și am dat un exemplu în care această problemă a căii se află în P. Și am cam încheiat acea prelegere înainte de semestru cu discuția despre această problemă a căii hamiltoniene. Deci vom reveni la asta astăzi. Așa că astăzi, ne vom uita la complexitatea non-non-deterministă ; definiți timpul nedeterminist al claselor sau NTIME; vorbim despre clasa NP, problema P versus NP-- care una dintre cele mai faimoase probleme nerezolvate din domeniul nostru; și uitați-vă la programarea dinamică, unul dintre algoritmii de bază - algoritmi în timp polinomial și reproductibilitatea în timp polinomial - îndreptându-ne către discuția noastră despre completitatea NP, pe care o vom începe cursul următoare. Deci, cu asta, să trecem la conținutul de astăzi, care este, ei bine, doar o recenzie rapidă. După cum am menționat, am definit clasa de complexitate a timpului. Clasa de complexitate temporală este o colecție a tuturor limbajelor pe care le puteți rezolva într-un anumit timp , într-un anumit interval de timp. Deci, timpul n-pătrat, de exemplu, este toate limbile sau toate problemele pe care le puteți rezolva în timp n-pătrat. Identificăm probleme cu limbile aici. Și clasa P este colecția tuturor problemelor pe care le puteți rezolva sau a tuturor limbajelor pe care le puteți rezolva în timp polinomial. Deci este uniunea pe tot timpul n cu k-- deci n-pătrat, n-cub, n cu puterea a cincea și așa mai departe. Unire din toate aceste limite. Limbile asociate, aceasta este clasa P. Și am dat un exemplu, această problemă a căii. Am dat un algoritm pentru cale. Și apoi, am introdus această problemă de cale hamiltoniană. Deci, dacă vă amintiți? În loc să întrebăm doar un grafic dat dacă puteți ajunge de la s la t, acum vrem să știm dacă pot ajunge de la s la t, dar vizitați fiecare alt nod de-a lungul drumului. Așa că găsește o cale care trece prin toate celelalte și ajunge de la s la t. Și ar trebui să spun, de asemenea, că este o cale simplă, așa că ai voie să treci prin fiecare nod o singură dată. Și acum, întrebarea pentru această problemă este dacă putem rezolva acea problemă în timp polinomial. Putem modifica cumva algoritmul pentru cale pentru a ne oferi un algoritm care rezolvă calea hamiltoniană în timp polinomial? Desigur, am putea rezolva calea hamiltoniană cu un algoritm exponențial încercând toate căile posibile. Și asta va da un algoritm corect, dar există exponențial multe căi diferite și încercarea lor pe toate nu va da un algoritm de timp polinomial. Deci problema interesantă este că putem rezolva asta fără a căuta forța brută prin toate căile posibile. Și asta e o problemă la care nimeni nu știe răspunsul. În ciuda multor eforturi, oamenii nu au reușit să găsească un algoritm pentru asta. Dar, pe de altă parte, nu avem idee cum demonstrezi că nu există un astfel de algoritm. Adică, este de imaginat că s-ar putea dovedi așa ceva, dar pur și simplu nu știm cum să o facem. Și deci, acea problemă este o problemă nerezolvată și doar... asta nu este cu adevărat o notă pentru mine. Ce este uimitor, și asta vom arăta în următoarele câteva prelegeri, că ar exista consecințe foarte surprinzătoare dacă ai putea găsi o modalitate de a rezolva calea hamiltoniană în timp polinomial. Pentru că ceea ce ar rezulta imediat este modul în timp polinomial de, să zicem, factorizarea numerelor mari sau rezolvarea unui număr mare de alte probleme pe care nu știm cum să le rezolvăm în timp polinomial. Deci, așa cum am menționat, factorizarea este o problemă pe care în prezent știm doar să o rezolvăm cu un algoritm exponențial. Și nu pare să aibă nimic de-a face cu problema drumului hamiltonian. Par foarte diferit. Dar, totuși, dacă puteți rezolva calea hamiltoniană în timp polinomial, atunci puteți factoriza numerele în timp polinomial. Și așa, vom vedea cum să facem acea conexiune. Pentru asta construim în următoarele câteva prelegeri. BINE. Așa că vă bucurăm să primim orice comentarii și întrebări în acest sens, sau vom continua, dacă aveți întrebări despre mica noastră recenzie. Ei bine, trimiteți întrebări și ne putem opri la sfârșitul diferitelor diapozitive pentru a încerca să le răspundem. Și, bineînțeles, scrieți-le AT, care vă pot răspunde întrebărilor în timp ce eu țin prelegeri. BINE. Deci, pentru a începe , va trebui să vorbim despre complexitatea nedeterministă ca o variație a complexității deterministe. Deci, în primul rând, toate mașinile din această parte a cursului și limbile, totul va fi decizibil și toate mașinile vor fi hotărâtori. Deci, ce ne referim când avem o mașină nedeterministă care este un decident? Și asta înseamnă pur și simplu că toate ramurile -- nu este vorba doar că mașina se oprește la fiecare intrare, ci toate ramurile se opresc la fiecare intrare. Deci mașina nedeterministă este nedeterministă, are o mulțime de ramuri posibile. Toți trebuie să se oprească-- toți-- la fiecare intrare. Acesta este ceea ce face ca o mașină nedeterministă să decidă. Și vei transforma un decident nedeterminist într-un decident determinist. Dar întrebarea este, cât timp ar introduce asta? Cât timp suplimentar va costa? Și singurul mod pe care oamenii îl știu în prezent pentru acea conversie ar fi să facă o creștere exponențială. Practic, să încerce toate ramurile posibile. Și asta, desigur, este foarte lent. Deci, mai întâi, să înțelegem ce înțelegem prin timpul folosit de o mașină nedeterministă. Și ceea ce înțelegem prin timpul folosit este că ne uităm la fiecare ramură individuală , separat. Deci, o mașină nedeterministă, vom spune, rulează într-o anumită perioadă de timp dacă toate ramurile se opresc în acest interval de timp. Deci, ceea ce nu înseamnă că cantitatea totală de utilizare, cantitatea totală de efort prin adunarea tuturor ramurilor este de cel mult T din n. Doar că fiecare ramură utilizează individual cel mult T din n. Aceasta va fi definiția noastră. Și se va dovedi a fi modul corect de a privi asta pentru a obține ceva util. Deci acum vom defini clasa de complexitate analogă asociată calculului nedeterminist, pe care o vom numi timp nedeterminist. Deci timpul nedeterminist T din n este mulțimea tuturor limbajelor pe care le puteți face cu o mașină nedeterministă care rulează în ordinea T din n timp. Gândește-te doar la definiția pe care am avut-o pentru complexitatea deterministă, clasa de timp -- sau uneori oamenii o numesc dtime pentru a sublinia diferența. Dar să spunem doar că o numim în acest curs time versus ntime. Deci TIME[T(n)] este tot limbajul pe care îl puteți face cu mașina Turing cu o bandă care este deterministă. Dar aceasta este o mașină Turing nedeterministă pentru timp nedeterminist. Deci imaginea pe care este bine să o aveți în cap aici ar fi dacă vă gândiți la non-determinism în termenii unui arbore de calcul gândindu-vă la toate ramurile diferite ale non-determinismului. Toate aceste ramuri trebuie să se oprească și trebuie să se oprească în termenul stabilit. Așa că imaginați-vă, aici, acesta este T de n timp. Toate ramurile trebuie să se oprească în T din n pași pentru aceasta, o mașină Turing nedeterministă să ruleze în T din n timp și să facă un limbaj în clasa NTIME[T(n)]. Și prin analogie cu ceea ce am făcut înainte, clasa NP este colecția tuturor limbajelor pe care le puteți face nedeterminist în timp polinomial. Deci este uniunea peste toate clasele ntime în care limita este polinomială. OK, așa că multe dintre acestea ar trebui să pară foarte familiare, dar tocmai am adăugat o grămadă de nedeterministe și o grămadă de N-uri la locul lor. Dar definițiile sunt foarte asemănătoare. Și una dintre motivațiile pe care le-am avut pentru a privi clasa P a fost că aceasta nu depindea de alegerea modelului, atâta timp cât modelul era determinist și rezonabil. Și clasa NP nu va depinde, de asemenea, de alegerea modelului, atâta timp cât este un model nedeterminist rezonabil. Deci, este din nou o clasă foarte naturală de privit din punct de vedere matematic. Și, de asemenea, surprinde ceva interesant, oarecum, din punct de vedere practic - despre care vom vorbi în următoarele două diapozitive - și anume că surprinde problemele pe care le puteți verifica cu ușurință atunci când sunteți membru al limba. OK, deci vom vorbi despre asta. Dar dacă luăm, de exemplu, problema drumului hamiltonian. Când găsiți un membru al limbajului, deci acesta este un grafic care are o cale hamiltoniană de la s la t, puteți verifica cu ușurință că este adevărat prin simpla prezentare a căii. Nu toate problemele pot fi verificate în acest fel. Dar problemele care sunt în NP au acea caracteristică specială - că atunci când ai un membru al limbii, există o modalitate de a verifica dacă ești membru. Așa că vom vorbi despre asta, pentru că asta este într-adevăr cheia înțelegerii NP-- această noțiune de verificare. OK, lasă-mă să plec... a fost o întrebare bună aici. Lasă-mă să văd dacă vreau să răspund. Da, adică, aceasta este o întrebare un pic mai lungă decât la care vreau să răspund pe deplin, dar... ei bine, să trecem la următorul meu diapozitiv, care poate să scoată asta oricum. De fapt, sunt câteva diapozitive de acum încolo. Dar voi ajunge la acel punct. Deci, să ne uităm la Hamiltonian, problema hampath. Și ceea ce voi arăta este că problema drumului hamiltonian este în NP. Și o să te ghidez prin asta cam încet. Deci problema drumului hamiltonian, amintiți-vă, nu știm dacă este în P. Dar este în NP. Deci este într-una dintre acestea. Puteți rezolva calea hamiltoniană în timp polinomial dacă sunteți o mașină nedeterministă. De ce este asta? Ei bine, este din cauza paralelismului non-determinismului, care vă permite să verificați toate căile de pe diferite ramuri. Deci, permiteți-mi mai întâi să descriu cum aș scrie algoritmul. Și apoi, vom încerca să despachetăm asta și să înțelegem cum arată de fapt în termeni de calcul al mașinii Turing . Deci, în primul rând, luând problema drumului hamiltonian, vi se oferă acum o intrare , care este un grafic și nodurile s și t unde încerc să îmi dau seama este calea hamiltoniană - din nou, care vizitează toate nodurile, care te duce de la s la t. Și încercăm să facem acum o mașină nedeterministă, care va accepta toate astfel de intrări care au o cale. Deci, modul în care această mașină nedeterministă va funcționa este că, practic, își va folosi non-determinismul pentru a încerca toate căile posibile pe diferite ramuri. Și modul în care voi specifica aceasta înseamnă că, nedeterminist, vom scrie o cale candidată care va fi doar o secvență de m noduri, unde vom spune că este numărul total de noduri ale grafic. Amintiți-vă, o cale hamiltoniană, deoarece vizitează fiecare nod, va fi o cale cu exact m noduri în ea. Deci, voi scrie o secvență de noduri ca o cale candidată. Și în mod non-determinist voi alege fiecare secvență posibilă în acest fel. Dacă doriți să vă gândiți la metafora ghicirii pentru non-determinism, vă puteți gândi la mașina nedeterministă ca ghicind calea corectă, care va fi calea hamiltoniană de la s la t. Dar cred că pentru această discuție, ar putea fi mai util să ne gândim la toate ramurile diferite ale non-determinismului. Pentru că asta este poate mai util când ne gândim la asta în termeni de timp. Cred că te vei obișnui să te gândești la asta. Ar trebui să fii obișnuit să te gândești la asta în multe moduri diferite. dar poate că arborele de calcul al tuturor ramurilor ar putea fi cel mai util aici. Deci, acum, după ce scriem o secvență de noduri de cale candidată, acum trebuie să verific dacă aceasta este într-adevăr o cale. Și modul în care voi face asta este să spun, ei bine, acum, dacă am doar o secvență de noduri notate, ce înseamnă să fie o cale hamiltoniană de la s la t? Ei bine, mai bine începe cu s și se termină cu t, în primul rând. Și trebuie să ne asigurăm că fiecare pas al drumului este de fapt un avantaj. Deci fiecare pereche de la vi la vi plus 1 trebuie să fie o muchie în grafic. În caz contrar, acea secvență de noduri nu va fi o cale Hamiltoniană legitimă de la s la t. Și trebuie să fie o cale simplă. Nu poți repeta nodurile. Aceste patru condiții împreună ne vor garanta că avem o cale hamiltoniană. Și odată ce am notat o secvență candidată, putem doar să verificăm dacă secvența funcționează cu adevărat. În această a doua etapă a algoritmului, non-determinismul nu este necesar. Aceasta va fi o fază deterministă. Dar prima etapă a algoritmului va fi o fază nedeterministă în care va scrie toate căile posibile. Acum, voi încerca să despachetez asta pentru dvs., astfel încât să puteți vizualiza cu adevărat modul în care mașina face acest lucru. Și apoi, bineînțeles, știi că pe fiecare ramură a non-determinismului, vei verifica pentru a vedea dacă condițiile au fost îndeplinite. Și pe ramura respectivă, dacă nu au fost îndeplinite condițiile, ramura respectivă va respinge. Desigur, una dintre celelalte ramuri ar putea încă accepta, așa că așa funcționează non-determinismul. BINE? Așa că aș dori să vizualizez acest lucru ca arborele diferitelor ramuri ale calculului lui m pe intrarea sa. Deci, iată mașina noastră Turing nedeterministă. Care? Aceasta. Și îi oferiți intrarea G, s și t. Și cum funcționează de fapt mașina? Așadar, când spun că scrieți în mod nedeterminist o secvență de m noduri -- uite, acest lucru ajunge la un pic mai detaliat decât m-aș gândi în mod normal, pentru că încercăm să avem tendința să ne gândim la lucruri la un nivel superior. Dar doar ca să începem, cred că este bine să ne gândim la asta cu puțin mai multe detalii. Deci, să ne gândim la nodurile m ca fiind numerotate, având etichete numerotate de la 1 la m. Și mă voi gândi la ei etichetați de secvențele lor binare. Vom scrie acele noduri. Așa va trebui să funcționeze mașina pe acele numere pentru noduri. Ne vom gândi la ele ca fiind scrise în binar. Și acum, pe măsură ce mașina va scrie, să spunem, nodul v1. Deci, alegerea nedeterminată a primului nod al secvenței. Ce înseamnă asta de fapt în ceea ce privește prelucrarea pas cu pas a mașinii Turing m? Ei bine, se va ghici printr-o secvență de mișcări nedeterministe, biții care reprezintă numărul nodului pentru v1. De exemplu, v1 ar putea fi nodul numărul 5 din grafic. Desigur, nedeterminist, mașina se află pe diferite ramuri, alegând toate opțiunile posibile diferite pentru v1. Acestea vor fi diferitele ramuri aici. Dar una dintre ramuri ar putea fi... și ceea ce reprezint cu adevărat aici, acestea sunt... Probabil că aș fi putut scrie asta pe diapozitivul de aici cu litere mici. Dar acestea sunt ca opțiunile 0, 1. De aceea este un fel de arbore binar aici pentru a scrie biții din v1. Deci, aici, poate că acesta ar putea fi 101, reprezentând numărul 5, care ar putea fi primul nod pe care îl notez în secvența mea. O altă ramură va scrie nodul numărul 6. O altă ramură va scrie nodul numărul 2. Pentru că, în mod nedeterminist, facem toate alegerile posibile pentru v1. Asta încerc să arăt în această mică parte a calculului lui m pe această intrare. Deci, după ce a terminat de scris descrierea nodului pentru alegerea sa pentru v1, merge în jos pentru a alege ce este v2. Din nou, nedeterminist, deci vor fi mai multe ramuri pentru fiecare posibilă alegere a v2. Și așa mai departe, nod după nod. Apoi, va ajunge în sfârșit la ultimul nod, vm. Va scrie o mulțime de opțiuni pentru vm. Și în acest moment aici, am finalizat prima etapă a algoritmului. Acum, există un arbore imens cu toate opțiunile posibile pentru V-uri care au apărut în acest moment. BINE? Și acum, vom trece la a doua fază. Deci, după aceasta, vor fi, aici, o grămadă de pași determiniști ai mașinii. Deci nu este nevoie de mai multe ramificații, deoarece aici, am notat-- în acest moment, am ajuns la un punct în fiecare dintre acele locații, unde am ales unul dintre candidați, una dintre posibilele ramuri-- una din posibilele căi prin grafic, îmi pare rău. Deci, aici, ghicim căi potențiale în grafic. Și acum, vom verifica dacă de fapt am ales o cale care este o cale hamiltoniană de la s la t. BINE? Deci, fiecare dintre aceste ramuri va ajunge acum să accepte sau să respingă. Și întregul calcul va fi acceptat dacă cel puțin unul dintre ei a ajuns să accepte, ceea ce înseamnă că ai găsit de fapt o cale hamiltoniană. BINE? Nu știu dacă vă este de ajutor sau nu, dar asta este... dacă există întrebări despre asta, să vedem. Întrebarea despre există ceva - încercarea de a face o legătură aici între asta și istoriile de calcul. Adică, există un model aici care apare adesea în care doriți să verificați dacă ceva începe bine, se termină corect și că toți intermediarii sunt corecti. Deci cred că există o legătură mai profundă aici. Probabil prea greu de explicat, dar asta are ceva de-a face cu această problemă de cale hamiltoniană. De ce folosim reprezentarea binară? Ei bine, vom vorbi despre-- algoritmul ar fi funcționat la fel de bine dacă am folosi baza trei sau baza cinci sau baza 20 ca o modalitate de a ne scrie etichetele pentru noduri. Dar, într-un fel, nu contează. Totuși, alfabetul trebuie să fie finit , așa că este adevărat. Vreau să spun, de aceea nu este doar într-un singur pas al mașinii Turing că ați alege nodul ales pentru v1. Chiar trebuie să mergi la o secvență de pași. Pentru că fiecare dintre ramurile mașinii are doar un număr fix de opțiuni. Deci nu puteți, într-un singur pas al mașinii Turing, să alegeți toate posibilitățile diferite pentru v1. Asta trebuie să treacă printr-o secvență. BINE. Acum, permiteți-mi să fac un al doilea exemplu, problema compozitelor. Deci, limbajul tuturor compozitelor sunt toate non-primele, scrise din nou ca numere binare . Deci vom vorbi despre bază și reprezentare într-o secundă. Dar imaginați-vă că acestea sunt toate numerele care nu sunt prime. Și acea limbă este ușor de văzut ca fiind membru al NP. Iată, din nou, algoritmul pentru asta. Având în vedere x, vrem să acceptăm x, dacă nu este un număr prim. Deci are un factor non-trivial. Deci, mai întâi, modul în care va funcționa mașina non-deterministă este că va ghici acel factor. Deci, nedeterminist, va încerca fiecare factor posibil. Y va fi un număr între 1 și x. Dar fără a include 1. Trebuie să fii un factor interesant, deci să nu incluzi unul în numărul în sine. Deci ceva strict între ele. Și atunci vom-- după ce am ales nedeterminist y, atunci vom testa pentru a vedea dacă y este într-adevăr un factor. Deci vom vedea dacă y se împarte egal în x cu un rest de 0. Dacă acea ramură a ales cu succes y-ul potrivit, va accepta. Și o altă ramură în care ar fi ales y greșit, nu o va face. Și dacă x este într-adevăr un număr compus, o ramură va găsi factorul. Acum, baza nu contează. Ar fi putut folosi baza 10, pentru că puteți face conversia de la o bază la alta. Deci, aceasta este într-adevăr în ceea ce privește reprezentarea noastră a numărului. Dar vreau să subliniez un punct aici, că schimbarea - nu vrem să scriem numărul în unară - scriind numărul lui k ca o secvență de k1s. Asta nu este chiar o bază. Aceasta este doar o reprezentare exponențială a numărului și asta schimbă jocul. Pentru că dacă măriți exponențial intrarea, atunci se va schimba dacă algoritmul în raport cu acea intrare exponențial mai mare este polinom sau nu. Deci un algoritm care ar fi putut fi exponențial inițial atunci când numărul este scris în binar ar putea deveni polinom dacă numerele sunt scrise în unară. Și vreau să menționez ca o notă secundară, că limbajul compozit -- sau numerele prime, de altfel -- ambele sunt NP. Dar nu vom acoperi asta. Deci, în timp ce problema drumului hamiltonian nu se știe dacă este NP, problema primelor și compozitelor sunt NP. Deci asta se știa. Acesta a fost de fapt un rezultat foarte mare în domeniu. Rezolvat de oameni de la unul dintre Institutul Indian de Tehnologie acum aproape 20 de ani acum. Deci, să ne întoarcem aici, să încercăm să obținem un sentiment intuitiv pentru P și NP. Și vom reveni acum la această noțiune de NP corespunzătoare verificabilității ușoare. NP sunt limbile în care puteți verifica rapid calitatea de membru. Voi încerca să explic ce înseamnă asta. În schimb, P sunt limbile în care puteți testa rapid calitatea de membru. De repede, folosesc timpul polinomial. Asta va fi, pentru noi, asta înseamnă rapid în acest curs. În cazul problemei căii hamiltoniene, modul în care verificați apartenența este că dați calea. În cazul compozitelor, modul în care verificați apartenența este să dați factorul. În aceste două cazuri și, în general, atunci când avem o problemă care este în NP, considerăm că această verificare are -- îi dăm un nume special, numit certificat, sau uneori un certificat scurt, pentru a sublinia polinomialitatea certificat. Este ca un mod de a dovedi că ești membru al limbii. În cazul COMPOZITELOR, dovada este factorul. În cazul lui HAMPATH, dovada este calea, calea hamiltoniană. Comparați asta, de exemplu, dacă ați avut un număr prim. Demonstrarea unui număr este compus este ușor, deoarece doar expuneți factorul. Cum ați demonstra că un număr este prim? Care este certificatul scurt prin care se dovedește că un număr nu are niciun factor? Asta nu este atât de evident. De fapt, există modalități de a face acest lucru, în care nu am de gând să intru în cazul testării numerelor prime. Și acum se știe chiar că este în P, așa că este și mai bine. Dar nu există o modalitate evidentă de a demonstra că un număr este prim cu un certificat scurt. Acest concept de a fi capabil să verifici când ești membru al limbii, acesta este cheia pentru înțelegerea NP. Aceasta este intuiția pe care trebuie să o dezvolți și, sperăm, să o iei din prelegerea de astăzi, sau cel puțin gândindu-te la ea, citind cartea și așa mai departe. Dacă comparați aceste două clase, P și NP. P, în primul rând, va fi o submulțime a lui NP, atât în ​​ceea ce privește modul în care l-am definit, deoarece mașinile deterministe sunt un caz special de mașini nedeterministe. Dar și dacă vrei să te gândești la testarea calității de membru, dacă poți testa cu ușurință calitatea de membru, atunci cu siguranță o poți verifica în ceea ce privește certificatul. Nici măcar nu ai nevoie. Certificatul este irelevant în acel moment. Pentru că oricare ar fi certificatul, vă puteți testa în continuare dacă introducerea este în limbă sau nu. Marea întrebare, așa cum am menționat, este dacă aceste două clase sunt aceleași. Deci, posibilitatea de a verifica rapid calitatea de membru, să zicem cu unul dintre aceste certificate, vă permite să renunțați la certificat? Nici măcar nu ai nevoie de un certificat și testează- l singur dacă știi limba. Și fă asta în timp polinomial. Asta e întrebarea. Pentru o problemă precum calea hamiltoniană, trebuie să cauți răspunsul dacă o faci în mod determinist? Sau puteți evita cumva acest lucru și veniți cu răspunsul direct cu o soluție de timp polinomială ? Nimeni nu știe răspunsul la asta. Și se întoarce, în acest moment, destul de mult timp. Sunt aproape 60 de ani acum. Problema a fost de aproximativ 60 de ani. Nu, ar fi 50 de ani. Nu, 50 de ani, aproape 50 de ani. Majoritatea oamenilor cred că P este diferit de NP. Cu alte cuvinte, că există probleme în P-- în NP care nu sunt în P. Un candidat ar fi problema drumului hamiltonian. Dar pare a fi foarte greu de demonstrat asta. Și o parte din motiv este cum demonstrezi că o problemă precum calea hamiltoniană nu are un algoritm de timp polinomial. Este foarte dificil să faci asta, deoarece clasa de algoritmi de timp polinomial este o clasă foarte bogată. Algoritmii de timp polinomial sunt foarte puternici. Și să încerc să demonstrez... nu există o modalitate inteligentă de a rezolva problema căii hamiltoniene. Se pare că este dincolo de matematica noastră actuală. Cred că într-o zi cineva o va rezolva. Dar până acum nimeni nu a reușit. Deci ceea ce am crezut că vom face este... Cred că am un check-in aici. Da. Și apoi ne oprim pentru o pauză. Să ne uităm la problema complementară, complementul HAMPATH. Ești în limba acum dacă nu ai o cale. Deci este acea problemă complementară în NP? Pentru ca acesta să fie cazul, ar trebui să avem certificate scurte de când un graf nu are o cale hamiltoniană. v-o las pe voi. Există trei opțiuni. BINE? Mă opresc aici, așa că asigurați-vă că obțineți creditul de participare aici. O să închei sondajul acum. Interesant. [RÂDE] Deci majoritatea greșește. Ei bine, nu greșit, nu știm. Cred că singurul răspuns corect la această întrebare este C. Pentru că nu știm dacă putem da sau nu certificate scurte pentru ca un graf să nu aibă o cale hamiltoniană. Dacă P este egal cu NP, atunci puteți testa în timp polinomial dacă un grafic are o cale hamiltoniană. Și atunci calculul în sine ar fi un certificat, indiferent dacă are o cale sau dacă nu are o cale. Pentru că ar fi ceva ce poți verifica cu ușurință. Deoarece nu știm sigur că P este diferit de NP, P ar putea fi egal cu NP, atunci este posibil să dăm un certificat scurt. Și anume, calculul algoritmului polinom. Deci singurul răspuns cu adevărat rezonabil la această întrebare este că nu știm. Gândește-te doar la asta. Aceia dintre voi care au răspuns cu da, totuși, trebuie să se întoarcă. Și am pus asta aici în mod explicit pentru că știu că este o confuzie pentru, ei bine, văd, pentru mulți dintre voi. Când avem calcule nedeterministe și aveți o mașină nedeterministă, nu puteți pur și simplu inversa răspunsul și obțineți înapoi o mașină nedeterministă. Non-determinismul nu funcționează așa. Dacă vă amintiți, complementul unui automat pushdown nu este un automat pushdown. Dacă aveți o mașină nedeterministă și inversați toate răspunsurile pe fiecare dintre ramuri, nu va fi recunoașterea sau deciderea limbajului complementar. Cred că acesta este ceva ce... dacă ați răspuns da, trebuie să vă întoarceți și să vă asigurați că înțelegeți de ce da nu este un răspuns rezonabil la această întrebare. Pentru că nu așa funcționează non-determinismul. Deci nu ai o înțelegere completă a non-determinismului. Și asta va fi foarte important pentru noi în viitor. Vă îndemn cu adevărat să vă dați seama și să înțelegeți de ce da nu este un răspuns bun la acest check-in. Bine, deci cred că vom... putem vorbi mai mult despre asta în pauză. Și așa ne vom întoarce aici în cinci minute. Cineva întreabă despre... pot fi generate secvențe infinite de mașină. Când vorbim despre, în special în secțiunea de complexitate a cursului, toate calculele vor fi mărginite în timp. Deci nu ne vom gândi la rulări infinite ale mașinii. Asta nu va fi relevant pentru noi. Deci să nu ne gândim la asta. Cum efectuează o mașină Turing diviziunea? Cum efectuează o mașină Turing diviziunea? Ei bine, cum faci diviziunea? [RÂDE] Diviziunea lungă este o operațiune care poate rula în-- procedura de divizare lungă pe care o înveți în școală, o poți implementa pe o mașină Turing. Da, o mașină Turing poate funcționa cu siguranță - face o împărțire lungă sau împărțirea unui întreg cu altul în timp polinomial. Alta intrebare. Putem spune în general, încercați să împărțiți y la x? Sau trebuie să enumerăm un șir de lungime y și să tăiem fiecare-- nu. Cred că este aceeași întrebare. Adică, dacă ai numere scrise în binar, cum ai face împărțirea? Nu vei folosi diviziunea lungă. Orice lucru, cum ar fi ceea ce este propus aici de cel care a întrebat, va fi un algoritm exponențial. Așa că nu face așa. De ce numerele prime din P-- compozitele din P nu implică numere prime din P? Implica. Dacă compozitele sunt în P, atunci primele sunt și în P. Când aveți o mașină deterministă, puteți întoarce răspunsul. Când aveți o mașină nedeterministă, este posibil să nu puteți inversa răspunsul. Deci mașină deterministă având doar o singură ramură, puteți face o altă mașină deterministă care rulează în aceeași perioadă de timp cu limbajul complementar. Pentru că pentru mașinile deterministe, la fel ca pentru decidenții din secțiunea de calculabilitate, puteți doar inversa răspunsul. Există aici o analogie între P și decidabilitate și NP și recunoaștere. Nu este o analogie etanșă aici, dar există o relație acolo. Cineva mă întreabă, care sunt implicațiile lui P egal cu NP? O mulțime de implicații. Prea lung pentru a enumera acum. Dar, de exemplu, ați putea sparge practic toate criptosistemele de care sunt conștient, dacă P este egal cu NP. Deci am avea multe consecințe. Cineva întreabă, deci compozite-- testarea de primalitate și compoziție poate fi rezolvată în timp polinomial. Dar factorizarea, destul de interesant, nu este cunoscută ca fiind rezolvabilă în timp polinomial. S- ar putea să vorbim despre asta puțin spre sfârșitul mandatului, dacă avem timp. Algoritmii pentru a testa dacă un număr este prim sau compus în timp polinomial nu funcționează prin căutarea factorilor. Ele operează într-un mod complet diferit, practic arătând că un număr este prim sau compus, analizând anumite proprietăți ale acelui număr. Dar fără a testa dacă are... testare, dar fără a găsi un factor. O altă întrebare aici despre întrebarea când vorbim despre codificări, trebuie să spunem cum codificăm numerele, valorile? Nu, nu trebuie. De obicei, nu trebuie să începem să scriem codificări, atâta timp cât acestea sunt codificări rezonabile. Deci nu trebuie de obicei. Vom vorbi despre lucruri la un nivel suficient de înalt încât codificările specifice nu vor conta. Să revenim la restul prelegerii noastre. Când vorbim despre, să zicem, această problemă P versus NP. Și cum arătați că o problemă s-ar putea să nu fie rezolvabilă în P, cum ar fi problema drumului hamiltonian? Mulți oameni care nu sunt practicieni în domeniu știu despre problemele P versus NP -- de-a lungul anilor, am primit multe, multe e-mailuri și scrisori fizice de la oameni despre asta. Din moment ce mi-am petrecut ceva timp gândindu-mă, sunt cunoscut că am petrecut ceva timp gândindu-mă la asta. Oamenii pretind că rezolvă problema, rezolvă P este NP, problema P versus NP, spunând practic, probleme precum calea hamiltoniană sau alte probleme similare, practic nu există nicio modalitate de a le rezolva fără a căuta prin multe posibilități. Și apoi trec printr- o analiză mare, lungă, care arată că există exponențial multe posibilități. Multe dintre dovezile care pretind că rezolvă P versus NP, toate arată așa. Trebuie doar să te uiți... undeva în acea ziare, va fi o declarație de genul: „Pentru a rezolva această problemă, în mod clar trebuie să o faci în acest fel”. Și acesta este defectul de raționament. Pentru că la fel ca și pentru problema factoring-- la fel ca și pentru problema de testare a compoziției, nu trebuie neapărat să o rezolvați căutând factori. Ar putea exista o altă modalitate de a face asta. S- ar putea să puteți rezolva problema căii hamiltoniene fără a căuta căi hamiltoniene. S- ar putea să existe un alt proces pe care îl puteți utiliza, care vă va oferi răspunsul. Clasa de algoritmi de timp polinomial este foarte bogată, poate face multe, multe lucruri. Și am vrut să vă prezint unul dintre cei mai importanți algoritmi de timp polinomial. Într-un fel, puteți face un anumit argument că acesta este cel mai fundamental algoritm de timp polinomial . Unii oameni s-ar putea certa cu mine în privința asta. Și acesta este un proces numit programare dinamică, pe care sunt sigur că unii dintre voi l-ați văzut deja în clasele voastre de algoritmi, iar unii dintre voi s-ar putea să nu îl aveți. Deoarece ai o problemă cu temele, vreau să petrec puțin timp descriindu-ți-l. Și asta este util pentru rezolvarea acestei probleme A CFG, pe care ți-o poți aminti din prima jumătate a cursului, implicând testarea dacă o gramatică generează un șir. Deci, vă amintiți această problemă A CFG? Dați o gramatică, gramatică fără context și un șir. Și vreau să știu, este în limbajul gramaticii. Deci asta se va dovedi a fi rezolvabil în timp polinomial, dar numai cu un fel de algoritm inteligent. Amintiți-vă, este decidabil. Ne-am decis asigurându-ne că convertiți gramatica în forma normală Chomsky. Atunci toate derivațiile au o anumită lungime. Încercați doar toate derivațiile posibile ale acelei lungimi și acceptați dacă oricare dintre aceste derivări generează w. Poate vă amintiți asta din prima jumătate a cursului. Asta oferă imediat un algoritm de tip NP pentru acest limbaj. Pentru că, practic, tu nedeterminist-- în loc să încerci cel mai secvenţial, toate aceste derivări, le încerci în paralel nedeterminist. Deci, nedeterminist, alegeți o derivație a acelei lungimi. Și îl accepți dacă generează intrarea. Acest lucru se potrivește în mod clasic cu modelul nostru de NP. Puteți crede că ghiciți derivarea și verificați dacă funcționează. Sau, în paralel, notând toate derivațiile posibile. Dar această problemă A CFG este în mod clasic o problemă NP, o problemă în NP. Și dacă vă imaginați... atunci care va fi certificatul? Dacă ați găsit o intrare care este în limbă, care este generată de gramatică, certificatul este derivația. Deci, dacă te uiți la asta în acest fel, s- ar putea să te gândești, ei bine, asta este tot ce poți face. Aceasta va fi o problemă NP, în NP, și nu va fi o modalitate de a evita căutarea derivației. Dar asta nu este adevărat. Există o modalitate de a evita căutarea derivației. Puteți construi derivarea folosind programarea dinamică. Și asta am vrut să vă descriu, cum funcționează. De asemenea, parțial pentru că este o problemă cu temele. Și cred că programarea dinamică este un algoritm foarte important. Înainte de a descrie ce este programarea dinamică, care este foarte simplă, apropo, să încercăm să ajungem la ea făcând o încercare de a rezolva această problemă doar folosind recursiunea obișnuită. Cum am rezolva problema A CFG? Deci ți se dă gramatică, ți se oferă o intrare. Să presupunem că gramatica este în forma normală Chomsky. Asta va fi de folos. Deci este o gramatică în formă normală Chomsky. Și vrem să vedem cum să testăm dacă puteți genera w. Și va fi un algoritm recursiv. Algoritmul recursiv va rezolva de fapt ceva mai general. Am de gând să- ți dau gramatica. Am de gând să- ți dau sfoara. Și vă voi permite, de asemenea, să începeți cu o altă variabilă în afară de variabila de pornire. Îți voi da o variabilă, R, și știu că vreau să știu, pot genera w începând cu R? Deci, aceasta este problema mea puțin mai generală, care va fi utilă în recursivitate. Deci, intrarea acum la acest algoritm este gramatica, intrarea și variabila de pornire. Și acum cum va funcționa algoritmul? Va încerca să testez, pot ajunge la-- există o derivație, ilustrată aici ca arborele de analiză, pentru w începând cu R? La asta încearcă să răspundă algoritmul. Pot obține w de la R? Modul în care va face asta este că va încerca să împartă w în cele două șiruri în toate modurile posibile. Ceea ce pare să fie exponențial, dar nu este. Există doar un număr polinom de moduri de a împărți șirul în două subșiruri. Doar de ordinul n, doar în funcție de locul în care faci acea tăietură. Deci nu e prea rău. Există un polinom, există doar n moduri de a face acea împărțire. Și, de asemenea, voi încerca fiecare regulă posibilă care vine de la R care generează două variabile. Deci acestea sunt ceea ce este permis în forma normală Chomsky, R merge la ST. Pentru fiecare modalitate posibilă de a tăia w în x, y și pentru fiecare regulă posibilă, R merge la ST, voi vedea, recursiv, pot ajunge de la S la x și de la T la y. Așa că o să-mi folosesc recursiunea acum. Acum că am șiruri mai mici în loc de w, pot aplica recursiunea și pot încerca să răspund astfel. Și acest algoritm va funcționa. Dacă am găsit o modalitate de a tăia w în x, y și am găsit o regulă, R merge la ST astfel încât S generează x și T generează y, atunci sunt bine. Știu că pot genera w din R. Și dacă nu există nicio modalitate de a tăia w pentru a satisface asta, sau dacă nu găsesc nicio modalitate de a împărți w în x, y și o regulă R merge la ST care face ca acest lucru să funcționeze , dacă toate căile posibile eșuează, atunci nu puteți ajunge de la R la w. Și apoi puteți decide problema inițială A CFG acum, pornind de la variabila de pornire, în loc de orice R vechi. Conectați variabila de pornire pentru R. Deci, acest algoritm funcționează și poate fi folosit pentru a rezolva A CFG. Dar întrebarea este, este polinom? Și nu este. Pentru că de fiecare dată când faceți recursiunea, în esență adăugați un alt factor de n. Pentru că aici, așa cum am subliniat, acesta este un factor de n. Dar asta se întâmplă de fiecare dată când faci un nivel recursiv. Și vă puteți imagina, fac doar o analiză foarte brută aici, în funcție de modul în care împărțiți w. Dar aproximativ vorbind, va fi împărțit la jumătate de fiecare dată, așa că vor fi jurnal n niveluri. Deci, asta înseamnă că vei înmulți n cu el însuși log n ori, sau vei da un n la algoritmul log n. Acesta nu este polinom, deoarece polinoamele se termină cu o constantă, pentru o constantă fixă. n la log n nu va fi polinom. Acesta nu este un algoritm polinom. În schimb, va trebui să faci ceva puțin mai inteligent. Va fi aceeași idee de bază, dar bazându-ne pe o mică observație. Și mica observație este că atunci când... această implementare non-polinomială pe care tocmai am descris-o este de fapt destul de proastă. Pentru că face o mulțime de recalculări a lucrurilor pe care le-a rezolvat deja. De ce este asta? Pentru că dacă vă uitați la numărul de subprobleme diferite posibile aici, odată ce vă dau G și vă dau w, câte subprobleme diferite de G, S și T există? Numărul de șiruri de aici, toate acele șiruri vor fi subșiruri ale lui w. Există doar aproximativ n subșiruri pătrate ale lui w. Întotdeauna voi genera, într-o subproblemă aici, un subșir de w dintr-o variabilă de pornire din gramatică. Deci, deoarece nu există atât de multe subșiruri diferite și nu atât de multe variabile de pornire diferite, numărul total de probleme posibile pe care acest algoritm va fi chemat să le rezolve va fi, în total, un număr polinom de subprobleme diferite. . Nu sunt foarte mulți dintre ei. Este doar ceva de genul ordinului lui n pătrat. Deci, dacă algoritmul rulează exponențial de mult timp, rezolvă aceeași subproblemă din nou și din nou. Asta e prost. De ce nu-ți amintești când rezolvi subproblema, ca să nu o rezolvi din nou? Făcând recursiunea îmbunătățită în care vă amintiți problemele pe care le- ați rezolvat deja, se numește programare dinamică. Nu știu de ce are un nume atât de confuz ca acesta. De fapt, este numit de mai multe lucruri diferite. Dar oricum, asta se numește programare dinamică. Este recursivitate plus memorie. Și aici doar mă repet. Nu există foarte multe subșiruri diferite, așa că de fiecare dată când în recursiunea dvs. undeva, veți lucra cu un subșir. Deci nu există atât de multe subprobleme diferite pe care le puteți rezolva. Și amintiți-vă doar când rezolvați subproblema și nu o rezolvați din nou. Permiteți-mi să vă arăt din nou acel algoritm aici, cu mica modificare. Deci, mai întâi de toate, permiteți-mi să vă ofer - acesta este același algoritm din diapozitivul anterior. O repet aici fără toate celelalte lucruri, ca să putem privi direct. Împărțindu-l în x și y pentru fiecare regulă posibilă. Și apoi recurge. Am de gând să adaug un mic pas 0 în prealabil, care spune că, dacă am G, w și R, permiteți-mi să verific mai întâi dacă l-am rezolvat deja înainte. Așa că trebuie să țin evidența celor pe care le-am rezolvat deja. Nu e prea rău, pentru că există doar ordine n pătrat posibile diferite pe care aș putea fi chemat să le rezolv. Așa că voi avea doar o măsuță unde îmi voi aminti de acestea. Și apoi de fiecare dată când primesc unul nou, am unul de rezolvat, voi verifica. E pe masa aceea? Și care este răspunsul? Deci nu va trebui să le repet. Practic, voi tăia acel copac, astfel încât să aibă doar un număr polinom de frunze. Și astfel, dimensiunea totală a acelui arbore va fi acum polinomială. Și astfel, asta va produce un timp de rulare polinom. Acest lucru, apropo, am învățat asta doar eu, sunt sigur că știți cu toții asta, cei care au luat asta la cursul de algoritmi, are un nume special numit memorare. Nu memorare. A venit din aceeași rădăcină, cred, dar memorarea, care este cumva amintirea rezultatelor unui calcul, astfel încât să nu trebuie să o repeți. Numărul total de apeluri va fi, cel mult, n pătrat, pentru acest algoritm, deoarece nu veți reface niciodată lucrările pe care le-ați făcut deja. Și când trebuie să treci prin asta, timpul de rulare - cantitatea totală de timp de care vei avea nevoie va fi cu totul polinom. Nu-mi amintesc care este înregistrarea mea pentru asta. Oh da. Acest lucru este cumva legat. Și nu ezitați să puneți întrebări, în timp ce vă gândiți la acest check-in. Dar înregistrarea spune aici că am rezolvat problema A CFG în timp polinomial. Ne spune asta că fiecare limbă fără context în sine este rezolvabilă și în timp polinomial? Gândește-te la asta și te rog să-mi dai un răspuns. Sper că te descurci mai bine la acest check-in decât la ultimul. Dar oricum, de ce nu te gândești la asta. Pot răspunde la câteva întrebări între timp. Cineva întreabă aici... de fapt, primesc câteva întrebări despre asta. De ce nu este ordinul n cub sau ceva mai mare decât ordinul n pătrat din cauza variabilelor? Variabilele nu depind de n. Când ți se oferă... ei bine, de fapt, nu este adevărat. Nu. Ai dreptate. Pentru că gramatica face parte din input. Deci, este posibil să aveți cât n variabile diferite în gramatica dată. Deci ai dreptate. Există potențial-- gramatica ar putea avea jumătate din dimensiunea intrării, iar intrarea în gramatica w ar putea fi jumătate din dimensiunea intrării. Deci nu m-am gândit la asta, dar ai dreptate. Există un număr potențial de variabile în diferite gramatici, așa că trebuie să adăugați un factor suplimentar, care ar fi cel mult dimensiunea intrării, pentru că sunt atâtea variabile pe care le-ați putea avea. Deci chiar ar trebui să fie, cred, comanda n cub pentru a ține cont și de asta. Plus toată munca care trebuie să aibă loc în ceea ce privește împărțirea lucrurilor. Pe o mașină Turing cu o bandă , va fi ceva muncă suplimentară doar pentru a efectua câțiva dintre acești pași individuali, deoarece cu o singură bandă lucrurile sunt uneori puțin incomode. Cred că timpul total de rulare va ajunge să fie ceva de genul n la a 4-a sau la a 5-a pe o mașină Turing cu o bandă. Dar acesta este un punct bun. Cineva spune, cum putem stoca n șiruri pătrate într-un timp finit? Nu spun timp finit. Avem timp polinom. Fiecare etapă a acestui algoritm are voie să ruleze polinomial mulți pași. Atâta timp cât este clar polinom, putem doar să scriem asta ca o singură etapă. Partea a doua ar trebui să spună... oh. E o greșeală de scriere aici. Deci folosește D. Mulțumesc. Este o greșeală de tipar. Mă tem că dacă îl schimb pe diapozitivul meu original aici, lucrurile se vor rupe într- un mod oribil. Să vedem. Mi-am distrus complet toboganul? Nu, asta e bine. Da multumesc. Buna observatie. Hopa! OK, ce face check-in-ul nostru? Cred că ai terminat aproape totul. Am petrecut mult timp cu asta. Încheiați sondajul. După cum vă amintiți din prima jumătate a cursului, deci răspunsul este A, într-adevăr. Amintiți-vă că am arătat că A CFG este decidabil și, prin urmare, fiecare limbă fără context în sine este decidabilă, doar pentru că puteți conecta o anumită gramatică la problema A CFG. Același raționament funcționează aici. Dacă aveți o limbă fără context , aceasta are o gramatică. Puteți conecta acea gramatică la problema A CFG. Și apoi, acesta este timpul polinomial, veți obține un algoritm de timp polinomial pentru limbajul respectiv. Bine să revizuim asta. Este același lucru, același argument pe care l-am folosit înainte. Nu vreau să petrec mult timp cu asta. Există un alt mod de a privi programarea dinamică. Vom vorbi din nou despre asta, poate într-o prelegere, probabil următoarea prelegere, doar pentru că ai o problemă cu temele. Dacă ați mai văzut programare dinamică, aceasta va fi ușor. Dacă nu l-ați văzut până acum, cred că va fi, probabil, puțin provocator. Un alt mod de a privi programarea dinamică este așa-numita versiune de jos în sus a programării dinamice. Și ceea ce ar însemna este că mai întâi rezolvi toate subproblemele. Rezolvați toate subproblemele mai mici înainte de a rezolva subproblemele mai mari. Este aici pe diapozitiv. Nu sunt sigur că vreau să discut. Dar, practic, rezolvați subproblemele aici, unde, începeți cu șiruri de lungime 1, și apoi construiți subprobleme cu subșiruri de lungime 2, apoi 3 și așa mai departe. Și fiecare dintre acestea se bazează doar pe subproblemele mai mici rezolvate anterior . Deci, puteți, într-un fel într-un mod sistematic, să rezolvați toate subproblemele din ce în ce mai mari pentru subșiruri din ce în ce mai mari. Asta oferă o perspectivă diferită asupra programării dinamice. Și pentru diferite probleme, uneori este mai bine să ne gândim fie la acest tip de proces bazat pe recursivitate de sus în jos , fie la procesul de jos în sus pe care îl descriu aici. Sunt într-adevăr complet echivalente. Versiunea care este descrisă pentru acest algoritm special, care apare în manual, este de fapt algoritmul de jos în sus. Deci nu ar trebui să fii confuz dacă vezi acolo ceva care arată oarecum diferit. Practic rezolvi toate subproblemele posibile, completând practic un tabel. Permiteți-mi să nu spun mai multe despre asta aici, din moment ce avem puțin timp. Există într-adevăr două perspective asupra programării dinamice. Așa că mergând de acolo, să schimbăm vitezele. Lăsați limbajele fără context și programarea dinamică în urmă. Și așa mă îndrept spre înțelegerea P și NP. Și pentru asta, vom introduce o nouă problemă numită problema de satisfacție. Și acesta este unul pentru care vom petrece mult timp. Dacă ați renunțat puțin în timpul discuției de programare dinamică , este timpul să reveniți la bord. Problema de satisfacție va fi o problemă de calcul la care vom lucra. Și are de-a face cu formula booleană. Deci acestea sunt expresii, cum ar fi formula aritmetică, cum ar fi x plus y ori z, dar în loc să folosim variabile numerice, vom folosi variabile booleene care iau valori booleene, adevărat, fals. Sau uneori reprezentați de 1 și 0. Operatorii pe care îi vom folosi vor fi operațiile și, sau, și de negație. Și, sau, nu. Voi spune o astfel de formulă, o astfel de formulă booleană, o vom numi satisfăcătoare - vom face un exemplu într-o secundă - dacă acea valoare a formulei se evaluează la adevărat dacă faceți o anumită atribuire de valori la variabilele sale. Deci, așa cum formula aritmetică va avea o anumită valoare dacă introduceți valori pentru variabile, formula booleană va avea o anumită valoare dacă introduceți valori booleene pentru variabilele sale. Și vreau să știu, există vreo modalitate de a conecta valori care face ca totul să fie evaluat drept adevărat. Formula în sine va fi evaluată la adevărat sau fals și am vrut să evaluez la adevărat. Iată exemplul nostru. Să luăm formula, phi, care este x sau y și x complement-- sau, nu x sau nu y. Deci notația x cu o bară deasupra, x complement, este doar x bară, nu x. Este doar modul dacă ești familiarizat cu cealaltă notație, operația not, care doar inversează 1urile și 0urile. O vom scrie cu o bară în loc de simbolul negației. Presupun că ați mai văzut cu toții algebră booleană, aritmetică booleană, unde operația și este adevărată numai dacă ambele intrări sunt adevărate. Acestea vor fi binare și operații și binare sau operații. Sau va fi adevărat dacă oricare dintre intrări este adevărată. Și nu este adevărat dacă singura sa intrare este falsă. Hopa, tocmai m-am uitat la răspuns. Aici vreau să știu, pentru această formulă booleană, aici este satisfăcătoare. Există vreo modalitate de a atribui valori variabilelor pentru ca această formulă să fie evaluată la adevărat? Deci, de exemplu, să încercăm lucruri. Să facem că x și y sunt adevărate. Deci x este adevărat și y este adevărat. Deci x sau y, ei bine, asta e adevărat. Dar acum trebuie să facem un și, așa că avem nevoie ca ambele părți să fie adevărate. Deci acum avem complementul x - ei bine, am spus că x este adevărat, deci complementul x este fals, complementul y este fals. Fals sau fals este fals. Deci acum avem un adevărat și un fals. Asta va fi fals. Nu am găsit o misiune satisfăcătoare. Dar poate mai e altul. Și de fapt, există. Dacă faceți x adevărat și y fals, atunci ambele părți se vor evalua drept adevărat și apoi veți avea adevărat și adevărat. Așa că am găsit o sarcină satisfăcătoare pentru această formulă. Este, de fapt, satisfăcător. Deci, dacă spuneți că x este 1 și y este 0, da. Acest lucru este satisfăcător. Acum, problema testării unei formule booleene, dacă aceasta este satisfăcătoare, va fi limbajul SAT. Este un set. Este o colecție de formule booleene satisfăcătoare. Și testarea dacă ești sau nu în SAT va fi o problemă de calcul importantă. A existat o teoremă uimitoare care a făcut cu adevărat să meargă în întregime acest subiect, descoperită independent de Steve Cook în America de Nord și Leonid Levin în fosta Uniune Sovietică, aproape exact în același timp, care a făcut o legătură între această problemă și toate problemele. în NP. Prin rezolvarea acestei probleme de satisfacție în timp polinomial, vă permite să rezolvați toate problemele din NP în timp polinomial. Deci, dacă ați putea rezolva această problemă stabilită în P, atunci calea hamiltoniană este de asemenea rezolvabilă în P. Dacă vă dați înapoi și vă gândiți la asta, este oarecum uimitor. Și metoda pe care o vom introduce se numește reductibilitate polinomială în timp. Să facem o verificare rapidă în acest sens. Acesta ar trebui să fie unul ușor. De ce nu te gândești doar la, SAT, problema SAT pe care tocmai am descris-o aici, este în NP? Trei secunde. Sunteți toți acolo? BINE. Încheierea sondajului. Sperăm că ai intuiția pentru NP că acestea sunt problemele -- a fi în NP înseamnă că atunci când ești membru al limbii, există o scurtă dovadă sau un scurt certificat de membru. Și în acest caz, certificatul scurt că formula este satisfăcătoare este atribuirea, ceea ce o face adevărată, numită și atribuirea satisfăcătoare. Deci da, acesta este un limbaj NP, limbaj care este în NP. Sunt o mulțime de lucruri pe care nu le știm în subiect, dar acesta nu este unul dintre ele. Știm că SAT este în NP. Deci, să vorbim despre metoda noastră pentru a arăta acest fapt remarcabil că, dacă puteți rezolva SAT în timp polinomial, atunci tot NP este rezolvabil în timp polinomial. Și folosește această noțiune de reducere a timpului polinomial, care este la fel ca maparea reductibilității pe care sper că ați ajuns să o cunoașteți și să o iubiți cu toții în prima jumătate a cursului. Dar acum, reducerea trebuie să opereze în timp polinomial. Deci, este aceeași imagine pe care am avut-o înainte, mapând A la B, transformând întrebările A în întrebările B. Dar acum transformarea trebuie să funcționeze rapid. Și obținem că dacă A este timp polinomial reductibil la B și B este timp polinomial, atunci A este și timp polinomial. Același model ca înainte. Dacă A este reductibil la B și B este ușor, atunci A este ușor. Iată un fel de esență a ideii, sau cel puțin schița ideii acestei teoreme Cook și Levin . Că dacă satisfiable este în P, atunci totul în NP poate fi făcut în P. Ceea ce se datorează faptului că, vom arăta că toate problemele din NP sunt timp polinomial reductibile la SAT. Acesta este faptul uimitor. Deci, prin urmare, dacă puteți reduce SAT în P utilizând această reducere, aduce totul împreună cu ea, totul poate fi redus la SAT. Deci trebuie doar să arătăm cum să facem asta. Există o analogie pe care am avut-o în prima jumătate a cursului, într-una din problemele noastre de teme, dacă vă amintiți. Am arătat că ATM are proprietatea foarte specială că toate limbile Turing recunoscute sunt mapate reductibile la el. Cred că a fost problema 2, sau 2a, fie în setul de probleme 3, fie în setul de probleme 2. Cred că în setul de probleme 3. Că fiecare limbaj de recunoaștere al lui Turing este timp polinomial reductibil la ATM. Și așa, o imagine foarte asemănătoare. Și există o mulțime de analogii aici pe care le puteți desena între secțiunea de calculabilitate și secțiunea de complexitate. Cu asta, știu că nu mai avem timp. Așa că haideți doar o trecere în revistă a ceea ce am făcut aici. Voi rămâne pentru întrebări pentru o vreme. Există o... OK, asta e o întrebare bună. Există o versiune obișnuită de analogie a reducerii pentru cartografierea reductibilității? Am avut reducerea generală pentru secțiunea de calculabilitate. Și am avut reducerea cartografierii pentru secțiunea de calculabilitate. Aici, ne vom concentra doar acum pe reducerea cartografierii. Deci, reducerea timpului polinomial va fi, prin presupunere, o reducere de cartografiere. Da, există și o noțiune generală de reducere a timpului polinomial . Acest lucru nu este necesar, dar dacă sunteți curios despre reducerea generală și cum să o formulați cu precizie, aceasta apare de fapt în capitolul 6 sub Reductibilitatea Turing. Aceasta este noțiunea generală de reductibilitate explicată într-un mod formal. Și există și reductibilitatea Turing în timp polinomial. Nu vom vorbi despre asta în acest curs. Alte intrebari? NP corespunde exact verificării în timp polinomial? Pentru ca eu să răspund la asta ca întrebare precisă, trebuie să avem o definiție precisă a verificării. Dar cu o definiție corectă, răspunsul este da. Deci, puteți defini un verificator ca un algoritm de timp polinomial care oferă un certificat, care preia un certificat și o intrare în limbă și va accepta dacă acel certificat este un certificat valid pentru acea intrare. Acest lucru este de fapt discutat în capitolul, cred, 9 al textului. Acum uit deja, ce se află în carte. Dar da, vă puteți gândi la NP în termeni de verificare ca definiție. Este dovedirea P egal cu NP la fel cu demonstrarea că un polinom - de fapt, pot chiar să fac -- dacă doriți, puteți posta și comentarii publice. Ar fi trebuit să fac asta în alte cazuri. Este demonstrarea lui P egal cu NP la fel cu a demonstra că o mașină de Turing nedeterministă în timp polinomial N are un timp polinom determinist? Da. Să presupunem că demonstrăm că P este egal cu NP, care este punctul de vedere minoritar, aș spune, punctul de vedere al minorității mici. Există unii oameni care cred că acest lucru este pe deplin posibil și ar putea chiar să fie cazul. Dar acesta este un grup foarte mic. Dar da, dacă demonstrați că P este egal cu NP, este același lucru cu a spune că fiecare mașină Turing nedeterministă cu timp polinom va avea o mașină Turing cu timp polinomis deterministă însoțitoare care face același limbaj. Exact asta înseamnă. La revedere, tuturor.