[SCRÂȘIT] [FOSȘIT] [CLIC] MICHAEL SIPSER: Bine, toată lumea. Sa incepem. Bine ai revenit. Mă bucur să vă văd pe toți aici pe Zoom. Așa că vom continua cu ceea ce am discutat săptămâna trecută, care a fost o introducere în NP-compleness. Așa că urmărim descrierea noastră a complexității timpului. Am început să vorbim despre clasele de complexitate a timpului, clasa P, clasele nedeterministe, clasa NP, problema P versus NP, și apoi am condus la această discuție despre NP-completitudine. Și astăzi vom demonstra marea teoremă în domeniu, care într-adevăr a făcut ca lucrurile să se întoarcă la începutul anilor 1970 de către Cook și Levin că a existat de fapt o problemă NP-complet, că SAT în special este un NP-complet. problemă. Și apoi vom vorbi și despre 3SAT, care este un instrument util. Doar ca să ne amintim, am avut această noțiune de NP-completitudine. Un limbaj este NP-complet dacă este în NP. Și orice altceva din NP este timp polinomial reductibil la acesta. Și dacă o problemă NP-completă se dovedește a avea o soluție de timp polinomială, atunci fiecare problemă NP are o soluție de timp polinomială. Și asta face parte din importanța NP-completitudinii, deoarece considerăm că este puțin probabil ca P să fie egal cu NP și că probabil există unele probleme care sunt NP, dar nu sunt rezolvabile în timp polinomial. Aceasta ar implica că o problemă NP-completă ar avea această proprietate. Și, așadar, a dovedi că o problemă este NP-completă este o dovadă, o dovadă foarte puternică, că nu are o soluție de timp polinomială. Și de aceea se numește insolubil. Este o problemă foarte dificilă. Deci, modul în care vom arăta de obicei problemele NP-complete este prin reducerea unei probleme NP-complete cunoscute anterior la acea problemă. Adesea este 3SAT, așa cum am văzut deja în mai multe exemple, sau ar putea fi un alt exemplu. Deci, să analizăm pe scurt lucrurile pe care le-am deja -- limbi pe care le-am văzut deja, care sunt NP-complete. Deci avem limbile SAT, care are o reducere directă de la fiecare problemă NP. Și așa vom arăta că astăzi, fiecare limbaj NP este reductibil în timp polinomial la SAT, care este, la rândul său, reductibil la 3SAT. Și am arătat anterior că 3SAT se poate reduce la CLIQUE și HAMPATH. Și în recitare, dacă ați trecut la asta, au arătat că problema SUBSET-SUM și problemele HAMPATH nedirecționate sunt, de asemenea, reductibile față de cele prezentate anterior - ei bine, fie de la 3SAT, fie în cazul problemei HAMPATH nedirecționate, este reducabilă de la problema HAMPATH. Și concluzia, odată ce avem aceste două reducbilități albastre afișate, atunci știm că toate aceste probleme sunt NP-complete. Deci clasa NP se descompune practic în probleme NP-complete , probleme P, probleme care sunt în P și apoi ar putea exista și probleme între ele. Deci, există unele probleme despre care se știe că nu sunt în nicio categorie. Și, de fapt, există o veche teoremă care arată că dacă P este diferit de NP, atunci există de fapt probleme care sunt în stare intermediară. Și, desigur, este posibil ca P să fie egal cu NP, iar apoi totul se prăbușește pentru a fi la fel, cu excepția minusculă a stelei sigma și a limbajelor set goale, care nu pot fi niciodată complete. BINE. Deci aceasta este recenzia noastră rapidă. Iată o înregistrare pe care o voi folosi pentru a ne pregăti pentru marea dovadă că vom petrece cea mai mare parte a prelegerii pentru a demonstra că SAT este NP-complet, dar doar pentru a defini o mică notație, pe care s- ar putea să-l ai... poate ai văzut deja. Dar o voi face sub forma unui check-in. Deci, sunt sigur că ați văzut cu toții notația de sumă mare folosind un sigma mare pentru a reprezenta o sumă peste un set de posibilități. Așa cum există notația mare sigma, avem... puteți avea alte operații care se aplică unui set de elemente. Deci, în acest caz, vom vedea finalul mare AND și operațiunea SAU mare -- va merge la -- notație, care ne va permite să vorbim despre luarea AND a multor lucruri sau SAU a multor lucruri. lucruri, pentru că vom construi aceste formule booleene. Și astfel AND-urile și OR-urile vor fi operațiunile pe care ne vom concentra. Și așa, doar ca exemplu, doar pentru a ne asigura că înțelegem cu toții această notație, dacă aveți două șiruri x și y scrise în termenii simbolurilor lor individuale. Deci ambele au lungimea n. Deci x este x1 la xn. Y este de la y1 la yn. Și acum scriu următoarea expresie. SI mare pentru i cuprins între 1 și n al lui xi egal cu yi. Dacă acel AND mare este adevărat, ce ne spune despre x și y? Și am să vă ofer doar două posibilități, că fie x și y sunt de acord cu un simbol sau sunt egali, și anume că sunt de acord cu fiecare simbol. Așa că haideți să o analizăm ca un sondaj rapid pentru a ne face să mergem aici. Vreau doar să mă asigur că înțelegeți notația, deoarece o vom folosi foarte mult pentru a descrie reducerea timpului polinomial de la limbile din NP la limbajul SAT. BINE. Cred că majoritatea dintre voi ați înțeles ideea. Deci hai să terminăm repede. Deci încă 15 secunde, vă rog, doar pentru a vă oferi șansa de a participa. BINE. Vom închide acest sondaj. Ultima șansă, ultimul apel. În regulă. Deci, da, SI mare - după cum majoritatea dintre voi puteți vedea, AND mare spune că x1 este egal cu y1 și x2 este egal cu y2 și x3 este egal cu y3, deci sunt toate - fiecare simbol din x este egal cu simbolul corespunzător în y. Dacă am avea un SAU mare în loc de un SI mare, atunci A ar fi răspunsul corect, pentru că atunci ar fi un loc unde ei sunt de acord în loc de fiecare loc în care sunt de acord. Deci, să începem să ne lansăm în această teoremă mare. Dovada în sine este o masă de detalii cu o idee subiacentă. Și de fapt, este o idee pe care am mai văzut-o. Dar haideți-- înainte de a trece înaintea noastră, să înțelegem ce încercăm să facem. Deci vrem să arătăm că acest limbaj SAT este NP-complet. Ne amintim ce este SAT. Formulele booleene sunt satisfăcătoare. Așadar, am arătat deja că problema SAT-- deci a fi NP-complet înseamnă că are aceste două caracteristici. Este în NP și totul în NP este reductibil la el. Deci, în primul rând, SAT este în NP, așa cum am văzut deja. Martorul care arată că formula este satisfăcătoare este pur și simplu sarcina satisfăcătoare care se evaluează la adevărat. Așa că acum vom alege un limbaj în NP, A și vom arăta că A este timp polinomial reductibil la SAT. Deci, acest lucru se va aplica oricărei limbi A din NP. Deci, să fie A un limbaj în NP. Este decis de o mașină Turing nedeterministă M în timpul n până la k. Asta înseamnă să fii NP. Voi ignora factorii constanți atunci când am putea duce asta pe tot parcursul dovezii. Ar face descrierea puțin mai greoaie și nu ar schimba niciuna dintre idei. Deci, să spunem doar că M rulează în timp n la k și recunoaște sau decide acest limbaj în A. Deci este o mașină nedeterministă. Deci trebuie să oferim o reducere a timpului polinomial de la A la SAT. Asta trebuie să- ți demonstrez. Deci, cum arată această reducere? Va mapa șiruri, care pot fi sau nu în A, cu formule, care pot fi sau nu satisfăcute. Asta trebuie să facă reducerea. Deci, spunând că mai formal, va lua un șir w și îl va mapa la o formulă pe care o vom numi phi sub M, w, unde M este mașina care decide că A și w este intrarea. Deci f va mapa w la această formulă, unde șirul este în limba exact când formula este satisfăcută. Și formula va depinde de M și w. De aceea doar are... este scris în acest fel. Așa că am mai văzut așa ceva. Deci, practic, treaba mea... avem această limbă A care este în NP. Și acum avem un șir w, care ar putea fi în A, sau poate nu este în A. Și trebuie să produc rapid în timp polinomial o formulă care va fi satisfăcătoare exact atunci când șirul w este în A. Deci, cum va merge formula aia? Cum pot produce o astfel de formulă? Ceea ce vreau să spun, desigur, nu știu dacă w este în A sau nu, pentru că eu sunt doar reducerea timpului polinomial. Și A este un limbaj NP. Deci, timpul polinomial probabil nu este suficient pentru a rezolva dacă w este în A. Așa că trebuie să fac acea mapare fără să știu răspunsul. Ideea este că-- și aici am mai văzut lucruri ca acestea înainte-- formula pe care o vom construi simulează mașina pe w. Deci, într-un fel, va face acea simulare. Trucul este să descoperi cum să... ce înseamnă asta. Dar interpretarea acelei formule este că într-un sens descrie, spune, în limbajul meu informal, că M acceptă w. Foarte asemănător -- există o mare paralelă aici între această construcție și, de exemplu, construcția, construcția PCP, în care am făcut o clipă -- având în vedere o mașină și o intrare, am făcut un set din acele piese de domino, unde găsim un meci te-a obligat să simulezi mașina. Aici găsirea unei sarcini satisfăcătoare vă va forța să simulați mașina. Deci, sarcina satisfăcătoare va fi un istoric de calcul pentru M pe w. Și voi scrie doar acea istorie a calculelor într-un mod anume. Deci, va avea o codificare oarecum diferită, care ne va ajuta să vizualizăm mai bine ce se întâmplă. Deci asta este abordarea. Aceasta este ideea de bază a ceea ce încercăm să-- ce vom face. Așa că mă bucur să aloc un minut dacă aveți întrebări despre această parte. Dar în caz contrar, voi trece doar să încep să fac construcția reală a cum arată formula. Cum se va face asta? Cum va funcționa formula? BINE. Deci fara intrebari. Să sperăm că suntem cu toții împreună. Deci, mai întâi de toate, permiteți-mi să descriu cum va arăta istoricul meu de calcul. Iar situația este puțin diferită de cea pe care o aveam înainte pentru că atunci când vorbeam despre problema corespondenței Postului aveam o mașină deterministă. Și acum mașina noastră este nedeterministă. Așa că vom numi obiectul -- în loc de un calcul de acceptare sau un istoric de calcul, vom doar să -- îl vom numi un tablou, sau uneori un tablou de acceptare dacă doriți să subliniați acceptarea naturii acesteia. Dar, în general, îl vom numi doar un tablou. Deci un tablou este într-adevăr o istorie de calcul acceptabilă pentru mașină pe o ramură de acceptare a calculului său nedeterminist . Deci, dacă M acceptă w, trebuie să aibă o ramură de acceptare, iar tabloul va fi secvența de configurații prin care mașina trece pe acea ramură de acceptare. Dacă există mai multe ramuri care acceptă, pot exista mai multe tablouri. Vor fi mai multe tablouri. Deci va exista un tablou pentru fiecare ramură de acceptare a calculului mașinii pe w. Dacă mașina nu acceptă w, nu vor exista tablouri. Și astfel, ideea este că vom face ca formula noastră să reprezinte afirmația că există un tablou. Și satisfacerea acestei formule va corespunde cu completarea simbolurilor din tablou pentru a-l face un tablou. Deci iată un tablou. Deci, un tablou este doar, din nou, un istoric de calcul acceptabil pe o ramură, o ramură acceptabilă a calculului mașinii. Rândurile sunt -- în loc să scriem liniar istoricul de calcul , îl vom reprezenta într-o formă de tabel în care fiecare configurație va fi pe un rând separat. Acum, dimensiunile acelui tabel vor fi n la k cu n la k, deoarece mașina rulează de la n la k pași. Deci va fi... dacă există o ramură care acceptă, va accepta în acel număr de pași. Și vom avea aici destule rânduri pentru a scrie toate configurațiile prin care trece mașina una după alta, rând cu rând, fiecare având o configurație în ea. Și apoi în partea de jos, va exista o acceptare. Detaliu minor, dacă mașina acceptă mai devreme, vom spune doar că mașina rămâne în... odată ce intră în acceptare, mașina nu se schimbă din acel moment. Deci regula mașinii este că nimic nu se schimbă. Și rămâne pur și simplu în aceeași configurație din acel moment . Atât de important să înțelegem ce suntem... dacă nu urmezi ceea ce vreau să spun prin tablou, ești condamnat pentru această prelegere. Deci, are sens să pui o întrebare pentru a înțelege ce înțelegem prin tablou. Deci doar câteva elemente aici. Deci aceasta va fi configurația de pornire pentru M pe w. Aceasta ar fi o configurație acceptabilă aici, la ultimul rând. Și vă puteți imagina... Cred că am completat un prim pas ipotetic al mașinii după pornire, unde poate mașina era... când este în... amintiți-vă cum ne-am codificat configurațiile. Deci mașina este în starea q0, uitându-se la w, primul simbol al intrării, w1. Și poate că atunci când este în q0 uitându-se la acel prim simbol, se mută în starea q7 și merge la dreapta și apoi schimbă acel w1 într-un A. Și deci acum iată capul afișat mutat cu o poziție la dreapta în noua stare q7 . Adică, desigur, asta depinde de ceea ce este proiectată mașina, care este funcția de tranziție . Dar asta este posibil ceea ce se întâmplă. La fel și... OK, atât de bine. Tabloul urmărește toți pașii tuturor ramurilor? Nu. Tabloul corespunde unei ramuri care acceptă. Fiecare ramură de acceptare diferită va avea propriul său tablou. Deci, ar putea exista mai multe moduri diferite de a completa chiar și al doilea rând. Desigur, primul rând va fi... în orice tablou, trebuie să fie la fel. Odată ce știu că... aici am scris... poate ar trebui să despachetez asta pentru tine. Este în starea de început aici, apoi aici sunt primele - aici sunt n simboluri ale w, w de lungime n. Deci există w1, w2, până la wn. Și apoi umplu restul cu spații libere. Așa că ar fi trebuit să spun și asta. Dar OK. Așa că vreau să fac tabelul meu n la k cu n la k, deoarece asta va fi suficient pentru a reprezenta întregul -- toate aceste configurații ale lui M rulează pentru majoritatea n la k pași, deoarece mașina, chiar dacă își trimite capul în mișcare spre dreapta cât de repede poate, nu va avea niciodată-- nu va ieși niciodată în afara acestei casete dacă rulează doar de la n la k pași. Deci, acesta va fi suficient de mare pentru a reprezenta întregul calcul al lui M. Deci înseamnă rularea de la n la k timp. Iar intrarea w este de lungime n. În regulă. Ce este k? Deci k este timpul de funcționare al mașinii. Deci am presupus din diapozitivul anterior că M rulează în timpul n până la k. BINE. Deci o întrebare bună aici. Cum poate tabloul să fie un tabel pătrat dacă avem un număr mic de istorii de calcul, dar multă bandă? Ei bine, istoricul de calcul al numărului mic , asta este o problemă. Nu spui asta bine. Știi, fiecare istoric de calcul este într-un tabel diferit. Deci, aici reprezint un singur istoric de calcul . Pot fi... vor fi multe configurații. Deci nu pot avea un număr mic de configurații folosind o mulțime de bandă, pentru că mai pot folosi o singură celulă, o celulă de bandă suplimentară de fiecare dată când... fiecare pas suplimentar al mașinii. Da. Deci nu este nicio diferență între asta. Dacă vrei să te gândești la asta ca la un istoric de calcul, este în regulă. Aceasta este de fapt doar terminologia standard care este folosită atunci când demonstrați această teoremă specială. De obicei, oamenii vorbesc despre el ca pe un tablou, dar este de fapt doar o istorie de calcul. Starea q -- Adică, întrebarea despre care sunt aceste stări q, acesta este modul în care reprezentăm configurațiile. Deci asta înseamnă că mașina este într-o stare. Nu toate coboară pe diagonală. Statele vor merge în zig-zag aici prin această imagine de aici, în funcție de modul în care se mișcă capul mașinii. Deci, trebuie să vă întoarceți și să revizuiți modul în care reprezentăm configurațiile mașinii. Amintiți-vă că configurația este un instantaneu al mașinii la un anumit punct. De unde știm că M rulează în timp polinomial? Presupunem că M rulează în polinom. Am început cu un limbaj care este în NP. Deci este o mașină a timpului polinomială nedeterministă și alegem o ramură care acceptă și notează toată secvența de configurații prin care trece mașina. Sa trecem peste. Și poate puneți mai multe întrebări pe măsură ce vi se adresează, iar eu voi alege câteva pentru a răspunde dacă asta va fi de ajutor altora. Deci acum vom construi această formulă pentru a spune că M acceptă w. Din nou, asta a fost ceea ce noi... acesta este scopul nostru. Și spune că un tablou pentru M pe w există. Și, practic, ceea ce înseamnă este că vrem să spunem că începe corect, se termină corect și că totul între ele este corect și apoi vom avea nevoie de alte lucruri pentru a vorbi despre cum vom codifica acele simboluri. folosind variabile booleene. Deci acestea vor fi cele patru părți. Iată începutul. Începe corect. Aici se termină corect. Aici se mișcă la dreapta. Și aici se vorbește despre codificarea simbolurilor în variabile booleene. Deci, acestea sunt cele patru părți ale acestei formule pe care le voi descrie. Sper că ați primit răspuns la întrebarea de ce numărul total de coloane este de la n la k, deoarece este suficient de mare pentru a se potrivi întregului - toate configurațiile pentru care rulează mașina cel mult de la n la k pași, adică ceea ce presupunem. BINE. Așa că acum revenind la asta, voi descrie aceste componente diferite acum pe diapozitive separate. Permiteți-mi să încep cu această celulă phi componentă, care este un fel de cea mai fundamentală, deoarece vorbește despre modul în care vom codifica acele simboluri ale tabloului în variabilele booleene. Deci, din nou, iată un fel de imagine de avut în vedere a acestui tablou, acest n la k cu n la tabelul k, reprezentând o ramură acceptabilă a calculului mașinii dacă există una. Și acum permiteți-mi să desenez una dintre celulele de aici. Am de gând să măresc. Deci aceasta este celula i, j aici. Și o să-- va fi o colecție de variabile booleene asociate cu fiecare dintre celule. Deci, fiecare dintre celule va avea o grămadă de variabile pentru sine. Și acestea vor fi practic variabile indicatoare. Ei vor indica ce simbol va avea acea celulă în ea. Deci, din nou, imaginează-ți aici... în acest tablou, nu știm cum va fi completat. Dar oricum este completat, fiecare dintre aceste celule primește un simbol. Și acel simbol ar putea fi fie un simbol al alfabetului pe bandă , fie un simbol reprezentând o stare. Așa ne facem configurațiile. Așadar, ar putea fi un simbol alfabet de bandă aici care arată mărirea. Poate că este simbolul alfabetului pe bandă, care reprezintă simbolul gol. Sau poate reprezintă o stare. Acum, cum voi codifica asta cu variabile? Deci asta-- permiteți-mi-- aceasta este colecția de variabile care se va aplica întregii formule phi sub M, w. Fiecare celulă este-- deci fiecare celulă i, j va avea un set de variabile, una pentru fiecare simbol posibil sigma care se află în alfabetul de configurare, și anume un simbol de bandă sau un simbol de stare. Deci voi avea... ei bine, poate asta va deveni clar pe măsură ce îl scriu. Deci, dacă transform variabila x i, j, sigma egală cu adevărat, acesta este doar un mod de a spune că celula i, j conține o sigma. Deci, dacă am x i, j, a, înseamnă că simbolul conține un a. Așa că o să ilustrez asta acum pentru tine. Așa că imaginați-vă că aveți lumini reprezentând toate diferitele x i, j pentru diferitele sigma. N-am spus asta bine. Deci suntem în celula i, j. Deci toate acestea sunt variabile x i, j. Toate sunt variabile x i, j sigma pentru diferitele sigma care pot intra în această celulă. Deci toate diferitele sigma posibile. Deci aceasta este uniunea gamma Q. Deci, acum, dacă am un A aici în acea celulă, atunci variabila x i, j, a este adevărată. Și doar ajutându- vă să vizualizați asta, asta va corespunde cu aprinderea luminii. Va fi o lumină asociată cu fiecare dintre aceste variabile. Și va fi pornit când acea variabilă este adevărată. În mod similar, dacă am simbolul gol este lucrul care merge în acea celulă, atunci acea variabilă este activată. Sper că o poți vedea. Poate că este puțin mic pe ecran. X i, j necompletat, o variabilă este adevărată. Și, în mod similar, dacă aici este q7, variabila x i, j q7 este adevărată. Deci, acesta este modul în care vom codifica conținutul acestor celule folosind aceste variabile indicator. Și acum trebuie să începem să facem o logică booleană pentru a ne asigura că acele variabile reprezintă în mod rezonabil celula con-- conținutul acestor celule. Deci, de exemplu, care ar fi primul lucru care îți vine în minte? Ei bine, mai bine nu avem două lumini aprinse în oricare dintre celule, pentru că atunci avem două simboluri în acea celulă. Și asta nu este permis. Fiecare celulă merge -- vrem ca fiecare celulă să aibă exact un simbol. Și asta corespunde că fiecare celulă are exact una dintre lumini aprinsă sau, în mod echivalent, fiecare celulă ar trebui să aibă exact una dintre variabile să fie adevărată. Aceasta este prima parte a formulei care va spune doar asta. Așa că permiteți-mi să vă arăt cum arată. Deci aici vorbim despre această celulă phi. Se spune că există exact o lumină aprinsă pe celulă sau, cu alte cuvinte, exact una dintre x i, j sigma este adevărată pentru fiecare i, j. Așa că așa voi exprima de fapt asta folosind formula mea booleană. Am un fel de codificare pe culori a diferitelor părți ale formulei, pe care vi le scriu aici în engleză. Deci, mai întâi, vreau să spun asta. Deci, în fiecare celulă, există cel puțin o lumină care este aprinsă și există cel mult o lumină care este aprinsă. Deci iată partea verde. Acest lucru va spune că cel puțin o lumină este aprinsă. Deci, voi spune că luând toate var-- toate simbolurile care pot apărea în acea celulă și luând un OR peste toate variabilele asociate diferite . Deci, fie are primul simbol activat, fie al doilea simbol este acolo, fie punct punct punct, fie ultimul simbol este acolo. Unul dintre aceștia trebuie să fie acolo. Voi scrie asta folosind notația mea SAU mare. Deci, pentru sigma care apare în acest set de posibilități, una dintre acele variabile trebuie să fie activată cel puțin. Asta îți spune acest SAU mare. Acum vrem să ne asigurăm că există cel mult unul activat. Așa că nu există... există cel puțin unul pornit, dar nu există două care sunt pornite. Deci voi avea o parte suplimentară a formulei aici, care spune... și sper că puteți citi asta. Este un pic mic. Dacă am două simboluri diferite, sigma și tau, acestea sunt configurații - posibile simboluri de configurare, unde sigma și tau nu sunt egale. Deci, ți-l citesc dacă este prea mic pentru ecranul tău. Atunci am să spun că nu se poate. Deci am negația lui x i, j sigma și x i, j tau. Deci, spunând altfel , nu este cazul că acea celulă conține atât sigma, cât și tau pentru oricare două simboluri sigma și tau, atâta timp cât sunt diferite. Și vrem să luăm aceste două formule și să le adunăm împreună. Și asta îmi spune în celula i, j, că exact una dintre variabile este adevărată. Exact unul dintre lumini este aprins. Și asta va reprezenta ce simbol intră în acea celulă. Și apoi vreau să iau AND peste toate celulele posibile pentru a mă asigura că acum voi aplica asta peste tot. Și așa că acum fac un AND pentru i și j cuprins între 1 și n până la k pentru a aplica această logică în imagine. Da. Sigma unions-- solicitarea sigma union Q conține intrarea, ieșirea, da. Aceasta nu este o sigma. Acesta este un gamma. Gamma este alfabetul benzii. Acesta este orice simbol, inclusiv un simbol de intrare, de la sigma va fi în gamma. Deci, acesta este orice simbol care poate apărea pe bandă. Și această expresie aici, adică expresia subcelulă phi. Așa că iată un mic check-in pentru tine. Dar poate înainte de a trece la check-in, să ne asigurăm că ar fi mai bine să răspundem la câteva întrebări, iar apoi putem cere check-in-ul pentru tine. Înțelegi? Adică, dacă nu primești asta, ar trebui să încerci să-ți dai seama cum să-l obții, pentru că aceasta este într-adevăr doar fundația. Devine doar mai mult... nu este o dovadă foarte complicată odată ce îți faci o idee despre ce se întâmplă, dar dacă nu primești această parte, nu vei putea obține restul. BINE. Habar n-am ce înseamnă asta, dar o să vă citesc. Aceasta arată ca o codificare de un tensor fierbinte , aceeași din comun - aceeași formă utilizată în mod obișnuit în ML. BINE. Este doar un indiciu... Le-aș numi doar variabile indicator. De ce este sigma union Q pentru cei mari SI aici? Uniunea Sigma Q? Te referi la uniunea gamma Q? [Gâfâind] Acest lucru este greșit. BINE. Acum înțeleg de ce toată lumea este supărată. Acesta ar trebui să fie un gamma, nu un sigma. Există un boo-boo. Îmi pare rău pentru asta. Nu știu dacă pot repara asta fără să sparg tot toboganul, așa că nici măcar nu voi încerca. Acest simbol aici ar trebui să fie gamma, nu sigma. Este o greșeală de tipar. Mulțumesc că ai prins asta. Da. Deci întrebarea este... OK. Deci, subcelula phi încearcă doar să se asigure că codificarea reprezintă setarea unei grămadă de simboluri în tablou. Nu... deci fiecare celulă va avea exact un simbol , nu două, nu zero. Așa că asta este sub-celula phi-- dacă ați mulțumit, dacă ați setat variabilele pentru a satisface subcelula phi , atunci va fi câte un simbol în fiecare-- câte un simbol în fiecare dintre acele celule. Acum, o altă întrebare, acesta nu este un CNF. Nu, acesta nu este un CNF. Asta e a doua jumătate a... asta va fi... Sper să nu rămânem fără timp. Dar am o modalitate de a converti formulele SAT generale în CNF-uri și de a păstra satisfacabilitatea. Deci vom face acea reducere după aceea. Iată o mică verificare pentru a vedea dacă înțelegi la un anumit nivel ce se întâmplă. Câte variabile are de fapt această formulă? Este ordinul n? Comanda n pătrat? n la k? Rețineți, k este timpul de funcționare al mașinii. Sau n la 2k? Ce crezi? Deci, pentru câte variabile. Vreau să spun că în toate phi sub M. Câte variabile avem toate împreună în această formulă dacă asta este întrebarea. Și aici sunt variabilele. Deci, descriindu-le aici - x i, j, sigma. BINE. Am de gând să închid asta. Deci alege ceva. În regulă. Încheierea sondajului, 1, 2, 3. OK. Da. BINE. Asta e o intrebare buna. Deci, în primul rând, răspunsul corect este, de fapt, D. Este ordinul n la 2k. Acum, primesc câteva întrebări despre, cum rămâne cu dimensiunea gamma și Q? Ei bine, acestea vor fi reparate. Ele depind doar de mașină, dar nu depind de n. Deci, gândindu-ne funcțional în termeni de n, acesta va fi un multiplicator constant. Și așa va fi absorbit în marele O. Deci de aceea avem... acestea sunt constante în raport cu n. Acestea sunt fixe. Nu există de la n la cele k simboluri posibile. Există un număr fix de simboluri. Depinde doar de mașină. Deci, ne uităm la o anumită mașină și la ce se întâmplă când te uiți la intrări mari. Deci de ce este D și nu C? Ei bine, nu uita... cât de mare este masa asta? Acesta este n la k cu n la k. Deci există n pentru cele 2k celule, n pentru k pătrat sau n pentru cele 2k celule de aici. Și deci există o colecție de variabile pentru fiecare celulă, un număr fix de variabile pentru fiecare celulă. Deci, de aceea ordinea sa n la 2k. Bun. Deci hai să mergem mai departe. Cred că de fapt... stai. Mai avem un tobogan și cred că mai avem o pauză după. Deci, acum să vorbim în continuare despre construirea a încă două bucăți din formula phi sub M, w. Deci am terminat deja sub-celula phi. Să ne uităm la phi sub start și phi sub accept. Și phi start ne va spune că configurația de pornire are exact aceste simboluri. Și phi accept ne spune că configurația de jos conține o stare de acceptare undeva. Deci cum vom scrie asta? Ei bine, în primul rând, o să le scriu doar celulă cu celulă. Deci, în primul rând, phi start va spune că celula 1, 1 conține un q0. Adică, știu care ar trebui să fie configurația de pornire , pentru că gândindu-ne la mine, sau gândindu-vă la noi ca reducere, reducerea este dată M. I se dă w. Deci știe care este starea de pornire. Știe care sunt simbolurile lui w. Deci știe care este configurația de pornire. Este doar q0 urmat de n simboluri ale lui w urmate de spații libere. Deci, vrea ca prima celulă din colțul din stânga aici să fie un q0, starea de pornire a mașinii, pe care o cunoaște. Deci, va spune x sub 1, 1, q0, care trebuie activat. Deci, aici va fi AND de o grămadă de variabile. Și pentru a satisface phi sub start, toate aceste variabile trebuie setate la adevărat. Deci asta înseamnă că trebuie să avem un q0 în acea celulă. Deci acum vom face următoarea celulă aici. 1, 2, următoarea celulă a configurației de pornire. Deci phi start va avea x 1, 2. Deci acesta este următorul loc. Conține w1. Și așa mai departe. x 1, 3 conține w2, până la wn, și apoi vor fi o grămadă de părți suplimentare care spun că avem spații libere în rest, explicând exact toate simbolurile din acel rând de sus. Pentru că așa arată formula phi start sau subformula a formulei generale pe care o facem. Acum să aruncăm o privire la phi accept. Phi accept, pentru că doar caut ca q accept să apară undeva în acel rând de jos, o voi face în termeni de SAU. Deci iată-- variabilele acum, observați, au de la n la k pentru că este ultimul rând din tabel. Deci rândul n la k aici. Și apoi voi varia j de la 1 la n la k. Deci j, numărul coloanei, va varia de la 1 la n până la k. Și caut să accept asta. Deci x n la k j, unde j variază și q acceptă. Una dintre acestea trebuie să fie adevărată. Unul dintre ele trebuie să fie pornit. Și de aceea este un SAU mare. Și asta e piesa mea de phi accept. Și acum vom lua o mică pauză. Și nu ezitați să- mi mai puneți câteva întrebări. Lasă-mă să pornesc ceasul. Ia-ți o cafea sau pune-mi câteva întrebări. Sunt bucuros să le răspund. De ce nu verificăm că q accept apare o singură dată? Este posibil ca q accept să apară de două ori? E o întrebare grozavă. Deci asta ar fi cu siguranță o configurație ruptă dacă s-ar întâmpla asta, deoarece o configurație poate avea... trebuie să aibă exact un simbol de stare să apară. Modul în care vom impune acest lucru este cu partea de mișcare phi a formulei, pe care nu am văzut-o încă. Așadar, phi move va garanta că mașina acționează corect, astfel încât toate rândurile tabloului sunt toate configurații legale și toate urmează legal din precedente. Deci, într-un anumit sens, ridicarea grea vine în mișcare phi, dar nu este chiar atât de rău. Cineva spune, din curiozitate, cât de aproape este această dovadă a intuiției de dovada reală? Aceasta este dovada reală. Nu există... Nu ascund nimic. Vreau să spun, suntem puțin liberi aici, dar poți întoarce asta... nu tăiem nici un colț aici. Exact așa stau dovada. Și deci nu... ai o afacere adevărată aici. Cineva a vrut să vadă diapozitivul anterior, așa că iată-ne. Hopa. Vrei să întrebi ceva? Deci celula phi spune că există exact un simbol pe celulă. Și variabilele sunt stabilite într- un fel în ceea ce privește gândirea lor ca variabile indicator. Există exact o variabilă setată la adevărat în fiecare celulă. Deci, există exact un simbol pe celulă. Asta îți spune celula phi. Dacă nu ai asta, atunci ai o mizerie. Deci trebuie să începi cu asta. Și apoi cu... alte lucruri vor fi condiții suplimentare, care, atunci când sunt îndeplinite, vor impune restul proprietăților pe care le dorim. De ce ar eșua demonstrația dacă înlocuim n la k cu 2 la n la k? Deci bine. Presupun unde... vom folosi doar timpul de rulare polinom al mașinii lui M, mașina nedeterministă. Adică, dacă ai avea o filă enormă, trebuie să arătăm în cele din urmă că această reducere este o reducere a timpului polinomial. Și asta va depinde de cât de mare este tabloul, pentru că asta ne va spune cât de mare este formula pe care o producem, phi sub M, w. Dacă phi sub M, w este exponențial de mare, nu avem o rugăciune de a putea scoate acea formulă în timp polinomial. Dacă au fost mai puțin de n la k pași, repetăm ultima configurație? Da, asta am spus. Dacă mașina se termină mai devreme, ultima configurație rămâne doar acolo. Deci vom modifica ușor definiția mașinii, astfel încât să rămână. Da. BINE. Da. Lasă-mă să nu o iau pe cealaltă... există o grămadă de alte întrebări, unele dintre ele puțin pe partea tehnică. Lasă-mă... poate voi încerca să le adresez pe măsură ce apar, dacă se dovedește că funcționează. Deci pauza s-a terminat. De ce nu noi-- este posibil ca configurația de codificare să nu se potrivească în n la k? Deci întrebarea este, există posibilitatea ca codificarea configurației să nu se potrivească în n la k? Dacă mașina rulează de la n la k pași, configurația trebuie să se potrivească între n la k, deoarece nu poate folosi nimic mai mult din n la k pași. Deci gândește-te. Dar nu. Răspunsul sunt configurațiile - dacă mașina rulează în timp n la k, întregul tablou este suficient de mare pentru a scrie întregul istoric al calculelor. Bine, deci hai să continuăm. Phi sub move, aceasta este, într-un fel, partea care ne va spune că am început corect, am terminat corect. Celula Phi spune că fiecare celulă conține un simbol. Și acum trebuie să spunem că întregul interior este corect. Cum vom face asta? Deci acestea sunt părțile pe care le-am făcut deja. Și felul în care voi descrie asta este în termeni de genul ăsta de ferestre mici pe care le numesc cartiere. Așa că imaginați-vă că aici avem un dreptunghi 2 pe 3, pe care îl voi numi un cartier 2 pe 3. Și ce voi argumenta, dar nu voi dovedi aici. O să o spun cu adevărat, dar este doar un fel de fapt mai mult sau mai puțin evident. Dar dovada... cartea are dovada formală, că, dacă vreuna... fiecare dintre acestea aici este legitimă, este legală conform regulilor mașinii, dacă fiecare... imaginați-vă că aveți acestea... hopa. Lasă-mă să mă pun din nou aici, ca să mă poți vedea. Dacă aveți aici fiecare fereastră 2 pe 3, puteți lua aceasta ca o fereastră și o glisați peste întreaga imagine a tabloului. Și totul arată bine aici în ceea ce privește funcționarea mașinii. Așa că voi spune ce înseamnă asta într-o secundă. Dar dacă totul arată bine la nivel local peste tot, atunci întregul tablou trebuie să fie un tablou valid în ceea ce privește regulile lui M. Poate că este mai ușor dacă descriu ce vreau să spun prin acestea fiind legale. Deci aceste cartiere, aceste cartiere 2 cu 3 sunt legale dacă sunt în concordanță cu funcția de tranziție a lui M. Așa că voi descrie mai degrabă decât... Adică, pentru a face asta în mod formal, ar trebui să trec printr-un proces pe care l-am parcurs-- cum am făcut atunci când am trecut prin construcția pentru problema corespondenței Post și să spun dacă mașina se mișcă la stânga, se întâmplă acest lucru. Dacă se mișcă corect, asta e... Cred că nu este chiar necesar. Puteți obține ideea foarte clar făcând-o la un nivel puțin mai înalt. Deci, să ne uităm la ce mă refer prin vecinătate legală. Deci o vecinătate legală este o setare a valorilor, cele șase valori ale acestei vecinătăți 2 cu 3, într-un mod care nu încalcă regulile lui M. Deci, de exemplu, dacă M, când este în starea q7 citirea lui b, intră în starea q3 și se mișcă la stânga, atunci aceasta ar fi o vecinătate legală, deoarece arată capul mișcându-se spre stânga, b devenind un c. Deci, citind a b, ar trebui să spun și că transformă acel b în a c. Și ne îndreptăm spre stânga în starea q3. Deci, aceasta ar fi o vecinătate legală, dacă așa este calea - deci a fi legal depinde de funcția de tranziție a mașinii. Deci, având în vedere funcția de tranziție, asta vă va spune care sunt vecinătățile legale. Deci, un alt cartier legal-- acesta ar fi întotdeauna un cartier legal-- este că dacă nimic nu se schimbă. Asta înseamnă că capul mașinii era în altă parte. Și, așadar, orice a fost pe bandă în acest pas va fi același lucru în acele locuri un pas mai târziu. Iată o altă posibilă vecinătate legală. Dacă capul apare brusc pe una dintre celule, fie din stânga, fie din dreapta, aceasta ar corespunde că mașina își va muta capul de undeva în afara cartierului în cartier în acel pas. Deci, aceasta ar putea fi o vecinătate legală, cu condiția ca mașina să își miște capul la stânga într-o stare q5 la un moment dat în anumite condiții. Și iată un alt fel de cartier legal ciudat. Dacă aveți a, b, c și apoi a se schimbă într-un d, aceasta ar putea fi, de asemenea, o vecinătate legală dacă funcția de tranziție a mașinii permite ca un a să fie convertit în d atunci când există o mașină - când există o citire de stare că a, și acea stare își mișcă și capul spre stânga. Deci nu se mută în această imagine. Deci acestea sunt exemple de vecinătăți legale. Lasă-mă să-ți arăt câteva cartiere ilegale. Doar că fac asta... asta este un fel de dovadă prin exemplu acum. Aceasta este poate cea mai intuitivă parte. Dar susțin că este ușor să transformi asta în ceva etanș și formal. Deci acest lucru ar fi în mod clar ilegal. Dacă aveți o bucată de bandă în pasul anterior unde este a, b, c și apoi brusc b se schimbă în a d. Simbolul de pe bandă se schimbă de nicăieri fără a avea un cap în apropiere de un diferit... de altceva. Asta nu s-ar putea întâmpla niciodată. Deci asta ar fi ilegal. Un alt lucru care ar fi ilegal este dacă un stat apare de nicăieri. Asta nu s-ar putea întâmpla niciodată. Sau dacă pur și simplu dispare. Asta nu s-ar putea întâmpla niciodată. Și iată un altul... iată unul interesant. Dacă un stat devine două stări. Nu uitați că mașina este nedeterministă. Așa că, în principiu, mașina și-ar putea mișca capul la stânga pe o ramură și la dreapta pe o altă ramură, dar acestea ar trebui să fie în tablouri diferite. Ele nu pot fi în același tablou, pentru că nu corespunde niciunuia dintre firele de execuție ale calculului, cele cu fire multiple. Și spun asta pentru că, dacă vă gândiți la afirmația mea, care va fi pusă aici, că dacă fiecare cartier 2 pe 3 este legal, atunci tabloul în general corespunde unui istoric de calcul. Acest lucru ilustrează de ce nu este suficient să ai un cartier 2 pe 2, unde chiar ai nevoie de 2 pe 3. Pentru că dacă acesta ar fi un cartier 2 pe 2, dacă te uiți doar la aceste patru -- acest 2 pe 2 din stânga, asta ar putea să fie un cartier legal dacă a fost un 2 cu 2, dacă regulile mașinii permiteau asta. Și cele patru casete din dreapta - patru celule din dreapta ar putea fi, de asemenea, un cartier legal. Deci ai putea avea ceva care arată OK din perspectiva cartierelor 2 cu 2, dar la nivel global, în ceea ce privește tabloul general, este complet nesens, deoarece are mai multe accesări. Dar dacă ai un cartier 2 pe 3, este suficient de mare pentru a preveni această situație. Și apoi puteți verifica detaliile. Și cred că este foarte plauzibil că garantează că tabloul general este legitim dacă toate cartierele 2 cu 3 sunt legale. Și asta este ceea ce vom transforma într-o expresie booleană. Vom spune pentru fiecare celulă că setul-- pentru fiecare cartier-- deci iată un cartier la locația i, j. Eu numesc această poziție aici un fel de locație de acasă pentru acel cartier. Pentru fiecare cartier, acesta trebuie setat la una dintre posibilitățile legale. Și există, din nou, doar un număr fix dintre acestea, deoarece există un număr fix de simboluri posibile care pot apărea în acele celule. Deci acesta este acel număr fix la a șasea putere cel mult. Și am să spun că celula din stânga sus, care ar fi aceasta, este în r. Și acesta de aici este un s. Și acesta este un t. Și acesta este un v, dacă doar urmăriți ceea ce vă spun indicii. Se spune că acea bucată de bandă, acea bucată de tablou de aici este stabilită în conformitate cu una dintre posibilele setări legale. Și vom merge doar la SAU peste toate aceste posibile număr fix de setări legale. Și apoi iau un AND peste toate celulele de bandă posibile, peste toate cartierele posibile. Și asta va fi mișcarea mea phi. Si asta e. BINE. Să vedem. Pot să explic din nou al treilea exemplu de ilegalitate? Deci despre acesta de aici, presupun, sunt întrebat despre mine. Ei bine, dacă mașina este într-o stare q7 citind un c, capul trebuie să se miște fie la stânga, fie la dreapta. Deci, la următoarea configurație, trebuie să existe un simbol de stare care să apară fie în această celulă, fie în această celulă. Și aici, banda... capul practic a dispărut fără nicăieri... a dispărut. Asta nu s-ar putea întâmpla conform regulilor mașinii, așa cum vorbim despre mașinile Turing. Deci nu este posibil. Deci acesta ar fi un cartier ilegal. Vrei să împiedici lucrurile rele să se întâmple oriunde aici. Deci numai lucruri bune se pot întâmpla la nivel local. Și asta garantează că imaginea de ansamblu este OK. Trebuie să verificăm că capul nu părăsește tabloul din stânga cea mai dreaptă spre dreapta? Da, sunt niște mici detalii aici de genul ăsta. Deci întrebarea este, trebuie să mă asigur că... da, probabil că trebuie să marcați. Cred că cartea probabil face acest lucru corect. Poate fi necesar să marcați capetele din stânga și din dreapta pentru a vă asigura că... Adică, capătul din dreapta nu este o problemă, pentru că mașina nu se poate deplasa niciodată de la capătul drept. Și dacă proiectați mașina astfel încât să nu-și miște niciodată capul de la capătul stâng, ceea ce puteți face, atunci nu ar trebui să vă faceți griji cu privire la această posibilitate. Dar, altfel, ar trebui să puneți un fel de delimitator aici pentru a impune ca capul să nu se miște de la capătul stâng. Deci, există și câteva detalii de acest fel. Vor fi două capete în același rând. Nu, asta poate... Nu știu ce tu... spune cineva, vor fi două capete în același rând. Vă rugăm să detaliați, deoarece acest lucru este conceput pentru a nu permite două capete în același rând. Aș putea să trec din nou peste sala de operații pentru legalitate? BINE. SAU, marele SAU aici, ceea ce mă gândesc este să iau-- va fi-- în primul rând, mă uit la mașină și mă uit la funcția de tranziție. Și pe baza asta, notez lista tuturor cartierelor legale 2 câte 3. Deci toate setările care corespund cartierelor legale 2 cu 3. Va fi un număr fix din acestea. 100. Există 100 de cartiere legale posibile din care am notat aici patru. Dar poate că există un număr, să zicem 100. Deci acum va exista un SAU peste acele 100 de posibilități diferite. Va fi fie acest cartier legal, fie un alt cartier legal, fie un alt cartier legal. Și pentru fiecare dintre acele vecinătăți legale, o să spun, ei bine, variabilele sunt setate în funcție de acea vecinătate legală, sau variabilele sunt setate în funcție de vecinătatea legală următoare sau variabilele sunt setate în funcție de următoarea vecinătate legală. cartier și fă asta de 100 de ori. Unul dintre aceia trebuie să ajungă... Adică este un operator operator, așa că unul dintre ei trebuie să funcționeze. În caz contrar, formula eșuează. Și va fi fals, pentru că vei merge și asta peste toate cartierele din imagine. Este posibil să aveți un cap în extrema stângă a configurației și unul în extrema dreaptă? Adică un cap aici și un cap acolo? Adică, cum a ajuns capul acolo? Nu se poate întâmpla. Știi, capul trebuie să vină dintr-un cap deasupra lui. Dacă aveți de gând să vă faceți griji cu privire la detaliile granițelor de aici, toate acestea se pot rezolva. Deci, să nu pierdem din vedere ideea principală. Adică, dacă înțelegi ideea principală, poți repara micile detalii. Așa că vreau să mă asigur că înțelegeți ideea principală a ceea ce se întâmplă. Deci, să terminăm această dovadă. Deci, în rezumat, am dat o reducere de la 8 la SAT. De asta aveam nevoie. Era în acele patru bucăți. Și trebuie doar să argumentezi că formula pe care o construim nu este prea mare. Și va fi practic de dimensiunea tabloului dacă te uiți la ceea ce am construit. Numărul de variabile este aproximativ de dimensiunea tabloului. Și cantitatea de logică pe care o punem în formulă va fi, de asemenea, o cantitate fixă de logică independentă de n pentru fiecare dintre variabilele din acel tablou. Și cineva m-a întrebat despre mărime - cât de mari sunt indicii. Indicii pentru valoarea x i , valorile i și j, din punct de vedere tehnic, vor fi numere între 1 și n până la k. Așa că va trebui să le notezi. Și, deci, acesta va fi un mic cost logaritmic suplimentar pentru a scrie acele lucruri. Nu este chiar atât de interesant un punct. Și astfel f general va fi calculat în timp polinomial, deoarece rezultatul nu este foarte mare. Și, de asemenea, nu este complicat să notezi rezultatul. Deci, acesta este sfârșitul dovezii. Pot răspunde la câteva întrebări. De ce nu putem să verificăm că întregul... aceasta este o întrebare bună. De ce nu putem verifica dacă întregul rând este legal? Puteți verifica dacă un rând este de fapt o configurație. Dar pentru a verifica dacă rândul urmează din rândul anterior, în cele din urmă, funcționarea unei mașini Turing este un lucru local. Adică, felul în care se mișcă de la o configurație la alta depinde local de unde se află capul. Și deci într-adevăr, acesta este doar un alt mod de-- modul în care spun că este doar să verifici întreaga configurație, dar doar să o faci local. Nu știu dacă asta te mulțumește. De ce nu merg mai departe pentru că vreau doar să mă asigur că avem suficient timp pentru a ajunge la ultima parte, care este puțin... Mă tem, puțin tehnic. Deci vom schimba treptele acum și vom vorbi despre reducerea SAT la 3SAT. Și să vedem cum merge. Nu întotdeauna am cel mai mare succes cu prezentarea acestei piese mici, pentru că este puțin un argument tehnic. Dar dacă nu îl înțelegi, nu-ți face griji. Trebuie doar să accepți că este adevărat. Dar aș vrea să vi-l arăt doar pentru a face întreaga prezentare completă în acest sens. Așa că voi oferi o reducere care mapează formulele generale cu formulele 3CNF. Așa că mapăm SAT la 3SAT. Dacă vă amintiți, 3SAT este satisfiability, dar pentru trei CNF-uri. Deci, o formă normală conjunctivă sub forma acelor propoziții, care sunt AND împreună. Și fiecare clauză este un SAU al unui grup de literale, care sunt variabile sau variabile negate. Așa că vreau să convertesc phi în phi prim, care este formula 3CNF, dar să păstrez satisfacabilitatea. Și phi prime nu va fi echivalent logic cu phi, pentru că și eu aș putea face asta. Pot converti orice formulă într- o formulă CNF echivalentă logic . Poate nici măcar un 3CNF, dar da, nu veți putea obține un 3CNF, dar puteți obține un CNF. Dar ar putea fi exponențial mai mare. Și asta nu este suficient de bun. Trebuie să fac reducerea timpului polinomial. Deci nu pot genera o formulă mult mai mare, care să fie exponențial mai mare. Și așa voi face asta adăugând variabile suplimentare. Deci nu va fi echivalent din punct de vedere logic, deoarece noua formulă va avea variabile suplimentare în ea. O să o fac prin exemplu. Și vom vedea cum merge. Deci iată phi, care nu este în 3CNF. Nici măcar nu este în CNF, pentru că apar SAU ale AND-urilor , ceea ce nu este permis să se întâmple într-un CNF. Deci, cum o vom transforma într-o formulă 3CNF care să păstreze satisfacabilitatea? Și doar lucrând cu acest exemplu, sper să vă dau măcar o idee despre cum faceți conversia în general. Deci, mai întâi de toate, voi reprezenta această formulă ca un copac folosind structura sa naturală de arbore. Deci intelegi. Deci a AND B devine a AND b scris ca un arbore. Și apoi eu SAU asta cu c. Așa că obțin structura arborelui aici într-un fel natural. Și voi eticheta toate aceste noduri intermediare, care sunt asociate acum cu operațiuni. Și presupun, de asemenea, că formula este complet între paranteze, astfel încât fiecare operație la care mă gândesc doar aplică doar cele două -- este o operație binară. Și să ignorăm negațiile pentru o clipă, pentru că negațiile, le poți împinge oricând până la frunze. Dar va face totul prea complicat. Deci negațiile se dovedesc a nu fi o problemă. Deci vor fi negații doar la nivelul intrărilor, nu la operațiile de negație din mijloc. Deci avem această structură arborescentă aici. Și acum voi folosi aceste două fapte logice. Și nu știu dacă... probabil că ați văzut cu toții AND și SAU, sper. Altfel, va fi foarte greu. Dar există și alți operatori logici, cum ar fi operatorul de implicare, unde aveți A implică B un fel de operație logică. Și astfel, aceasta presupune că dacă A este adevărat, atunci B este adevărat. Totuși, dacă A este fals, B poate fi orice. Și, în mod similar, dacă B este adevărat, A poate fi orice. Singurul lucru care este interzis este că dacă A este adevărat și B este fals. Acesta este singurul lucru care ar fi invalid. Și deci, dacă te gândești bine, asta va fi echivalent cu a spune că fie A este fals, fie B este adevărat. Una dintre acestea trebuie să fie. Și asta va fi echivalent din punct de vedere logic cu a spune că A implică B. O altă echivalență logică vă poate fi mai familiară. Este pur și simplu legea lui De Morgan, care spune că, dacă ai nu a lui A ȘI B, asta echivalează cu a spune nu a lui A sau nu a lui B. Voi folosi ambele. Acum, aici, vreau să... Am rămas fără loc pe acest slide. Așa că mă voi scoate din imagine aici pentru un minut. Nu aveam alt loc unde să pun asta. Deci aici avem -- dacă vă gândiți la AND în termeni de tabelul său de adevăr , deci iată a și b în termeni de a și b. Deci 1 și 1 sunt 1, dar toate celelalte setări ale lui a și b dau 0 pentru AND. Și o să le reprezint pe acelea-- dacă vă imaginați că a și b se vor numi c. Voi reprezenta această informație cu patru formule mici, care luate împreună, tu ȘI ei împreună, vor forța c să aibă comportamentul corect asociat cu a ȘI b. Deci, dacă a și b sunt ambele 1, atunci c este 1. Dacă a este 0 și b este 1, atunci forțează c să fie 0. Și, în mod similar, orice altă setare în afară de a și b fiind adevărată, pentru ca C să fie fals, care este ceea ce îți dorești când ai ȘI. Așa că voi scrie această expresie aici, cu z1 în locul lui c, luând acele patru expresii și adunându-le împreună. Deci acestea sunt exact aceleași patru expresii scrise liniar. Acum vreau să fac același lucru pentru z2, dar acum asta este scris în termeni de SAU. Deci, aici, în acest colț, există un tabel de adevăr puțin diferit . Deci acum, dacă oricare dintre ele este 1, obținem un rezultat 1. Și acum, dacă a ȘI b sunt adevărate, obțineți că c este adevărat. Totuși, dacă a este adevărat și b este fals, asta implică totuși c este adevărat. Deci, voi scrie acele reguli pentru a specifica modul în care trebuie setat z2. Și fiecare dintre aceste lucruri va fi transformat în clauze, trei clauze cu trei literale, folosind aceste reguli de aici. Așa că o să fac asta pentru fiecare zi. Și, în sfârșit, pentru a mă asigura că totul este satisfăcut, ceea ce înseamnă că există o ieșire de una aici, voi avea o clauză asociată, care spune că z4, ieșirea, este 1. Acum, pot converti toate acestea. când am a AND b implică c. Este echivalent logic cu not a SAU nu b SAU c. Și modul în care puteți vedea acest lucru este de fapt prin aplicarea repetată a acestor reguli aici. Rămânem puțin la timp. Așa că poate va trebui doar să verifici asta offline. Dar repede, a AND b implică c folosind prima echivalență este nu a acestei părți, SAU C. Și apoi pot folosi De Morgan pentru a converti acel nu a unui AND într-un SAU a noturilor. Și apoi pot elimina parantezele pentru că OR este asociativ. Și așa primesc o clauză, care este ceea ce am nevoie. Deci, fiecare dintre acești tipi este într-adevăr echivalent cu o clauză. Și așa am doar o grămadă de clauze. Și de fapt, din punct de vedere tehnic, acestea trebuie să fie trei, o copie a trei lucruri aici. Ar trebui să fie z4 SAU z4 SAU z4, ceea ce este mult. Așa că check-in-- [INAUDIBLE] Îmi dau seama că înregistrarea mea este întreruptă, pentru că mi-am dat seama de ultimul punct abia acum când vorbeam. Deci valoarea reală pe care o obțineți în termeni de-- oh, nu, numărul de clauze este corect. Nu, o iau înapoi. Este în regulă. Deci, dacă ați înțeles ce spuneam, sper că puteți vedea cât de mare este formula phi prim în ceea ce privește numărul de operații în phi. Deci, să vedem câți oameni primesc asta. Recunosc că acest lucru poate fi puțin din partea tehnică. BINE. O să-l închid , o să-l închid. Vă rugăm să introduceți valoarea dvs. BINE. Da, răspunsul corect este 4k plus 1, pentru că fiecare dintre aceste operații va ajunge să fie un rând în această imagine. Fiecare operație va avea asociată o variabilă. Va deveni un rând în această imagine. Și astfel, fiecare rând va avea patru clauze, care definesc ceea ce aveți nevoie - setați ceea ce aveți nevoie pentru a forța acea variabilă să aibă valoarea corectă corespunzătoare acelei operațiuni. Și atunci ai nevoie de... și ai nevoie de o clauză suplimentară aici pentru a spune că toată treaba se evaluează ca adevărată. Deci asta este tot ce am vrut să fac astăzi. Am demonstrat aceste două teoreme principale. Și acum știm că există probleme NP-complete. Și toate celelalte probleme din care putem obține - prin reduceri de la aceste probleme vor fi, de asemenea, NP-complete atâta timp cât sunt în NP. Deci asta este. Simțiți-vă liber să puneți câteva întrebări în chat sau să treceți la orice altceva veți face în continuare. Deci, o întrebare bună aici este, de ce phi prime nu este echivalent logic cu această construcție? Nu poate fi echivalent din punct de vedere logic. Echivalent logic înseamnă că vă oferă exact aceeași funcție. Dacă setați variabilele în același mod, obțineți același rezultat. Ei bine, phi prime are mai multe variabile decât are phi. Deci nici nu ar avea sens să vorbim despre echivalență logică, deoarece sunt două funcții pe un număr diferit de variabile. Deci, în acest sens, nu prea are sens. Ceea ce ați putea spune este că pentru fiecare setare a variabilelor care se suprapun, deci variabilele care apar atât în phi, cât și în phi prim-- deci acestea sunt variabilele originale ale phi-- va exista o setare de variabile noi, care va merge pentru a face -- va fi -- va exista o anumită setare a noilor variabile care va face ca cele două formule să fie de acord, dar aceasta nu este definiția echivalenței logice. Deci, de ce... revenind la dovada, dovada de satisfacție și vecinătățile legale, aș putea să trec peste de ce numărul de vecinătăți legale este polinom. Numărul de vecinătăți legale nu este doar polinom. Este constantă. Depinde doar de mașină. Nu depinde de M. Pentru că fiecare celulă poate avea cel mult un număr fix de-- poate avea numărul de simboluri de bandă plus numărul de simboluri de stare. Asta depinde doar de mașină. Deci acum avem șase celule de bandă pentru cele șase celule dintr-un cartier de 2 pe 3. Deci vei avea acel număr până la a șasea putere. Dar totuși, este o constantă pentru a șasea putere. Este încă o constantă. Nu depinde de M. Deci nu este vorba de a fi nici măcar polinom. Este o valoare constantă. Este un multiplicator constant dacă doriți să vă gândiți la dimensiunea formulei care va rezulta. Nu uitați că încercăm să facem o formulă care este... reducerea trebuie să fie polinomială. Este o reducere a timpului polinomial. Deci, asta înseamnă că pe măsură ce n crește, timpul de calcul al reducerii crește ca polinom. Dar îl reparăm pe M. Deci M nu se schimbă. Prin urmare, orice depinde doar de M va avea un impact constant asupra formulei. Nu va fi... nu depinde de M. OK, toată lumea. Pa! Pa. Te văd.