[SCHIHÂND] [FOȘIT] [CLIC] MICHAEL SIPSER: Bine ați venit, tuturor, înapoi la teoria calculului. Așa că suntem acum la cursul numărul 15. Și aceasta este o prelegere importantă. Ei bine, toate prelegerile noastre sunt importante, dar aceasta va introduce unul dintre subiectele majore pe care le vom vedea în curs de desfășurare în diferite forme în restul semestrului, care este noțiunea de problemă completă. În acest caz, va fi o problemă NP completă. Și cred că unii dintre voi probabil ați auzit deja de acest concept . Poate ați văzut-o în unele cursuri sau altele, dar o vom face într- un mod destul de atent și formal în următoarele două prelegeri. Așa că urmărim discuțiile noastre anterioare despre complexitate, complexitatea timpului. Am definit clasele de complexitate temporală și nu deterministă, după cum vă amintiți, clasele P și NP, au vorbit despre problema P versus NP, au analizat niște algoritmi interesanți pentru a prezenta probleme în P numită programare dinamică. Și am început să ne îndreptăm spre discuția despre completitudinea NP cu introducerea reducebilității în timp polinomial , care este legată de unele dintre noțiunile anterioare de reductibilitate pe care le-am discutat în secțiunea de calculabilitate. Revizuire rapidă -- ce înseamnă pentru o problemă să fie reductibilă în timp polinomial la alta -- aceasta urmează modelul nostru de concepte de reductibilitate, unde dacă o problemă este reductibilă la o altă problemă și acea altă problemă este rezolvabilă, atunci prima problemă este rezolvabilă . Deci, dacă o problemă este reductibilă la o problemă ușoară, acea problemă devine [INAUDIBILĂ].. Și tipul de reducere la care ne vom uita aici sunt reducerile de cartografiere, dar acum reducerile sunt calculabile în timp polinomial. Și așa am avut acest rezultat pe care l-am menționat data trecută, că, dacă A este timp polinomial reductibil la B și B este în P, atunci A este și în P. Deci asta va fi extrem de important pentru întreaga discuție care urmează. Intuiția noastră despre P și NP, repetând că aici-- problemele NP sunt cele în care puteți verifica cu ușurință apartenența, spre deosebire de a putea testa cu ușurință apartenența. Acestea sunt problemele care sunt în P. Verificarea necesită de obicei un fel de certificat care să stabilească o dovadă că intrarea este membru al acelei limbi. Și marea întrebare a câmpului, care rămâne o problemă nerezolvată, este dacă P este egal cu NP. Se numește întrebarea P versus NP. Și nu știm răspunsul - deci dacă există probleme care sunt în NP rezolvabile în timp polinomial nedeterminist - de obicei, acestea sunt probleme care implică căutarea - dacă pot fi rezolvate în timp polinomial, de obicei fără căutare . Și dacă P ar fi egal cu NP, atunci ai putea elimina întotdeauna căutarea. Și dacă P ar fi diferit de NP, atunci au existat cazuri în care trebuie să cauți. Și nu știm răspunsul la asta. Deci, în direcția explorării acestei întrebări și a ramificațiilor ei, am introdus această problemă numită SAT. Acestea sunt formulele booleene, care au o atribuire care le face să se evalueze la adevărat. Deci numim acele formule satisfăcătoare. Și am menționat, dar nu am dovedit încă-- și nu vom demonstra până la următoarea prelegere de marți-- că există această teoremă, o teoremă foarte remarcabilă care spune că, dacă aveți-- luați problema satisfacabilității și dacă este rezolvabil rapid, apoi toate problemele NP sunt rezolvabile rapid. Deci, dacă SAT este în P, atunci P este egal cu NP. Deci, într-un fel, SAT nu este un fel de-- este un fel de problemă super NP, în sensul că toată dificultatea oricărei probleme NP este încorporată în SAT. Deci, dacă SAT devine ușor, atunci toate celelalte probleme NP devin ușoare. Și în cele din urmă vom dovedi asta, dar acum stabilim terminologia care să ne permită să facem asta. Deci, oricum, vom ajunge acolo. Deci ingredientul cheie pentru demonstrarea acestei teoreme Cook-Levin este reductibilitatea timpului polinomial. Ceea ce vom arăta este că fiecare problemă din NP poate fi redusă în timp polinomial la SAT. Deci, fiecare problemă NP poate fi convertită într-o problemă SAT. Așadar, lucrând în acest sens, pentru că, atunci când te gândești la asta, există infinit de numere prime în NP și a fi capabil să arăți că toate sunt reductibile la SAT este, într-un fel, un fel de... trebuie să dovedești o teorema de nivel superior . Nu este doar o singură reducere. Prezentăm o schemă de reduceri, care arată că toate aceste probleme pot fi reduse la SAT. Și dezvoltându-ne intuiția în această direcție, ne vom uita astăzi la anumite reduceri de timp polinomiale . Și vom începe cu o reducere între două probleme pe care nu le-am văzut încă -- una dintre ele numită 3SAT și cealaltă numită clică. Deci, în acest diapozitiv, vom introduce aceste două probleme. Așadar, amintindu-ne, din nou, despre formulele booleene, vom lua în considerare o clasă specială de formule booleene, formă restrânsă de formule booleene numită formă normală conjunctivă. Și astfel această formulă aici în special este în acea formă normală conjunctivă. Așa că amintiți-vă... Am explicat altcuiva o parte din asta mai devreme în această dimineață, arătând unele dintre aceste diapozitive și sa subliniat că nu toți dintre voi s- ar putea să fiți familiarizați cu operațiile booleene ale și și sau. Deci acesta este simbolul sau aici. Acesta este simbolul și aici. Sper că ați văzut doar conceptul de Booelan și și sau. Sau este, într-un fel, un pic ca o uniune. Și este ca o intersecție. Și simbolurile de aici sunt puțin similare cu uniunea și intersecția -- simbolurile unirii și intersecției în sine. Forma V este puțin ca un simbol de unire ascuțit, iar forma în V cu susul în jos este puțin ca un simbol de intersecție ascuțit. Dacă nu ați mai văzut acele... ați văzut acea conexiune înainte, poate că este interesant să observați asta. Dar oricum, ce face ca această formulă să fie în formă normală conjunctivă? Ei bine, formulele normale conjunctive sunt organizate într-un anumit fel. Ei au aceste grupuri numite clauze în paranteze care sunt unite împreună, care sunt conectate prin acestea și operații. Și în cadrul acelor grupuri, care sunt numite clauze, elementele sunt OR împreună. Aceste elemente vor fi fie variabile, fie variabile cu negație, variabile negate. Așa că, pentru a repeta asta, acestea-- ei bine, doar pentru a afirma, acele variabile sau variabile negate vor fi numite literale, iar OR ale unui grup de literale vor fi numite clauze. Aceasta este doar terminologia standard în domeniu. BINE? Deci un literal este o variabilă sau o variabilă negată, iar o clauză este un sau al literalilor - doar o definiție. Bine, deci avem o grămadă de aceste clauze aici. Fiecare dintre clauze are un sau de literale în ea. Acum, o formulă Chomsky-- Chomsky-- formulă de formă normală conjunctivă -- Presupun că ambele sunt CNF-- dar formula de formă normală conjunctivă este una care este scrisă ca și dintre aceste clauze. Deci luăm aceste clauze, care sunt ele însele SAU -- noi și ele împreună, obținem o formulă care este forma normală conjunctivă. Conjunctiv înseamnă și, cred. Conjuncția este un și. Și apoi un 3CNF este un CNF în care fiecare clauză are exact trei literale. Deci, de exemplu, această formulă particulară este un CNF, dar nu este un 3CNF, deoarece are cel puțin două clauze care încalcă condiția a trei literale per clauză. Aceasta este în regulă, evident... această primă clauză. Și o problemă 3SAT-- deci aceasta este prima dintre cele două probleme despre care vom vorbi-- problema 3SAT este problema de satisfacție limitată la aceste formule 3CNF. Deci aceasta este o colecție de... un set de formule 3CNF care sunt satisfăcătoare. Așa că vă puteți gândi la el ca la un fel de caz special al problemei SAT, în care ne pasă doar de formulele de tip special. Acesta fiind un caz special, vă puteți imagina că aceasta ar putea fi o problemă mai ușor de rezolvat, dar, în general, se dovedește că nu este, așa cum vom vedea. Rezolvarea acestui caz special este la fel de grea ca și rezolvarea cazului general de satisfacție. Acum să trecem la a doua dintre aceste două limbi aflate în titlu, problema clicei. Deci, pentru asta, ne vom întoarce la teoria graficelor. Deci vom lua în considerare graficele, punctele și liniile -- conectarea lor. Și vom spune că o clică dintr-un grafic este o colecție de noduri - o colecție de puncte care sunt toate conectate perechi prin linii. Și o clică k este una în care aveți k astfel de noduri. Deci aici avem o clică cu trei, patru clicuri și o clică cu cinci. Și atunci problema clicei este să încercăm să găsiți clicuri de o anumită dimensiune specificată încorporate într-un grafic dat. Vi se va da un grafic, care vizează clica de mărimea k și doriți să știți, există un subset de noduri din graficul de dimensiunea k care sunt toate conectate între ele? Asta e problema clicei. Deci, evident, problema clicei, la fel ca și problema satisfacabilității, este o problemă decidabilă. Puteți doar să încercați fiecare subset posibil de k noduri și să vedeți dacă constituie o clică. Dar acesta va fi, în general, un algoritm exponențial. Dacă aveți-- k este o valoare mare-- ar putea fi jumătate din dimensiunea graficului-- s-ar putea să căutați o clică foarte mare. Apoi trebuie să încercați multe, multe subseturi pentru a vedea dacă vreuna dintre ele este o clică. De asemenea, va fi și-- sper că veți obține această intuiție-- aceasta este o problemă care este în NP. Problema clicei este o problemă NP, deoarece puteți verifica cu ușurință că un grafic are o clică k doar prezentând clica. BINE. Acum, deci limbajul de aici este că ai dat un grafic și un k și vrei să știi dacă graficul conține o clică k? Și ceea ce vom arăta este că aceste două probleme sunt conectate, că problema 3SAT din problema clicei sunt legate, prin aceea că puteți reduce în timp polinomial 3SAT la clică. Doar să stau înapoi la ea... înapoi pentru un minut, pare oarecum surprinzător. Nu există niciun motiv real, nici un motiv evident pentru care ar trebui să existe o legătură între trei 3SAT și clică. Arată foarte diferit unul de altul. Dar noi dăm asta... vom acorda acea reducere. Aceasta înseamnă că, dacă puteți găsi o modalitate de a rezolva problema clicei rapid, aceasta vă va oferi o modalitate de a rezolva problema 3SAT rapid. Și acesta va fi scopul. Așa că vom arăta acest lucru în următorul diapozitiv sau două, această reducere a timpului polinomial. O să trec prin asta încet, dar acesta este unul în care este cu adevărat important să încercăm să ne facem o idee despre cum funcționează, pentru că acesta este genul de lucru pe care îl vom face noi, iar tu vi se va cere să o facă și la teme și, eventual, la examenul final. Urăsc să folosesc asta ca forță de motivare aici, dar cel puțin ar putea fi o motivație pentru unii dintre voi, că trebuie să înțelegeți cum să faceți acest tip de reducere. Cred că, la un nivel înalt, ceea ce se întâmplă este că arătăm cum să recodăm o problemă de satisfacție a formulei booleene în problema testării dacă un grafic are o clică. Oh, să vedem dacă avem întrebări aici care apar în chat. OK, deci aceasta este o întrebare interesantă aici. Putem converti întotdeauna o formulă booleană în formă normală conjunctivă , în primul rând? Da. Răspunsul este că puteți converti întotdeauna o formulă booleană într-una echivalentă în CNF. Dar, în general, asta ar putea face formula exponențial mai mare. Așadar, simplul fapt că puteți converti formule în formă normală conjunctivă nu înseamnă că rezolvarea formulelor de formă normală conjunctivă pentru a testa satisfacabilitatea formulelor CNF va fi la fel de dificilă precum testarea cazului general, deoarece doar conversia ar putea fi exponențială. . Se întâmplă ceva mai mult... puțin mai complicat decât atât. Lasă-mă să văd aici. Dacă phi este o formulă satisfăcătoare care nu este în CNF, poate fi-- deci o întrebare similară-- deci întrebările pe care le primesc sunt despre conversia formulelor în CNF. Deci, da, o puteți face, dar nu în timp polinomial, în general, pentru că formula rezultată pe care o obțineți ar putea fi mult mai mare-- dacă căutați o formulă echivalentă. Dacă nu căutați o formulă echivalentă, atunci... desigur, atunci, în funcție de ceea ce căutați, s- ar putea să găsiți ceva mai mic. Aceasta este, cred, o întrebare de bază bună. De ce este clica în NP? Verificarea faptului că aveți o clică nu necesită parcurgerea tuturor clicurilor posibile? Trebuie să înțelegeți ce înseamnă verificarea. Verificarea înseamnă că puteți verifica ceva dacă vi se oferă un certificat. În cazul unei clici-- problema clicei-- certificatul este clica. Deci, odată ce ai certificatul, poți face verificarea în timp polinomial. Găsirea certificatului, desigur, ar putea fi dificilă. Deci te gândești la NP doar în contextul de a avea acel certificat. Deci, într-un caz de compoziție, certificatul ar putea fi factorul. Există probleme uneori în care ceea ce este certificatul nu este neapărat evident. Dar poate exista un certificat care să arate că intrarea este în limbă. În cele pe care le-am făcut până acum, poate puteți argumenta că certificatul este un lucru oarecum evident, dar nu este întotdeauna un lucru evident. BINE. Atunci de ce nu mergem mai departe? Deci, să vedem, cum facem această reducere a timpului polinomial de la 3SAT la clică? OK, aici mergem. Așa că am de gând să dau doar o reducere. Asta înseamnă definiția. Voi oferi o modalitate de conversie a formulelor în perechi, un G și un k, în care formula va fi satisfacabilitatea dacă și numai dacă graficul are o clică k. OK, așa că hai să o facem puțin prin exemplu. Și pentru a face asta... deci aici va fi o formulă acum. Este în 3CNF. De asta am nevoie pentru a putea face această reducere. Convertesc formulele 3CNF în probleme de clică. Trebuie să înțelegem puțin ce înseamnă atunci când spunem -- vorbim despre satisfacabilitatea unei formule ca aceasta, pentru că va fi de ajutor în reducerea. Evident, satisfacabilitatea înseamnă că... puteți găsi o atribuire pentru variabile. Deci, veți seta fiecare dintre aceste variabile - A, B și C și așa mai departe - la adevărat sau fals și doriți să faceți ca întreaga formulă să evalueze adevăratul. Dar ce înseamnă asta de fapt? Înseamnă că, din cauza structurii formulei, ca această formulă să fie adevărată corespunde ca fiecare clauză să fie adevărată -- deoarece clauzele sunt toate împreună, deci singura modalitate prin care formula să fie adevărată este aceea de a face fiecare clauză adevărată. Și pentru a face o clauză adevărată, trebuie să faceți adevărat cel puțin unul dintre literali. Deci este un alt mod de a gândi să satisfacă această formulă. Satisfacerea acestor sarcini satisfăcătoare [INAUDIBILE] face cel puțin un literal adevărat în fiecare clauză. Este foarte important să ne gândim la asta în acest fel, pentru că asta va fi baza pentru a face această reducere și toate reducerile. Este ceea ce face ca 3SAT să fie ușor de gândit, în ceea ce privește satisfacția sa. Dacă ați avut o problemă generală de satisfacție și ați avut o formulă de satisfacție, nu există nicio modalitate evidentă de a vedea cum arată sarcina satisfăcătoare , dar aici înțelegem cum arată. Are acea formă foarte specială , făcând un literal adevărat în fiecare propoziție - cel puțin un literal adevărat în fiecare propoziție. Deci acum vom face reducerea. Așa că o să iau din această formulă... Știu, pentru unii dintre voi, veți fi supărați. De ce merg incet? Dar vreau să mă asigur că suntem cu toții împreună și înțelegem care sunt regulile jocului și ce încercăm să facem. Încercăm să transformăm această formulă într-un grafic și un număr. Deci, în acest moment, treaba mea este să fac această reducere este să prezint acel grafic. Așa că o să fac asta și doi pași. În primul rând, vă voi spune care sunt nodurile graficului . Apoi vă voi spune care sunt muchiile acelui grafic [AUDIO OUT] În cele din urmă, vă voi spune care este numărul k. Așa va funcționa această reducere a timpului polinomial . Și trebuie să observăm, de asemenea, la sfârșit, că reducerea pe care mi-o primesc -- oferindu-vă, această procedură pentru construirea acestui grafic se poate face în timp polinomial, dar asta, cred -- veți vedea, odată ce voi Am terminat, asta e destul de evident. OK, deci mai întâi, așa cum am promis, nodurile - deci nodurile acestui grafic vor corespunde literalilor formulei. Fiecare literal va deveni un nod în grafic și va fi etichetat cu numele acelui literal. Fiecare nod va fi etichetat cu o bară a, a b sau c și așa mai departe. Deci iată. Deci, acestea sunt nodurile graficului G, câte unul pentru fiecare literal din formulă, etichetat ca promis. Acum trebuie să vă spun cum arată marginile. Îți voi spune care sunt marginile spunându-ți mai întâi ce nu sunt. O să vă explic mai întâi care sunt marginile interzise, ​​ce margini o să promit că nu le includ. Și apoi cei pe care îi voi include vor fi toți ceilalți. Deci, care vor fi marginile interzise? În primul rând, marginile interzise vor fi de două tipuri. Una este marginile dintre nodurile care provin de la literalele din aceeași clauză. Așa că aș numi asta fără margini în cadrul unei clauze. Deci, de exemplu, aceste trei noduri nu vor fi conectate unul la altul. Și voi indica asta scriind linii roșii întrerupte, ceea ce înseamnă că nu există o margine acolo. Acelora le este interzis să aibă un avantaj. Deci, aceste trei nu au margine și același lucru pentru fiecare alt triplu de trei noduri care provin din clauze. Alea nu sunt margini acolo. Și mai există o altă categorie de margini pe care o interzic și care sunt margini care pot-- care merg între etichete inconsecvente și nodurile cu etichete inconsistente. Deci, de exemplu, între a și o bară... acestea sunt inconsecvente. Nu e nimic în neregulă cu a merge de la a la d. Acestea nu sunt inconsistente. Acestea sunt doar etichete diferite. Sau mergând de la a la a... e în regulă. Dar de la un la un bar... asta nu este permis. Deci asta va fi o altă margine interzisă-- sau, de exemplu, a la o bară aici, o bară la a, sau de exemplu, de la această bară c la c-- interzis. BINE? Așa că vă imaginați că veți nota toate acele margini interzise. Acestea sunt toate marginile interzise și apoi, după ce le-ați îndepărtat, veți pune toate celelalte margini posibile. Așa că, de exemplu, permiteți-mi să le îngrijesc, astfel încât să nu interfereze cu imaginea, de la a la d, va exista un avantaj, pentru că acestea nu sunt interzise. de la a la a-- nu sunt interzise, pentru că ei-- sunt în clauze diferite și nu sunt inconsecvente. Sunt consecvenți unul cu celălalt. Deci, aici sunt o grămadă de alții. Nu le arăt pe toate. Devine foarte dezordonat. Dar aici sunt toate celelalte margini dintre noduri care sunt... unde nu sunt interzise. BINE? Și acesta este graficul. Asta e G. G sunt toate acele noduri și acele margini care nu sunt interzise. Și trebuie doar să- ți spun ce este k. k va fi numărul de clauze. Aceasta va fi dimensiunea clicei pe care o caut în acest grafic G pe care tocmai l-am descris pentru tine. Și voi pretinde că acest grafic aici pe care tocmai l-am descris va avea o clică k. k este numărul de clauze exact când phi a fost satisfăcut. E cam misto. Dacă phi este satisfacabilitatea, atunci va exista o clică k aici. Și dacă phi nu a fost satisfiability-- nici k-clică. Vom demonstra asta ca o afirmație pe următorul diapozitiv. OK, deci k este numărul de clauze. În regulă? Aveți întrebări despre construcția respectivă? Deci am terminat cu construcția. Ceea ce rămâne este să argumentăm de ce se lucrează. Până acum, foarte bine... hai să mergem mai departe. BINE. Deci, aici este aceeași construcție. Am eliminat marginile roșii interzise. Acestea sunt cele care au rămas, plus orice altceva care nu era interzis. Aceasta a fost aceeași formulă pe care am avut-o din diapozitivul anterior. Acum vreau să susțin că acea formulă este satisfiabilitate exact atunci când G are o clică k. Acum, de ce naiba este asta? Deci acesta este un dacă și numai dacă. S- a dovedit în ambele sensuri. Și acesta va fi genul tipic de lucru pe care veți dori să îl faceți atunci când expuneți o -- una dintre aceste reduceri, care este că veți avea ocazia să faceți asta. Și vom face asta și în exemplele noastre. OK, deci acum ceea ce vreau să arăt este că, dacă phi este satisfiabil-- deci să demonstrăm direcția înainte-- dacă phi este satisfiabil, atunci G are o k-clică. OK, deci în primul rând, dacă phi este satisfăcător, înseamnă că are o sarcină satisfăcătoare. Acum, iată o confuzie comună. Nu sunt sigur dacă este util să presărăm confuziile singur cu discuția, dar în cazul în care ești îngrijorat, s- ar putea să întrebi, ei bine, cum găsesc acea sarcină satisfăcătoare? Am crezut că a fost exponențial de greu de făcut. Aceasta este o dovadă. Acesta nu este un algoritm. Încercăm doar să argumentăm corectitudinea acestei construcții. Deci, nu mai există nicio îngrijorare cu privire la cum să găsiți o misiune. Spun doar, dacă există o misiune... dacă există o misiune satisfăcătoare, atunci ceva se va întâmpla ceva. Atunci se va întâmpla ceva -- în special, atunci vom arăta că G are o clică k. Deci, să presupunem că phi este satisfiabil, deci are o anumită misiune. Să luăm această sarcină satisfăcătoare. Și amintiți-vă că, în orice atribuire satisfăcătoare la o formulă în CNF, aceasta face ca cel puțin un literal să fie adevărat în fiecare clauză. Deci hai să alegem una dintre ele. Pot exista mai multe clauze care au mai multe literale adevărate. În acest caz, alegeți unul dintre ele în mod arbitrar. Nu am acest lucru indicat pe această diagramă aici, dar imaginați-vă că poate, chiar în prima clauză, a era adevărat; în a doua clauză, b a fost adevărat; în a treia clauză, e complement-- e bara a fost adevărată, nu e-- e bara a fost adevărată, ceea ce înseamnă că e în sine era falsă, dar e bara era adevărată. Și așa este modul în care fiecare dintre aceste clauze, la rândul său, a devenit adevărată în această sarcină satisfăcătoare, pentru că veți alege câte un adevărat literal pentru fiecare clauză. Și acum, din acea alegere de literali -- unul per clauză -- mă voi uita la nodurile corespunzătoare din G și voi pretinde că acele noduri luate împreună formează o clică k. OK, deci în primul rând, au numărul potrivit de noduri? Ei bine, sigur, pentru că aleg un nod per clică. Am spus deja k este numărul de clicuri, așa că primesc exact k noduri. Deci am cel puțin numărul potrivit de noduri. Dar de unde știu că sunt toate conectate unul la altul, acele noduri pe care tocmai le-am ales? Ei bine, toți sunt conectați unul cu celălalt pentru că am să spun... ei bine, pentru că nu existau margini interzise printre ei. Și amintiți-vă că punem toate marginile posibile cu excepția celor interzise. Deci, de unde știu că nu există margini interzise? Ei bine, care au fost regulile pentru a fi interzis? Înseamnă că ei-- două noduri în aceeași clică-- în aceeași clauză. Ei bine, aleg un nod per clauză, așa că nu pot avea niciodată două noduri din aceeași clauză. Așa că nu voi avea niciodată probleme cu prima condiție de a fi interzis. Deci, care este a doua posibilitate de a fi interzis, este că aleg două noduri care sunt inconsistente - de unde știu că nu am ajuns cu două noduri cu etichete inconsecvente? Ar fi rău, pentru că atunci ar avea o margine interzisă, și ce... rezultatul meu nu ar fi o clică. De unde știu că nu am ajuns să aleg... în acest grup aleg un, iar în acest grup aleg un bar? Ei bine, pentru că toți au venit din aceeași misiune. Toți erau adevărați liberali în clauze. Nu este posibil ca a să fi fost adevărat în această clauză și o bară să fie adevărată în acea clauză, deoarece dacă a este adevărat aici, o bară trebuie să fie falsă. Nu poate fi adevăratul literal din această clauză. Deci nu pot avea niciun nod inconsecvent să apară printre nodurile clicei mele. Și deci nu sunt în aceeași clauză. Nu sunt inconsecvenți, așa că marginea trebuie să fie acolo. Și asta va fi adevărat pentru fiecare pereche de noduri din acea clică-- din acel grup de noduri, și de aceea este o clică. Deci asta dovedește o direcție. Acum mai trebuie să dovedim cealaltă direcție, pentru că trebuie să spunem, ei bine, dacă G are o clică k, de unde știm că phi este satisfăcut? Deci asta e invers. Deci, să luăm orice clică k care este în G. Și de unde știu că pot obține din asta, o sarcină satisfăcătoare pentru formulă? Bine... am câteva întrebări bune aici în chat. Dar lasă-mă să merg mai departe. Deci, demonstrând inversul -- direcția inversă, presupunând că avem o clică k -- luați orice astfel de clică. Acum, în primul rând, observați că trebuie să aibă un nod în fiecare clauză. Nu poate avea două noduri în aceeași clauză sau zero noduri într-o clauză. În primul rând, nu poate avea două noduri în aceeași clauză. De ce? Ei bine, pentru că acele noduri nu sunt niciodată conectate unul la altul. Deci nu pot fi amândoi în aceeași clică, deoarece toate nodurile din clica interioară sunt conectate între ele. După cum am construit G, nodurile din aceeași clauză nu sunt conectate, așa că nu pot apărea într-o clică împreună. Deci va fi cel mult un nod din fiecare clauză care apare în această clică, dar... care apare în această clică. Dar avem, de asemenea, știm că avem k noduri, deci asta înseamnă că, dacă există cel mult unul per clauză și avem doar k clauze, înseamnă că fiecare clauză trebuie să aibă una. Dacă unei clauze îi lipsește un nod, atunci trebuie să existe o altă clauză care are două. Deci știm că fiecare-- că această clică pe care G are exact un nod în fiecare clauză. Deci, cum obținem de la această misiune satisfăcătoare? Deci, ceea ce vom face este să luăm literalele corespunzătoare care corespund aceluiași nod din clică, să luăm acei liberali și să setăm acele literale să fie adevărate, ceea ce înseamnă să setați variabila ca adevărată sau setarea -- dacă literalul a fost o bară, apoi setând a să fie fals, pentru că vrei ca o bară să fie adevărată. Vrei să setezi literalele să fie adevărate. Ei bine, acum setăm -- există un nod în fiecare clauză -- setăm un literal -- literalul corespunzător -- adevărat, așa că va stabili un literal adevărat în fiecare clauză. Deci asta înseamnă că va fi satisfăcător. Există un lucru pe care trebuie să fii foarte atent aici pentru a verifica -- pentru a ne asigura că facem acest lucru în mod consecvent, că nu ni se cere să setăm un adevărat și, de asemenea, un bar adevărat, pentru că atunci asta nu ar fi posibil. Dar a și a bara nu sunt conectate, așa că este... nu vom încerca niciodată să setăm atât a cât și bara adevărate. Dacă vom încerca să stabilim un adevărat, nu vom încerca niciodată să stabilim o bară adevărată, pentru că acestea nu sunt... a și o bară nu pot fi în aceeași clică. Nu sunt conectați unul cu celălalt. BINE? Deci acesta este argumentul. Și, în sfârșit, susțin -- nu ne vom uita la asta în detaliu -- că este oarecum evident că această reducere poate fi făcută în timp polinomial. Și anume, dacă vă dau acea formulă, puteți scrie acel grafic în... destul de ușor. Nu este nicio muncă grea de făcut pentru a scrie acel grafic sau a număra numărul de clauze. Deci asta este dovada că pot reduce 3SAT la clică. Și vă mai spune că, dacă aș putea rezolva rapid clica, atunci pot rezolva rapid 3SAT. Și acesta este ideea, pentru că acum pot converti problemele de clic în probleme 3SAT. Nu imi pare rau. L-am primit invers -- converti problemele 3SAT în probleme de clic. Deci, dacă pot rezolva clic cu ușurință, atunci pot rezolva cu ușurință 3SAT. Tocmai am arătat o modalitate de a converti aceste formule în grafice. Deci, dacă pot rezolva cu ușurință graficele, atunci pot rezolva cu ușurință formulele. OK, de ce nu ne întoarcem la cineva... oh, întrebare, check-in. Dar acum putem și... Voi lansa un check-in, dar vom... Hai să vedem. Văd multe, multe întrebări aici, care sunt de fapt despre ce este vorba despre check-in-ul meu. Vă voi întoarce înapoi, băieți. OK, deci unde am folosit faptul că avem trei literale pe propoziție? Funcționează acest lucru chiar dacă am avea orice număr de literali per clauză? Ce crezi? Avem o cursă strânsă aici. Adevărul pierde, din păcate. În regulă. Oh, este foarte aproape, dar totuși... OK. Încă unul... Bine, e gât și gât. OK, aproape gata-- 10 secunde-- am terminat aici? OK, asta este... terminând sondajul. Da, adevărul a câștigat. Slavă domnului. Da, funcționează pentru orice clauză de dimensiune. Nu am folosit faptul că este un 3CNF. Ar fi putut fi orice număr aici. Ei bine, avem o... Cred că aici este o pluralitate , totuși, nu o majoritate. Unde am folosit 3 în oricare dintre aceste argumente? Nu am pomenit. Poate v-ați imaginat că va face parte din asta, dar 3 nu intră deloc în această discuție. Dacă vă gândiți cum este - de ce funcționează, chiar dacă am avut -- una dintre aceste clauze avea 10 literale în ea, atâta timp cât k este numărul de clauze și nu conectăm nicio variabilă - niciun literal intern unei clauze, tot acest argument va funcționa în continuare. Așa că vă rugăm să verificați marca. Sigur că înțelegeți ce se întâmplă, pentru că văd că o bună parte dintre voi nu ați înțeles bine. Deci am o întrebare bună aici. Dacă ar fi doar o singură clauză mare, deci este ca și cum întreaga formulă ar fi doar un SAU mare. Deci, ce se întâmplă în acest caz? Bună întrebare-- deci în acest caz-- să presupunem că există o clauză mare cu 100 de literale. Asta-i toată formula. Este doar un SAU mare. Deci știm că formula va fi satisfăcătoare, apropo, evident. Deci, dacă te uiți la G-ul corespunzător, va avea 100 de noduri, pentru că există unul pentru fiecare literal. Niciuna dintre ele nu va fi conectată între ele, pentru că toate sunt în aceeași clauză. Deci, se pare că vom fi într-o formă grea încercând să găsim o clică acolo, pentru că nu există margini deloc. Totul este interzis. Dar ce este k? k va fi 1 în acest caz, pentru că există o singură clauză. Și un fel de caz degenerat, dar o clică cu un singur nod - doar un singur nod este - contează ca o clică, pentru că este doar un nod. Nu este deloc nevoie de margini. Încă contează ca o clică. Deci tot va merge. Să vedem. Ce altceva aici? A fost o întrebare amuzantă pe care mi-ai pus-o. Mulțumesc. Sunt o mulțime de întrebări. Cred că suntem de fapt destul de aproape de pauză. Vom vedea. Da. Oh, multe, multe întrebări aici, așa că cred că voi începe să treacă ceasul pentru pauza noastră de cafea și voi răspunde la câteva dintre aceste întrebări. Voi încerca să răspund la unele dintre aceste întrebări-- hopa-- încerc să răspund la unele dintre aceste întrebări după aceea. În regulă. Bine... în regulă. Așa că am o întrebare despre a mă asigura de ce nodurile nu au etichete inconsistente, dacă înțeleg corect întrebarea. Așa că nu am pus niciodată margini între noduri cu etichete inconsistente. Asta e regula. Asta e construcția mea. Pot să spun cum funcționează construcția. Deci acele două noduri cu etichete inconsecvente nu pot fi niciodată în aceeași clică, pentru că nu există nicio margine între ele. Deci nu sunt sigur că a răspuns la întrebarea de acolo, dar asta a fost... să vedem. Deci primim o altă întrebare aici. Deoarece orice formulă booleană poate fi convertită în CNF, înseamnă asta -- timpul polinomului SAT poate fi redus la clică ca w-- [ INAUDIBIL] timpul redus la clică, dar nu pentru motivul că orice formulă booleană poate fi convertită în CNF, deoarece acea conversie va fi o conversie exponențială în general - conversia în CNF. Așa că trebuie să fii atent la ceea ce înțelegem prin conversia unei formule în CNF. Așa că primesc și o întrebare -- ce se întâmplă în cazul 1SAT? Ei bine, nu prea am vorbit despre 1SAT. Deci întrebarea este, să presupunem că există doar un singur literal per clauză. Este un interesant... un alt tip de caz marginal aici. Ce se întâmplă în aceste circumstanțe? Deci, există doar un singur literal per propoziție. Deci trebuie să vă dați seama ce se întâmplă. Dar, în acest caz, toate clauzele au doar un literal în ele, iar acum au -- când aveți un 1CNF, deci există doar unul literal per clauză, singura modalitate prin care poate fi satisfăcătoare este să faceți fiecare literal adevărat. , pentru că nu mai există ORing. Deci fiecare literal trebuie să fie adevărat în sarcină. Deci, asta înseamnă că nu poți avea niciodată literalmente consistente. Și acesta este singurul caz în care nu ai avea un avantaj, pentru că nu ești-- condiția interzisă nu se va întâmpla pentru că nu ai mai mult de un nod pe clauză. Fiecare clauză va avea doar un singur nod în ea. Deci, se rezumă într-adevăr dacă aveți sau nu clauze inconsecvente etichetate. Nu am explicat foarte bine, dar e... argumentul încă funcționează, totuși. Ar trebui să verificați singur. Deci aceasta este o întrebare de bază. Cum vedem că F este timpul polinomial? Nu sunt sigur că vreau să petrec multe discuții despre asta. Conversia din formulă în grafic este un fel de unu-la-unu - fiecare literal devine un nod. Regula pentru când marginile sunt prezente -- este o regulă foarte simplă. Nu sunt sigur ce să mai spun. Pare destul de clar că conversia - acea reducere este calculabilă în timp polinomial. Dacă ai scrie un program pentru a face asta, ar funcționa foarte repede. Este posibil ca G să aibă o clică k plus n, unde n este mai mare decât 0? Conteaza? Dacă vă gândiți bine, cea mai mare clică posibilă pe care o poate avea acest grafic G este k. Nu ar putea avea niciodată mai mult decât o clică mai mare, deoarece două noduri din aceeași clauză nu sunt niciodată conectate. Ai doar k clauze. Deci răspunsul este nu, nu poți avea o-- mai mare decât o clică k-- pur și simplu să nu se întâmple. Fiecare clauză trebuie să aibă același număr de literale? Nu văd de ce. Deci întrebarea este, de ce ne facem griji pentru 3SAT, deoarece nu părea să conteze aici? Există și alte exemple în care contează. De fapt, nu sunt sigur dacă vom vedea unul sau nu, dar există cazuri în care contează. Lasă-mă să văd dacă există întrebări rapide aici. Cineva spune, nu... trebuie să ne îngrijorăm că există un număr polinom de literali? Așa că trebuie să te gândești la ce înseamnă această întrebare. Mărimea intrării, care include toate literalele, este n. Deci vor fi, cel mult, n literali, pentru că aceasta este dimensiunea intrării, cel mult, în literale care apar. Deci nu trebuie să vă faceți griji că acesta este polinom, pentru că... apropo, definim dimensiunea intrării va fi, cel mult, n literale. Sper că este clar. BINE. OK, deci aceasta este o întrebare bună. Când vorbim despre timp polinomial, este polinom în reprezentarea intrării, care este... dacă vrei să te gândești la asta în termeni de biți, e bine... sau orice altceva. Nu va conta dacă folosiți un alfabet mai mare. Dar numărul de simboluri de care aveți nevoie în alfabetul de dimensiune fixă , numărul de simboluri de care aveți nevoie pentru a nota acea intrare în orice codificare rezonabilă va fi n. Și va fi polinom în n, polinom în acea lungime a intrării. Deci, o altă întrebare este, SAT reduce 3SAT? Da. Asta vom vedea. SAT de fapt reduce timpul polinomial la 3SAT. Nu prin conversia la o formulă echivalentă, ci printr-un argument mai mult... ceva mai implicat decât atât. OK, de ce nu mergem mai departe? Unele dintre acestea vor apărea oricum în cadrul prelegerii. OK, deci acum să vorbim despre completitudinea NP, pentru că am cam pus lucrurile la punct. Nu vom demonstra că teorema de bază, teorema Cook-Levin despre completitudinea NP, dar cel puțin vom putea face definiția. OK, iată definiția noastră a ceea ce înseamnă ca o problemă să fie NP completă. Deci un limbaj B se numește NP complet dacă are două proprietăți. Numărul unu este că trebuie să fie membru al NP, iar numărul doi -- fiecare limbă din NP are timpul polinomial redus la acea limbă -- la acel limbaj NP complet pentru ca acesta să fie NP complet. O imagine atât de simplă-- trebuie să fie în NP și tot ceea ce un NP reduce la ea. Și asta este un fel de proprietate magică pe care noi pretindem că o are SAT. sat, în primul rând, este evident în NP. Și, după cum arată teorema Cook-Levin, sau va arăta, totul în NP este reductibil la SAT, așa că SAT va fi primul nostru exemplu de problemă completă NP. Și vom obține ceea ce am susținut și pentru SAT - că, dacă SAT sau orice altă problemă completă NP se dovedește a fi rezolvabilă în timp polinomial, atunci fiecare problemă NP este rezolvabilă în timp polinomial. Și asta este imediat, pentru că totul este reductibil în timp polinomial la problema NP completă. Deci, dacă o poți face cu ușurință, poți face totul cu ușurință doar trecând prin reducere. BINE. Deci, teorema Cook-Levin , așa cum am menționat, este că SAT este NP complet. Și o vom demonstra de fapt în următoarea prelegere, dar să presupunem pentru restul acestei prelegeri că știm că este adevărat. Așa că voi folosi terminologia problemelor fiind NP complet, presupunând că știm-- că avem SAT ca NP complet. BINE? Așa că vom folosi unele dintre lucrurile pe care le vom demonstra următoarea prelegere doar în terminologia pe care o vom vorbi astăzi. OK, deci iată poza. Iată clasa NP. Și totul în NP este timp polinomial reductibil la SAT. SAT însuși este membru al NP, dar nu am vrut să o arăt așa, deoarece face ca imaginea să fie cam greu de afișat. Deci, doar din perspectiva reducerii, totul în NP este timp polinomial reductibil la SAT. Vom arăta următoarea prelegere. Un alt lucru pe care îl vom arăta următoarea prelegere este că SAT, la rândul său, este timpul polinomial reductibil la 3SAT. Deci 3SAT, după cum vă amintiți, sunt doar acele probleme care sunt în conjuncție - sunt în 3CNF. Și apoi ceea ce arătăm astăzi este că 3SAT este timpul polinomial reductibil la clică. Deci, acum, luând ipoteza că SAT este NP complet - deci totul este timp polinomial, reduceți atât SAT, care este, la rândul său, timpul polinom reductibil la 3SAT și, la rândul său, reductibil la clică. Aceste reduceri, după cum am văzut înainte, au compus. Puteți aplica doar o funcție de reducere după alta. Dacă fiecare în parte este polinom, totul ca o combinație va fi polinom. Așa că acum știm că 3SAT va fi și NP complet, pentru că putem reduce orice din NP la SAT și apoi la 3SAT, și apoi obținem o reducere direct la 3SAT prin compunerea acestor două reduceri - și apoi, în plus, la clică. Deci acum avem... mai multe probleme complete NP. Și trecând dincolo de asta, avem problema HAMPATH, despre care vom vorbi în continuare. Și vom arăta o altă reducere în plus față de cea pe care tocmai am arătat-o ​​clicei, acum una care trece de la 3SAT la HAMPATH. BINE. Deci, în general, cred că mesajul de luat este că, pentru a arăta că un limbaj este NP complet, doriți să arătați că 3SAT este timp polinomial reductibil la el. Bine, vin câteva întrebări bune... Voi încerca să răspund la acestea. Deci vei lua 3SAT și vei reduce la C. Acesta este cel mai tipic caz. Vor fi și alte exemple, s- ar putea să începem cu o altă problemă despre care ați arătat deja că este în NP completă și să o reducem la limba dvs. Deci, nu trebuie să înceapă cu 3SAT, deși de multe ori așa face. De ce este important acest concept? Asa ca as spune ca sunt doua motive. Și acest lucru va ajunge puțin la unele dintre întrebările de chat. În primul rând, dacă te confrunți cu o nouă problemă de calcul -- ai o problemă de robotică pe care vrei să o rezolvi în teza ta și ai nevoie de un algoritm care să știe dacă brațul robotului poate face așa ceva -- mișcă-te într-un într-un astfel de mod și implică căutarea-- posibil căutarea printr- un spațiu de diferite tipuri de mișcări și vrei să știi-- Aș dori să găsesc un algoritm polinom pentru a rezolva problema. Folosesc asta ca exemplu pentru că acest lucru i s-a întâmplat de fapt unuia dintre foștii elevi din această clasă, care lucra în robotică, și de fapt ajung să demonstreze că problema pe care încercau să o rezolve este NP completă. Așadar, acestea sunt informații utile, pentru că, deși știind că o problemă este NP completă, nu garantează că nu este în P -- pentru că, probabil, P este egal cu NP -- ceea ce vă spune -- dacă aveți o problemă care este NP completă și este se dovedește a fi în P, atunci P este egal cu NP. Deci ar exista consecințe uimitoare și surprinzătoare ale problemei tale, dacă s-ar ști că este NP completă, ajungând în P. Deci, în general, oamenii consideră o dovadă a completității NP ca o dovadă puternică că problema nu este în P. Chiar dacă nu este o dovadă destul de mare, este o dovadă puternică că nu este în P. Și așa că ați putea la fel de bine să renunțați la încercarea de a găsi un algoritm polinomial pentru el, pentru că dacă o faceți, nu trebuie să vă mai faceți griji pentru robotică. Vei deveni celebru ca un Așa că nu mi-aș face griji cu privire la-- așa că dacă arunci NP-ul problemei complet, poți presupune aproape că-- aproape sigur că nu în P. Acum, există un alt motiv legat de-- pentru teoreticienilor să fie -- le pasă de completitudinea NP, și adică, dacă încercați să demonstrați că P este diferit de NP -- sau P este egal cu NP, deoarece una dintre întrebările de chat se ridică -- pentru a demonstra că P este diferit de NP , cea mai probabilă abordare este să alegi câteva [? pre ?] problemă în NP și arată că nu este în P. Asta ar însemna pentru ei să fie diferiți. Veți alege o problemă NP și veți arăta că nu este o problemă P. Ei bine, un lucru ar fi groaznic este posibil, P este diferit de NP și alegeți problema greșită. Să presupunem că mi-am petrecut tot timpul încercând să arăt-- cu 20 de ani în urmă, muncesc foarte mult încercând să arăt că compozitele nu sunt în P, adică ar fi fost perfect rezonabil, deoarece compozitele este un NP , și nu se știa să fie în P acum 20 de ani. Și apoi am investit tone de efort pentru a încerca să demonstrez -- pentru că îmi place teoria numerelor sau Dumnezeu știe ce -- pentru a demonstra că compozitele nu sunt în P. Și apoi, se pare, compozitele erau în P. A fost problema greșită să alege, chiar dacă P ar putea fi diferit de NP. Dar ceea ce garantează NP complete este că, dacă lucrați la o problemă, care este NP complet, nu puteți alege problema greșită, deoarece dacă orice problemă este în NP și nu în P, o problemă NP completă va fi fii un exemplu în acest sens, deoarece dacă NP probleme complete în P, totul în NP este în P. Deci, dacă NP este diferit de P, știi că problemele complete nu sunt în P, așa că ai putea la fel de bine să lucrezi la una dintre acestea. Deci, acestea sunt două moduri în care completitatea NP sa dovedit a fi - este un concept important. OK, deci iată un check-in. Voi, băieți, începeți... poate începeți să gândiți așa cum gândesc eu. Primești... unii... cel puțin unul dintre voi a pus această întrebare în chat. Ce limbă pe care am văzut-o probabil este cel mai analogă cu SAT-- ATM, ETM sau 0 cu k, 1 cu k? Evident, acest lucru este poate subiectiv. Este posibil să aveți propria interpretare a ceea ce înseamnă asta. Într-un fel, poate că nu există un răspuns corect, dar ce crezi? OK, asta e. Nu știu cum în lume ai putea vedea această problemă ca fiind analogă cu 0 cu k, 1 cu k, dar OK. Sunt sigur că ai motivul tău. Da, seamănă mult cu ATM-ul. De ce? Ei bine, pentru că, în primul rând, am arătat într-o problemă cu temele pentru acasă că toate limbile Turing recunoscute sunt reductibile la ATM - maparea reductibilă la ATM. Deci este puțin ca noțiunea de completitudine pe care o avem pentru satisfacție, deoarece toate problemele NP vor fi reductibile la SAT. Și celălalt lucru este că, odată ce începem... vrem să arătăm că alte probleme sunt indecidabile, am redus ATM-ul la ele. Și asta seamănă foarte mult. Vom reduce SAT sau 3SAT-- deci este indirect de la SAT-- la alte probleme pentru a arăta că NP nu ar trebui să fie complet, astfel încât să fie greu-- că sunt greu, într-un sens. Și astfel, în ambele moduri, ATM și SAT joacă roluri similare. O diferență cheie, totuși, între ATM și SAT este că pentru ATM, putem dovedi că este indecidibil, dar pentru SAT, nu știm cum să dovedim că este în afara lui P. Acestea ar fi situațiile analoge. Și astfel povestea pentru SAT, care este ușor de rezolvat printr-un argument de diagonalizare pentru ATM-- există motive să credem-- că vom vedea mai târziu-- că diagonalizarea nu va funcționa pentru a dovedi SAT în afara P. Și în plus , nu prea avem metode bune. Deci oricum, hai să mergem mai departe. De ce ETM este mai puțin analog? Pentru că ATM-ul a fost prima problemă pe care am arătat-o ​​indecidabilă, iar SAT este prima problemă pe care o vom arăta NP completă. Bănuiesc că acesta ar fi răspunsul meu. OK, hai să continuăm. Deci, să arătăm acum că HAMPATH este NP complet, presupunând că știm că SAT sau 3SAT este NP complet. Deci vom acorda o reducere de la 3SAT la HAMPATH. Despre asta este vorba. Este exact ca ceea ce am făcut pentru clica, dar acum pentru HAMPATH. Și asta va fi foarte tipic. În aceste reduceri, de obicei, ceea ce se întâmplă este că încercați să simulați o formulă -- o formulă booleană pentru satisfacție -- din perspectiva satisfacției. Încercați să simulați acea formulă cu un fel de structuri în limbajul țintă, care ar fi HAMPATH. Lingoul pe care oamenii îl folosesc este că veți construi gadgeturi pentru a simula structurile din formulă - și anume, variabilele, literalele și clauzele. OK, acestea vor fi substructuri ale graficului, în acest caz, pe care îl construiți. Vom vedea ce înseamnă asta. Deci, să luăm o formulă aici și să încercăm, din nou, să ne imaginăm cum am reduce asta la problema HAMPATH. Deci reducerea ar produce un grafic - nu, ar produce o instanță HAMPATH - deci un G, s și t. Vrei să știi, există o cale hamiltoniană de la s la t în grafic? Și acesta nu va fi întregul grafic, dar acesta va fi o substructură în acel grafic. Următorul diapozitiv va avea structura globală a graficului. Dar aici, acesta va fi un element cheie și îl vom numi gadget variabil. OK, cum arată? Nu știu dacă îl poți vedea pe... destul de clar, dar aceste margini... deci sunt patru noduri exterioare aici. Marginile care le leagă sunt toate cam îndreptate în jos. Și apoi au fost aceste noduri orizontale aici și există margini care le conectează atât la stânga la dreapta, cât și la stânga. Există un rând de aceste noduri orizontale. OK, deci ai o imagine despre cum arată asta? Trebuie să te uiți cu atenție pentru a vedea vârfurile de săgeți. Poate ar fi trebuit să le fac un pic mai mari. Hopa-- deci acum, dacă încercăm să trecem de la acest nod la acel nod-- imaginați-vă că acum încercați să construiți o cale hamiltoniană, pentru că aceasta va fi o parte din acel grafic G pe care îl construiesc . Acum, amintiți-vă, pentru ei... pentru a exista un graf hamiltonian, asta înseamnă că trebuie să treceți prin fiecare nod din grafic. Deci, dacă vreau să ajung de la s la t, singurul mod în care voi putea să merg-- să lovesc aceste noduri orizontale aici este prin a le ridica pe măsură ce merg de la s la t. Deci singura posibilitate este... dacă te gândești bine, este... ar fi ca secvența să meargă așa, dacă poți... dacă asta ți se întâmplă. Deci calea ar merge de la s la acest nod, apoi prin aceste hopuri de-- de-a lungul acestor noduri orizontale, și apoi în jos până la nodul de jos aici. Deci, acesta este o modalitate prin care poți să ajungi de aici în jos până acolo și să ridici toate celelalte noduri de-a lungul drumului, adică -- nu vor avea nicio altă posibilitate -- căi posibile de a ajunge la ele. Așa că o să numesc asta zig-zag. BINE? Dar există o altă modalitate de a ajunge de la s la nodul de jos, care va fi făcând un fel de dual-- mergând la dreapta, apoi ieșind la stânga și apoi în jos. Voi numi asta zig-zig-- și cu o mică diagramă aici doar pentru a rezuma ce înseamnă. Și acesta este lucrul clasic pentru un gadget variabil, deoarece este o structură care atunci când încerci să te gândești la modul în care obiectul pe care îl întrebi dacă există sau nu - calea hamiltoniană - cum se raportează la acel obiect. , va avea două posibilități, care vor corespunde variabilei care este setată adevărată sau falsă în formulă. Așa că arătăm cum să setăm -- simulăm variabila în această instanță HAMPATH. Deci, setarea variabilei va corespunde construcției căii. BINE? Acum, trebuie să ne asigurăm nu numai că variabila este setată la adevărat sau fals, ci și că primește un set de adevărat și fals într-un mod care face din aceasta o sarcină satisfăcătoare - și anume, că obținem un literal adevărat în fiecare clauză. Așa că voi adăuga un alt gadget aici numit gadget cu clauză, care este doar un singur nod. Și vizitarea acelui nod aici va corespunde cu satisfacerea acelei clauze, cu un literal adevărat în acea clauză. Voi avea [? activat?] un ocol de la aceste noduri orizontale către acest gadget cu clauză. Deci aici este. Iată acel ocol. Pe măsură ce merg de la stânga la dreapta, pot-- în loc să fac un singur salt aici, aș putea să mă ramific și să vizitez acel nod clauză, apoi să mă întorc și să-mi iau calea de la stânga la dreapta , așa cum făceam inainte de. Sper că vedeți imaginea de ansamblu, pentru că aceasta trebuie să fie o cale hamiltoniană. Trebuie să lovească fiecare nod. Asta e una dintre cerințe. Acesta va fi unul dintre nodurile din graficul meu. Calea trebuie să lovească acel nod. Singurul mod în care va putea atinge acel nod este luând un ocol de pe această cale orizontală aici. Dar observă-- și asta este cheia-- dacă fac un zig-zag, atunci pot face o ocolire și pot vizita acel gadget de clauză-- acel nod de clauză. Dar dacă fac un zag-zig, modul în care este structurat acest ocol nu îmi permite să vizitez acel nod, pentru că dacă merg de la dreapta stânga aici, până ajung la această margine de ieșire-- acum Vreau să mă întorc... acea notă a fost deja luată. Funcționează doar dacă merg în zag-zig, dacă merg de la dreapta la stânga-- de la stânga la dreapta. Dacă merg de la stânga la dreapta, atunci o pot face, dar dacă merg de la dreapta la stânga, nu. Dacă vă gândiți la stânga-- direcția de la stânga la dreapta ca fiind adevărată, aceasta va corespunde cu acea variabilă care apare în sens pozitiv în acea clauză, dar nu în sens negativ. Calea negativă-- aș inversa înăuntru și ieși din ocol, aș întoarce asta, așa că acum aș putea face ocolul doar când merg de la dreapta la stânga, în loc de la stânga la dreapta. Sper să înțelegi poza. Așa funcționează structura. Acum, ceea ce îmi mai rămâne de făcut este să le adun pe toate. Dar acest slide conține curajul a ceea ce se întâmplă. Există vreo întrebare la care pot să vă răspund despre asta? Să trecem la următorul diapozitiv și apoi, pe măsură ce apar întrebări, le poți introduce și poate vom răspunde acolo. OK, deci iată imaginea de ansamblu. Așa că imaginați-vă că avem acea formulă pe care o începem -- o reducem. Și să presupunem că are m variabile și k clauze. O să le numesc clauza c1, c2, până la ck - aici, variabilele m apar fie pozitiv, fie negate în acea formulă. Și așa va arăta structura globală a lui G. Acum, primesc o întrebare aici. Ce au acele noduri orizontale -- ce rol joacă ele? Acele noduri sunt acolo pentru a- mi permite să vizitez acele noduri de clauză, nodurile care reprezintă gadgeturile de clauză, pe care le voi plasa aici. Acesta este aproape un întreg G. Îmi lipsesc doar câteva muchii, dar acestea sunt toate nodurile lui G. Așa că nu uitați, încerc să aflu, există o cale hamiltoniană de la s la t? Acum, dacă nu ar trebui să-mi fac griji pentru aceste noduri, răspunsul ar fi doar da. De fapt, ar exista multe căi hamiltoniene de la s la t, pentru că pot face un zig-zag sau un zig-zag prin fiecare dintre aceste gadget-uri variabile și asta m-ar duce de la s la t și mi-ar fi bine. . Sunt doar nodurile c, aceste noduri... aceste noduri ci... Trebuie să le lovesc și eu. Așa că vor fi... vizitarea lor va fi activată prin ocoliri de aici. Așa că lasă-mă să încerc să- ți arăt cum arată. Așa că am să măresc bucăți mici de la aceste gadget-uri și vă voi arăta cum sunt conectați acești tipi. Deci, iată gadgetul x1. Deci x1 apare pozitiv în c1. Iată x1 și c1. Și asta înseamnă că, când voi merge de la stânga la dreapta, voi fi o posibilitate de a vizita c1. Dar acum, să vedem ce se întâmplă cu... care a fost următorul pe care l-am avut aici? BINE. Dreapta. Deci următorul este... oh, da. Deci x1 apare pozitiv în c1. De aceea am o astfel de conexiune. Acum, x1 apare negat în c2, așa că vreau doar să fac-- să permit ocolului să viziteze c2 când merg la stânga, spre deosebire de stânga la dreapta. Deci acest set de noduri orizontale îmi va permite doar să fac o ocolire fie la c1, fie la c2, dar nu la ambele, deoarece calea hamiltoniană va merge fie la stânga, fie la dreapta, fie la stânga. Nu le poate face pe amândouă, când trece prin gadgetul x1. Trebuie să... [INAUDIBIL] Voi încerca să te ajut, dar trebuie să încerci să te gândești de ce funcționează. Să gândim împreună. Deci x2 apare și în c1, dar acum apare negat. Așa că voi avea margini de la acest gadget x2-- hopa-- gadget-ul x2, dar acum uită-te la... uită-te la cum am aranjat acel ocol. Pot pleca pe partea stângă spre stânga și mă pot întoarce pe partea dreaptă, ceea ce înseamnă că pot face acel ocol doar când merg la stânga. Și asta pentru că x2 este negat în c1. Poate că sunt multe aici, dacă nu înțelegi prea bine, dar ideea este, să zicem, să încerci să demonstrezi rapid... deci asta e toată construcția. Faceți asta pentru fiecare apariție a literalului dintr-o clauză. Veți adăuga aceste ocoluri, care vă permit, eventual, să vizitați clauza. Deci direcția înainte este... de ce este adevărat? Deci, luați orice sarcină satisfăcătoare, așa cum am sugerat, faceți zig-zag-uri sau zag-zig-uri corespunzătoare prin gadgeturile variabile de la s la t, apoi faceți ocolurile pentru a vizita nodurile clauzei. Direcția inversă este de fapt puțin mai complicată. Nu vom avea timp să trecem prin subtilitatea ei, dar ceea ce doriți să vă asigurați aici este că nu aveți o cale ciudată, pentru că acum voi începe cu o cale hamiltoniană și voi construi O însărcinare. Și vrem să ne asigurăm că calea pe care o construiesc nu merge de la unul-- de la aceste noduri orizontale la un nod închis și apoi înapoi la nodurile orizontale ale altcuiva și este un fel de amestec de lucruri care nu Nu are niciun sens să încerci să reconstruiești o misiune satisfăcătoare. Ceea ce vrei cu adevărat să se întâmple este că calea hamiltoniană ar trebui să aibă zig-zag și zag-zig-uri clare care să îți permită să decizi cum să setezi variabilele. Și deci acesta este rolul acestor mici noduri aici. Acestea sunt distanțiere care separă ocolurile unul de celălalt și care forțează o vizită la nodul clauzei să revină în același loc din care a plecat. Altfel, nu ați putea niciodată să vizitați acele noduri de distanță. Trebuie să cauți asta în carte, dar există un mic detaliu prin care trebuie să treci. Trebuie să arătați că trebuie să fie zig-zag și zag-zig, apoi obțineți atribuirea corespunzătoare de adevăr și trebuie să satisfacă phi pentru toate căile. BINE. Din nou, reducerea este calculabilă în timp polinomial. Nu am de gând să spun mai multe despre asta. Avem puțin timp. Ultima check-in-- ar mai funcționa această construcție dacă G ar fi nedirecționat? Să presupunem că am eliminat toate direcțiile de pe margini, le-am făcut linii, în loc de săgeți. Ar arăta asta acum că problema drumului hamiltonian nedirecționat este NP completă? Staţi să văd. OK, ce reprezintă nodurile c aici? Există un nod c pentru fiecare clauză. Deci există k clauze numite c1 la ck și există k c noduri. Acestea sunt așa-numitele gadgeturi cu clauze, care vor forța să existe un literal adevărat în fiecare clauză pentru misiunea satisfăcătoare. Trebuie să te uiți la asta, sau poate putem petrece puțin mai mult timp explicându-l, dar acesta este scopul. Asta înseamnă că avem nevoie doar de două noduri în interior? Deci nodurile orizontale... avem nevoie doar de două dintre ele? Nu veți putea reutiliza aceste noduri pentru mai multe ocoliri. În primul rând, odată ce ați mers la un ocol, vă întoarceți la nodul următor și, deci, mai bine nu suprapuneți mai multe ocoluri. Și, de asemenea, trebuie să le păstrați separați unul de celălalt. Nu uitați, acest nod x1 poate apărea în multe, multe clauze diferite, așa că ar trebui să aveți posibil multe dintre aceste noduri orizontale. Deci cineva spune acum că 2k în interiorul nodurilor ar fi suficiente. Probabil 2k-- aș spune 3k, doar pentru a fi în siguranță pentru nodurile distanțiere. Trebuie să priviți cu atenție argumentul, care este prezentat în manual. Este posibil să nu aveți nevoie de nodurile de distanță, dar apoi face argumentul mai urât. Deci, modul în care se face construcția este că aveți 3k în interiorul nodurilor. BINE. Din nou, mai multe întrebări de genul - graficul ar începe să arate dezordonat dacă x9 ar fi în c1. Da, dacă x9 aici era în c1? Da, ar fi dezordonat. E bine. Dezordonat este permis. Bine, cred că suntem... hai să încheiem sondajul. Sunteți cu toții? În regulă, împărtășește rezultatele. Da. Răspunsul este nu. Construcția depinde de această direcție. Puteți vedea asta peste tot , dar, pentru un lucru, scopul acestor ocoliri îl reprezintă direcțiile marginilor. Și deci fără asta, această construcție va fi doar o grămadă de... nu va însemna nimic. Nu va dovedi nimic. Probabil că întotdeauna va fi... să aibă o cale hamiltoniană fără indicații. Așa că cred că nu avem timp. O revizuire rapidă - acestea sunt subiectele pe care le-am abordat. Cred că nu avem timp, așa că ar trebui să te las să pleci. Dar voi rămâne câteva minute, în cazul în care vreunul dintre voi are întrebări. Dar trebuie să fug eu la 4:00 pentru o altă întâlnire, așa că nu am prea mult timp. Clarificați comentariul meu despre alegerea problemei greșite pentru a aborda P versus NP, când am folosit compozite ca exemplu - dacă aș munci din greu pentru a dovedi că compozitele nu sunt în P ca o modalitate de a demonstra că există un limbaj NP care nu este în P. P, ar fi fost o greșeală, pentru că compozitele este în P. Aș fi muncit din greu pentru a dovedi ceva despre care acum știm că este fals. Deci nu vrem să petrecem timp lucrând pe limba greșită. Dar lucrul frumos despre limbajele NP complete este că avem garanția că, dacă P este diferit de NP, că acel limbaj nu este în P. Există probleme care nu sunt în P care sunt în NP, dar nu sunt NP complete? Oh, asta e o întrebare bună. Există probleme între P și NP complete? Deci NP complete este un fel ca cele mai grele probleme din NP, iar problemele P sunt, evident, problemele ușoare care sunt în NP. Este totul fie NP complet, fie în P? Deci, în primul rând, există probleme despre care se știe că nu sunt în nicio categorie. Așa că vom discuta câteva dintre acestea la timp, dar una dintre ele este problema izomorfismului grafic, testând două grafice -- dacă sunt într- adevăr doar permutări unul celuilalt. Este clar o problemă în NP, dar nu se știe că este în P. Deci există probleme despre care se știe că nu sunt nici NP complet, nici în P, deci există probleme care ar putea fi între ele. Dar apoi a existat o altă teoremă , care spune că, dacă presupuneți că P este diferit de NP, atunci puteți construi probleme care sunt între, care nu sunt nici NP complete, nici în P. Sunt NP, probleme dar ele 'nu sunt NP complet, nu în P. Deci acele probleme în sine sunt poate oarecum artificiale, dar ele măcar dovedesc faptul că este posibil să avem aceste probleme intermediare. Oh, deci cineva întreabă, nu este factorizarea. Nu [? cunoscut--?] pentru cazul factorizării-- sau trebuie să faci un limbaj din asta, apropo. Dar este pentru că factorizarea este o funcție, așa că nu vom dori să vorbim despre limbi. După cum sugerează temele, NP și P sunt clase de limbi străine, dar OK, aceasta este o notă separată acolo. Factorizarea nu este cunoscută. Factorizarea ar putea fi în P și ar putea fi NP completă. Ambele nu sunt excluse. Deci, cred că majoritatea oamenilor s-ar aventura probabil să ghicească că este o problemă care se află în starea intermediară, care nu este nici P, nici NP completă, dar nu este cunoscută. Cine s-a gândit prima dată la această reducere de la 3SAT la HAMPATH? Este atât de inteligent. Ei bine, nu am fost eu. Cred că asta se datorează lui Dick Karp, care a fost unul dintre profesorii mei la Berkeley, unde eram student absolvent. Asta s-a făcut înainte să ajung acolo. Era în jurul anului 1971 când... deci erau două ziare celebre. Acolo este ziarul Cook. Mai este și ziarul Levin. Asta era în rusă. Asta a durat ceva timp pentru ca oamenii să descopere aici, în Occident. Dar lucrarea lui Cook a fost din 1971 și a urmat foarte repede după-- el doar a arătat că SAT este NP complet, dar după aceea, Karp a fost-- a avut o lucrare numită „Reductibilitate printre problemele combinatorii” și avea o listă de aproximativ 20. problemele despre care a arătat că sunt NP complete - prin reducerea de la SAT - includ clica, includ HAMPATH și o grămadă de alte lucruri. Și asta a fost, de asemenea, o ziare foarte faimoasă. Ambele sunt -- oamenii vorbesc adesea despre Cook-Karp , deoarece, împreună, arată cu adevărat importanța completității NP și întreaga noțiune a completității NP. Da, 21 de probleme, deci... da, deci Karp a dovedit 21 când problemele au fost NP complete în 1972. Deci, la scurt timp după ce Cook a arătat că SAT era NP complet. De altfel, cred că terminologia NP complete nu a existat decât puțin mai târziu. Și asta ar fi fost... ar putea fi din cauza lui Knuth. Nu sunt sigur. Îmi amintesc că a făcut un sondaj mare de oameni despre care ar trebui să fie limbajul potrivit pentru termenul respectiv și cred că a venit cu el. Bine, mă duc , băieți. Mă bucur să vă văd pe toți... deci până joi... oh, până marți. Pa! Pa.