[SCRÂȘIT] [FOSȘIT] [CLIC] MICHAEL SIPSER: Bine ați venit, tuturor. Bine ați revenit la teoria calculului. Și doar pentru a recapitula unde ne aflăm, ne-am uitat la complexitatea timpului și la complexitatea spațiului. Și tocmai am terminat de demonstrat ceea ce se numesc teoreme de ierarhie, care, pe scurt, spun practic că, dacă permiteți modelului de calcul să aibă puțin mai multe resurse, puțin mai mult timp, puțin mai mult spațiu, atunci pot face mai multe lucruri cu anumite condiții. Așa că am demonstrat asta data trecută. A fost o dovadă, practic, printr-o diagonalizare. Nu știu dacă ați recunoscut diagonalizarea acolo, dar când codificați o mașină printr-o intrare și apoi rulați practic toate mașinile diferite posibile, aceasta este în esență o diagonalizare. Așa că astăzi, vom construi pe această lucrare pentru a da un exemplu a ceea ce numim o problemă naturală insolubilă. Vom spune mai multe despre ce înseamnă asta. Și apoi, vom vorbi despre ceva care este un subiect diferit, dar totuși legat, care are de-a face cu oracole și metode care pot sau nu să funcționeze pentru a rezolva problema P versus NP , care, desigur, este o mare problemă. problemă deschisă în domeniu. BINE. Deci, teoremele de ierarhie a timpului și spațiului -- pentru că le vom folosi astăzi -- ei spun că dacă acorzi puțin mai mult spațiu aici -- deci pentru funcții construibile în spațiu , funcții pe care le poți calcula efectiv în limita cantității de spațiu pe care îl specifică, puteți arăta că lucrurile pe care le puteți face în atât de mult spațiu este probabil mai mare decât ceea ce puteți face în mai puțin spațiu. Și puteți dovedi un fapt similar puțin mai slab despre clasele de complexitate a timpului. Deci ceea ce înseamnă este că aceste clase formează o ierarhie. Deci, pe măsură ce adăugați mai mult timp, sau să spunem, în acest caz, spațiu, de la n pătrat, la n cub, la n la al 4-lea, obțineți clase din ce în ce mai mari, pe care le ilustrez cu drag aici punând un punct acolo , ceea ce arată că există ceva despre care știm că este nou în acele clase, pe măsură ce treci peste aceste limite diferite. Și acest lucru va fi adevărat pentru complexitatea spațiului și va fi valabil și pentru complexitatea timpului. Și unul dintre corolarele pe care le-am subliniat data trecută este că, PSPACE este un-- include în mod corespunzător spațiul de jurnal nedeterminist , NL. Deci NL este un subset adecvat al PSPACE. Deci sunt lucruri în PSPACE care nu sunt în NL. Și amintiți-vă această notație aici, aceasta înseamnă submulțimea adecvată. Unul dintre lucrurile pe care-- un corolar ulterior pe care nu l-am menționat data trecută, dar asta ar trebui să știți, este că problema TQBF, problema noastră completă bazată pe PSPACE, este un exemplu de problemă care este în PSPACE. , evident, dar știm că nu este nici în NL. Și pentru a obține această concluzie, trebuie să te uiți, din nou, la dovada că TQBF este PSPACE complet și să observi că reducerile pe care le-am dat în acea demonstrație pot fi efectuate nu numai în timp polinomial, dar pot fi efectuate. afară în spațiul de jurnal. Și, prin urmare, dacă TQBF s-ar dovedi să coboare în NL, atunci pentru că totul în PSPACE este spațiu de jurnal reductibil la TQBF, asta ar aduce tot PSPACE la NL. Dar asta tocmai am demonstrat că nu este cazul. Prin urmare, TQBF nu putea fi în NL. OK, și vom folosi din nou acest tip de raționament în această prelegere. Deci doar un check-in rapid. Acestea sunt câteva, mai mult sau mai puțin ușoare, poate mai mult sau mai puțin complicate, continuare pe care le puteți concluziona din teoremele ierarhiei în timp și spațiu, plus câteva dintre celelalte lucruri pe care le-am demonstrat pe parcurs. Și, așadar, doar ca o verificare a înțelegerii dvs., poate acestea sunt puțin mai complicate, așa că trebuie să le citiți cu atenție. Care dintre acestea sunt cunoscute ca fiind adevărate pe baza materialului pe care l-am prezentat? Și acesta este, de asemenea, doar material, care sunt faptele despre care știm că sunt adevărate în teoria complexității. Așa că lasă-mă să lansez acel sondaj. Și bifează-le pe cele pe care le putem dovedi. Hmm. BINE. Am de gând să-l închid. Așa că vă rugăm să răspundeți repede dacă aveți de gând. OK, 1, 2, 3, sfârșit. BINE. Ei bine, cei doi candidați fruntași au dreptate. Iar cei doi care sunt în urmă aici sunt, de fapt, cei care nu sunt adevărate. Deci A și D nu sunt adevărate, pe baza a ceea ce știm. Și B și C sunt adevărate. Deci, să înțelegem, în primul rând, A, știm că este fals pentru că 2 la n plus 1 este doar de 2 ori 2 la n. Și astfel aceste două limite diferă doar printr-un factor constant. Și, de fapt, sunt de aceeași clasă de complexitate. Și astfel nu obțineți o izolare adecvată pentru A. Așa că știm că este fals. D, ei bine, dacă am putea demonstra asta, atunci am fi rezolvat celebra problemă, pentru că nu știm dacă nici P este egal cu PSPACE. Deci, dacă P este egal cu PSPACE, atunci cu siguranță PSPACE ar fi egal cu NP, care se află între cele două. Și deci nu știm cum să dovedim că PSPACE este diferit de NP, asta se bazează pe starea actuală a cunoștințelor din domeniu. Deci, acesta nu ar fi ceva despre care știm că este adevărat pe baza lucrurilor pe care le-am spus. Acum, B decurge direct din teorema ierarhiei timpului, deoarece 2 la 2n este pătratul lui 2 la n. Și aceasta este, asimptotic, o limită semnificativ mai mare. Și astfel puteți demonstra că timpul 2 n este în mod corespunzător conține timpul 2 n. C este puțin mai complicat pentru că trebuie să vă amintiți teorema lui Savitch. Teorema lui Savitch se aplică spațiului. Dar trebuie să rețineți că ceea ce puteți face în timp, în timpul nedeterminist n pătrat, puteți face și în spațiul nedeterminist n pătrat, ceea ce, la rândul său, puteți face în spațiul determinist n la pătrat. 4, care este cuprins în mod corespunzător în spațiul de la n la al 5-lea. Deci puteți demonstra că PSPACE conține în mod corespunzător timp nedeterminist n pătrat. OK, doar o grămadă de rețineri acolo. A și C sunt poate, într-un anumit sens, poate fi cel mai complicat din acest grup. BINE. Deci hai să mergem mai departe. Așa că vom prezenta, astăzi, două clase noi. Și de fapt, vreau să mă întorc aici. Ce vom încerca să realizăm în prelegerea de astăzi? Așa că ne vom uita la insolubilitatea demonstrabilă. Deci, o problemă care este insolubilă pentru noi înseamnă că este în afara lui P. Deci nu o putem rezolva în timp polinomial. Din perspectiva noastră, vom numi asta o problemă insolubilă. Acum, această problemă de aici, care se află în timpul 2 și n, dar nu în clase mai mici, deci aceasta este o problemă insolubilă. Asta e în afara lui P. Dar acest exemplu de limbaj, dacă îți amintești cum s-a dovedit teorema ierarhiei timpului sau teorema ierarhiei spațiului , practic, acest limbaj în sine nu este un limbaj interesant în afară de scopul pe care îl servește, de a fi în acea clasă și nu într-o clasă inferioară. Dar nu este o limbă de care ar păsa nimănui. Și nici măcar nu este un limbaj ușor de descris. Este doar limbajul pe care o decide o mașină Turing, unde mașina Turing este special concepută pentru a avea proprietatea că limbajul său este la un anumit nivel de complexitate. Dar în rest, nu există o descriere frumoasă a acelei limbi. Nu este ca a la n, b la n, sau vreo echivalență a 2 dfa sau ceva de genul ăsta. Deci, aș spune că acea limbă este, într-un fel, își servește scopul, dar nu este o limbă naturală la care îți pasă cu adevărat. Așadar, unul dintre scopurile prelegerii de astăzi este acela de a oferi un exemplu de limbaj natural, un limbaj care apare în mod natural , într-un sens, care este ușor de descris, în care puteți demonstra că acel limbaj este insolubil, este de fapt în afara lui P. Așa că asta e un pic de motivație unde mergem. Deci, pe parcurs, vom introduce aceste clase de complexitate exponențială , timp exponențial și spațiu exponențial, care sunt exponențial mai mari decât clasele de timp polinomial și spațiu polinomial. Deci este 2 la n la k în ambele cazuri. 2 la un polinom. Și primele cinci dintre aceste clase, de la L la PSPACE pe care le-am văzut deja, iar timpul exponențial și spațiul exponențial extind limitele pe care le-am văzut deja. Deci trebuie să verificați din nou dacă înțelegeți de ce PSPACE este un subset al timpului exponențial. Dar asta pentru că , așa cum am arătat, mergând din spațiu în timp, poți face asta cu o creștere exponențială. Acesta este costul simulării. Și mergând din timp în spațiu, nu aveți nevoie de nicio creștere. Orice poți face într- o anumită perioadă de timp, poți face în atât de mult spațiu. Deci, orice puteți face într- o anumită cantitate de spațiu, puteți face și într-un timp exponențial mai mare. Bine, deci acelea erau teoreme simple pe care le-am demonstrat chiar de la început. Acum, teoremele de ierarhie ne permit să încheiem unele separări între aceste clase. Așa că ne-am uitat deja la acesta, NL versus PSPACE. Și am văzut că, deoarece NL este, după teorema lui Savitch, în spațiu determinist log pătrat, care este conținut în mod corespunzător în spațiul polinomial, obțineți o separare între aceste două clase, probabil. Și din motive similare, spațiu polinomial la spațiu exponențial, veți obține o separare de teorema ierarhiei spațiului. Și timpul polinomial la timpul exponențial, obțineți o separare demonstrabilă în virtutea teoremei ierarhiei. Acum vom defini probleme complete pentru aceste două clase, timp exponențial și spațiu exponențial. Deci avem timp exponențial complet. Va fi analog cu ceea ce am arătat înainte, și anume că este un membru al timpului exponențial. Și fiecare problemă în timp exponențial este reductibilă la ea, să spunem, în timp polinomial, deși nu se va dovedi cu adevărat a fi materie. Ar putea fi în spațiul de jurnal. O metodă simplă de reducere va fi suficient de bună. Să presupunem că timpul polinomial este definiția tipică. Și același lucru pentru spațiul exponențial complet. Vom spune că este spațiu exponențial complet, dacă este un spațiu exponențial. Și orice altceva din spațiul exponențial este timpul polinomial reductibil la el. BINE. Dar lucrul important este că, dacă ceva este complet în timp exponențial, știi că este în afara lui P, din aceleași motive pe care le-am văzut acum de mai multe ori. Și anume că, dacă o problemă în timp exponențial complet ar ajunge să fie în P, atunci pentru că orice altceva în timp exponențial este reductibil la problema completă, ele ar fi, de asemenea, în P. Și astfel timpul exponențial și P ar fi egale. Dar am spus doar că nu sunt egali din cauza teoremei ierarhiei. Deci logica este că teorema ierarhiei separă clasa, iar apoi problema completă moștenește dificultatea clasei mai mari. Deci problema completă nu poate fi mai mică decât celelalte probleme din clasă, pentru că toate sunt reductibile la ea. Așadar, același lucru va fi valabil și pentru o problemă de spațiu exponențial complet. Nu poate fi nici măcar în PSPACE, deoarece spațiul exponențial și PSPACE sunt diferite. Și dacă nu este în PSPACE, nu va fi în P. Și astfel, în ambele cazuri, dacă aveți o problemă care este completă pentru spațiu exponențial sau timp exponențial, știm că acele probleme sunt insolubile. Și strategia noastră de a oferi o problemă naturală insolubilă este să arătăm că este completă pentru una dintre aceste clase. Și de fapt se va dovedi a fi o problemă completă a spațiului exponențial pe care o vom da ca exemplu. OK, deci acesta este planul. Cred că este un moment bun să... haideți să luăm câteva întrebări aici pentru a ne asigura că suntem cu toții pe aceeași pagină cu ceea ce facem. Așa că lasă-mă să citesc. Am câteva întrebări deja aici. Deci acesta este un mic comentariu secundar că cineva... e o întrebare interesantă. Practic, este posibil să nu putem demonstra, rezolva problema P versus NP, că nu este o problemă la care se poate răspunde din axiomele de bază ale matematicii, dacă interpretez corect întrebarea. Există anumite probleme în matematică-- și cred că, poate, am menționat mai devreme în termen, problema dacă există o mulțime a cărei dimensiune este între numerele întregi și numerele reale. Știm că numerele reale sunt mai mari ca dimensiuni decât numerele întregi. Acesta a fost primul nostru exemplu de diagonalizare. Și există o problemă de dimensiune strict între cele două? Mai mare decât numerele întregi, mai mici decât numerele reale. Deci aceasta este o problemă care a fost pusă cu mult timp în urmă. A fost una dintre problemele lui Hilbert. Și în cele din urmă s- a dovedit a fi fără răspuns folosind axiomele de bază ale matematicii. Deci întrebarea este, poate P versus NP este în aceeași categorie. Ar putea fi. Acest lucru ar putea fi valabil pentru orice problemă nerezolvată de matematică. Dar cel puțin experiența noastră a arătat că tipurile de probleme care, cel puțin, s-au dovedit a fi de nerezolvat din axiomele matematice tind să implice infinitate și lucruri foarte mari , lucruri care sunt foarte departe de intuițiile noastre. Și ceva la fel de practic ca P versus NP, cel puțin, ar fi foarte surprinzător pentru mine dacă asta s-ar dovedi a fi fără răspuns folosind axiomele noastre matematice. Dar cine știe? Oh, aceasta este o altă întrebare bună. Teoremele ierarhiei timp și spațiu au variante nedeterministe? Da, ei fac. Cu toate acestea, sunt mult mai greu de dovedit și nu vom acoperi asta. Dar puteți demonstra și că timpul nedeterminist, n cub include în mod corespunzător timpul nedeterminist n pătrat. Nu vei fi responsabil pentru asta. Nu vă faceți griji. Dacă încerci să demonstrezi asta, vei vedea că diagonalarea nu funcționează direct. Și deci trebuie să faci ceva mai chic. Oamenii se întreabă despre ce metodă de reducere să folosească. Din nou, tipurile de reduceri pe care le întâlnim sunt întotdeauna foarte simple. Deci vom lucra doar cu noțiuni foarte slabe de reduceri. Nu este încă interesant, în general, să luăm în considerare tipuri puternice de reduceri, cum ar fi reducerile de timp exponențiale polinomiale sau lucruri de genul acesta. Deci nu este ceva la care oamenii se gândesc prea mult. Adică, pot vorbi despre asta pe larg offline. Dar să presupunem că puterea noastră de reducere este ceva foarte scăzută. Spațiul în jurnal va fi suficient de bun pentru a face toate reducerile din această clasă. Bine, deci să mergem mai departe, atunci. Așadar, aici este problema că vom petrece următoarele 20 de minute și demonstrăm a fi spațiu exponențial complet. Mai întâi trebuie să fac o mică introducere. Deci nu aceasta este problema, dar aceasta este legată de problemă. Deci problema testării dacă două expresii regulate sunt echivalente. Scrieți în expresii regulate, generează ele același limbaj? Deci problema se dovedește a fi de fapt în PSPACE. Așa că nu va fi spațiu exponențial complet. Este de fapt în PSPACE. Nu cred că vom avea... M-am gândit să o prezint în prelegere. Nu este atât de greu de arătat. Dar a durat prea mult timp și nu introduce cu adevărat metode noi. Este un exercițiu bun, de fapt, folosind teorema lui Savitch. Dar poate o vom face în recitare, sau dacă prelegerea se termină în mod miraculos mai devreme, o voi face la sfârșit. Dar nu cred că vom avea timp. Dar aceasta este o configurație pentru problema insolubilă despre care vom vorbi , care este foarte legată. Acum, OK, înainte de a ajunge la asta, așa că dacă am o expresie regulată, voi îmbunătăți expresia noastră regulată într-un mod simplu, permițând exponenți sau exponentiație. Și asta înseamnă că dacă am o expresie regulată R, pot scrie R la k pentru a însemna R concatenat cu sine de k ori. Oricum am folosit asta în mod informal pe tot parcursul , ca atunci când vorbim despre 0 la k, 1 la k. Deci, dacă vom permite formal acest lucru atunci când scriem expresii regulate, în unele cazuri, asta ar putea permite expresiei regulate să fie mult mai mică, mai ales dacă scriem k în binar. Pentru că pot scrie R la milion cu doar câteva simboluri dacă am exponențiație. Dar dacă nu am exponențiație, atunci trebuie să scriu R concatenat cu R de un milion de ori și obțin o expresie mult, mult mai lungă, o expresie exponențial mai lungă dacă nu am acel exponent ca mod de a descrie regula obișnuită. expresii. Și asta va face o mare diferență. Deci, acum, problema echivalenței pentru expresiile regulate cu exponențiere - asta înseamnă săgeata în sus, ceea ce înseamnă -- acum vă ofer două expresii regulate. Dar li se permite să aibă operația de exponențiere în plus față de operațiunile obișnuite standard. Deci, acum, testând dacă două dintre aceste expresii regulate care au exponențiere, acea problemă se dovedește a fi spațiu exponențial complet. Deci, iată problema echivalenței pentru expresiile regulate cu exponențiere. Aceasta este o problemă de spațiu exponențial complet. Și așa cum am subliniat, asta înseamnă că această problemă este imposibil de rezolvat. Deci nu există nicio modalitate, în general, de a rezolva acea problemă în timp polinomial. Asta se dovedește, se știe. Deci vom trece prin reducerea. Cred că va fi ultima noastră reducere a termenului, de a demonstra probleme complete pentru o anumită clasă. Dar fiecare dintre ele are propriul lor lucru care îl face special. Deci, în primul rând, trebuie să arătăm că este în spațiu exponențial. Asta se va baza cu adevărat pe acest alt fapt pe care nu l-am dovedit. Așa că o să trec peste asta foarte repede. Dar partea interesantă este reducerea. Deci, dacă am ceva în spațiul exponențial, pot arăta că îl pot reduce la problema echivalenței pentru expresiile regulate cu exponențiere. OK, argumentând atât de repede partea întâi că suntem în spațiu exponențial, practic, ceea ce faci este să iei cele două expresii regulate pe care vrei să le testezi pentru a vedea dacă sunt echivalente, dar acum au exponențiație. Și ca prim pas, scapi de exponențiere. Doar extindeți lucrurile prin repetarea părților care au exponenții. Și, desigur, așa cum am spus, asta va face expresia în sine mai mare exponențial. Dar acum, rulați algoritmul PSPACE pe acele două expresii exponențial mai mari. Deci, intrarea pe care algoritmul PSPACE este acum exponențială în dimensiunea inițială de intrare, dar este PSPACE în acea intrare mărită. Deci asta vă va oferi un algoritm de spațiu exponențial în dimensiunea inițială de intrare , pentru că l-ați extins pentru a deveni exponențial mai mare, apoi rulați algoritmul PSPACE pe acea problemă extinsă. Deci, asta vă oferă un algoritm de spațiu exponențial pentru această problemă. Dar acum, ceea ce vom face... partea interesantă este reducerea. Deci, având în vedere un anumit limbaj și spațiu exponențial, să zicem, decis de o mașină Turing în acea cantitate de spațiu, de la 2 la n la k, vom da o reducere care mapează a cu această problemă de echivalență. Am înţeles? Acesta este planul. Așa că haideți să ne asigurăm că suntem cu toții împreună în plan înainte de a merge mai departe și de a pune în aplicare acel plan. Am stabilit lucrurile aici, într-un fel, pentru ceea ce vom face. Așa că nu ezitați să puneți o întrebare doar despre plan. Va deveni tehnic. Pentru că, așa cum se face întotdeauna aceste reduceri, este implicată o simulare și trebuie să descrii acea simulare în felul ei. Așa că acum, vom simula, într-un anumit sens, M pe w, decisorul acestui spațiu exponențial, problema A, vom lua M pe w și va trebui cumva să exprimăm faptul că M acceptă w folosind această problemă de echivalență pentru expresii regulate cu exponențiere. Deci fără întrebări? De ce nu mergem mai departe? Am trei diapozitive despre asta, dar sunt cam dense, îmi pare rău să spun. Deci, iată planul ca de obicei. Vom mapa A cu o reducere a timpului polinomial la problema de echivalență pentru expresiile regulate cu exponențiere. Deci, asta înseamnă că va trebui să luăm o intrare, care poate fi sau nu în A și să producem două expresii regulate cu exponențiere, care vor fi echivalente atunci când w este în A. Sau când M acceptă w. Așa că va fi, așa cum sunt întotdeauna aceste lucruri, acestea vor fi în termeni de istorie de calcul pentru M sub w. Dar în acest caz, se va dovedi a fi convenabil să lucrezi cu istoricul de calcul de respingere pentru M pe w. Deci, amintiți-vă, acum avem o mașină Turing M. Este un decident, deci asta înseamnă că ține întotdeauna-- pentru șirurile din limbă, ajunge la o stare Q accept, pentru lucruri care nu sunt în limbaj, ajunge la o stare de respingere Q. Deci, un istoric de calcul de respingere este secvența de configurații prin care trece mașina de la configurația de pornire până când ajunge la o configurație cu o stare de respingere, o configurație de respingere. Și vom face o expresie regulată care să descrie toate șirurile, cu excepția acestuia. Va evita descrierea unui istoric de calcul de respingere pentru M pe w. În caz contrar, va descrie toate șirurile posibile. Acum, dacă M nu respinge w, deci nu există nici un istoric de calcul de respingere - și anume, M acceptă w, apropo. Deci, dacă M acceptă w, nu respinge w, nu are un istoric de calcul de respingere, ce descrie R1? Ei bine, descrie, în acest caz, totul, pentru că nu există nicio istorie de calcul respingătoare. Deci, descrie orice alt șir în afară. Deci, asta înseamnă că descrie toate șirurile, dacă nu există un istoric de calcul de respingere în cazul în care M acceptă w. Deci, ce sugerează că ar trebui să folosim pentru R2? R2 va fi expresia regulată care doar generează toate șirurile. Deci vom testa dacă R1 generează toate șirurile sau nu, ceea ce este același cu a spune M acceptă w sau nu. Deci R2 va fi... Aș dori să spun stea sigma, dar sigma este într-adevăr intrarea în M, iar gamma este alfabetul de bandă pentru M. Deci avem o mulțime de litere grecești cu care să ne jucăm, așa că suntem vom folosi delta pentru alfabetul în care scriem istoriile de calcul. Dacă doriți să vi se reamintească ce este acea delta, un istoric de calcul poate avea un simbol alfabet de bandă pentru M, poate avea un simbol de stare pentru M sau poate au un delimitator pound-- hashtag. Deci, fie un alfabet delta capitală este un simbol al alfabetului pe bandă, fie un stat, ceva care reprezintă un simbol de stat, sau un hashtag. Asta e doar delta. Așa că nu te... Mă simt mereu prost dacă cineva devine confuz de ceva care ar trebui să fie foarte simplu. Nu vă confundați cu stea delta. Acestea sunt doar toate șirurile posibile peste delta alfabetului. OK, deci ce înseamnă R1-- deci treaba mea este să fac R1. R2, ți-am spus deja. R1 trebuie acum să descrie toate acele șiruri, cu excepția istoricului de calcul respingător. Deci, tot ceea ce nu reușește să fie un istoric de calcul respingător - deci eșuează fie pentru că a început greșit, fie pentru că s-a terminat greșit, fie este greșit undeva la mijloc. Și prin greșit, vreau să spun, nu reușește să descrie corect modul în care funcționează mașina dacă sfârșește prin a respinge w. În regulă. Așa că voi descrie toate acele șiruri posibile împărțindu-le în acele trei categorii. Începe greșit, se termină greșit sau undeva calculează greșit pe parcurs. BINE. Deci respingerea istoricului de calcul arată cam așa. Iată configurația de pornire așa cum o imaginăm de obicei. Este o stare de pornire care se uită la primul simbol al intrării și există restul intrării. Așa că lasă-mă să scriu asta. Acesta este un istoric de calcul care respinge acum. Deci prima configurație, a doua și așa mai departe și așa mai departe, până ajungem la un calcul de respingere - configurație de respingere. Acum, pentru comoditate, voi insista că toate aceste configurații au aceeași lungime. Îmi va face viața mai ușoară făcând dovada. Dar de ce pot face asta? Ei bine, o să le iau doar... știi, pentru că, de obicei, te gândești la configurații, ele încep mici pentru că practic au lungimea n, dar asta folosește spațiu exponențial, devin din ce în ce mai lungi. . Să le asociem pe toate cu semifabricate, astfel încât să fie toate de aceeași dimensiune. Deci, așa cum am indicat aici, adăugăm o grămadă de spații libere. Aici vor fi o mulțime de spații libere, pentru a vă asigura că toate au lungimea de la 2 la n la k, care este dimensiunea maximă a unei configurații atunci când aveți atât de mult spațiu. Voi construi... deci practic asta e treaba mea. Voi construi R1 astfel încât să genereze toate acele șiruri. Am scris o căsuță în jurul acelui lucru pe care încerc să-- asta trebuie să fac. Mă va ajuta în diapozitivele viitoare pentru că sunt puțin dense. Când voi desena acest fel de cutie roșiatică, roz în jurul a ceva, înseamnă că voi încerca să descriu toate șirurile, cu excepția acela. Vreau să evit să-l descriu pe acesta, pentru că acesta este istoricul de calcul care respinge, dar vreau să descriu orice altceva. Asta e dorința mea. Așa că iată o verificare înainte de a merge mai departe. Dar putem, de asemenea,... poate ar trebui să răspundem la câteva întrebări, chiar înainte de a lansa înregistrarea. Cum ne descurcăm aici? Deci, este cel care descrie - ei bine, R1 este o expresie regulată. Aici, vorbim despre un... acesta este doar un istoric de calcul obișnuit, dar se termină cu o respingere. Asta e tot. Un istoric de calcul de respingere este doar unul care este puțin diferit la sfârșit. Mașina a ajuns să respingă în loc să accepte. În caz contrar, totul trebuie să fie precizat în conformitate cu regulile mașinii și configurația de pornire. Da, presupuneam o stare de respingere. Da, așa definim de fapt mașinile Turing, în primul rând. Dar cine se ceartă. Da, există o stare de respingere. Cu toții suntem determiniști, corect. De ce avem nevoie de căptușeală? Pentru că vreau să le fac toate de aceeași dimensiune, toate aceste configurații. Asta mă va ajuta mai târziu în ceea ce privește descrierea configurațiilor invalide, a celor care nu sunt configurații legale, configurații de respingere legale. Deci, doar o chestiune de comoditate, dar acceptați-o pentru moment. Vreau doar ca toate aceste configurații să aibă aceeași lungime în istoricul de calcul al respingerii. În caz contrar, nu voi... doar codez acea respingere a istoriei de calcul în acest mod special. Așa că oamenii întreabă despre detaliile unui început prost. Asta urmează să vină. Mai am două diapozitive despre asta. Așa că vă voi spune despre cum le vom face. Deci R bad-start-- aceasta este o întrebare bună-- este R bad-start all-- acestea sunt toate șirurile care nu încep așa. O să vedem într-o secundă. Dar R bad-start sunt toate lucrurile care nu încep cu... ele încep prost. Nu încep cu configurația de pornire. Încep cu alte gunoaie. Avem nevoie de un singur istoric de calcul care respinge? Dar ceilalți? Aceasta este o mașină deterministă, așa că va fi doar... dacă prescriu lungimile așa cum am făcut, va fi doar un singur care respinge istoricul calculelor. Pentru că este determinist, totul va fi forțat de la început. R1 ar trebui să fie nu dintre cei trei? Nu. R1 descrie toate șirurile , cu excepția acestui șir. Prin urmare, capturez toate modurile posibile prin care un șir ar putea să nu fie șirul. Ar putea începe greșit. S- ar putea să greșească pe la mijloc undeva. Așa că trebuie să- i unesc împreună. Pentru că descriu, așa cum cred întotdeauna, negațiile sunt cel mai confuz lucru pentru toată lumea, inclusiv pentru mine. Deci, descriem toate lucrurile care nu sunt acest șir. Încercăm să stăm departe de asta. Vrem să descriem orice altceva. Bine, cred că ar fi mai bine să merg mai departe aici. Avem o mulțime de întrebări. Discutați cu AT. În regulă, înregistrează-te. Cât de mare este acest istoric de respingere a calculelor? Interesant. Există o lecție aici. Am primit o explozie mare de răspunsuri chiar de la început. Totul gresit. Dar apoi cei strălucitori— oamenii cărora le-a luat puțin mai mult timp să se gândească au început să obțină răspunsul corect, adică să ne uităm. Avem alegeri strânse aici, oameni buni, așa că acum trebuie să raportez. Sper că nu trebuie să facem o renumărătoare. OK, haideți băieți. Răspunde sus. 10 secunde. Acest lucru nu este foarte greu. Opriți numărătoarea. Da, cred că ar fi bine să ne oprim la asta, suntem la margine. OK, 3 secunde. Încheiați sondajul. Distribuiți rezultatele. Răspunsul corect este, de fapt, c. De ce este asta? Deoarece fiecare configurație este de la 2 la n la k. Deci, atât spațiu are mașina, spațiu exponențial. Dar cantitatea de timp, care este fiecare -- numărul de configurații va fi cantitatea de timp folosită. Va fi exponențial mai egal decât atât. Deci, va fi 2 la 2 la n al lui k, este câți pași poate rula mașina. Și asta va fi cât de lung ar putea fi istoricul calculelor . Deci este un lucru foarte lung. Și când te gândești la asta, la expresia regulată pe care o generăm, cât de mare este? Expresia obișnuită... din nou, mulți oameni joacă comentariile mele aici. Voturile au fost legale sau nu? BINE. Să ne concentrăm aici. Deci, acesta este de două ori exponențial de mare. Cât de mare este expresia regulată pe care o generăm? Ei bine, asta trebuie produs în timp polinomial, deci este doar polinomial mare. Deci avem această mică expresie obișnuită , relativ vorbind , care este doar de la n la k. Trebuie să descrie toate șirurile, cu excepția acestui șir special, care este de la 2 la 2 la n la k. Deci, într-un sens, acest șir care este legat de acea expresie regulată este de două ori exponențial mai mare decât atât. Și așa ceva prezintă o parte din provocare în realizarea reducerii, în construirea acelei expresii regulate. Deci hai să mergem mai departe și să începem să facem... acestea sunt lucrurile grele. Aici este începutul prost, care este destul de provocator. Chiar și această mică bucată va fi puțin dificil de descris. Tocmai rescriind din diapozitivul anterior. Deci încercăm să facem R1, care generează toate șirurile, cu excepția istoricului de calcul de respingere pentru M pe w. Este în acele trei părți. Chiar acum descriu piesa de început prost. Deci, asta va descrie toate șirurile care nu încep cu acest C1. Așa că lasă-mă să scriu asta aici. Acest lucru va genera toate șirurile care nu încep cu C start sau C1, care este așa cum este specificat. Arata asa. Deci orice șir care nu începe cu aceste simboluri, nu începe exact așa, ar trebui să fie descris prin pornire greșită, acea expresie regulată. Deci, în sine, va fi subdivizat în continuare. Și motivul pentru care nu este atât de greu de înțeles. Am de gând să-- un început prost își va îndeplini scopul spunând, ei bine, orice nu începe în acest fel fie nu începe cu un q0, fie nu are sau nu are un w1 în locul următor sau nu are un w2 pe locul următor. Sau undeva pe parcurs, are un simbol greșit. Fiecare dintre acești tipi va fi despre unul dintre acele simboluri greșit într-un anumit loc. Așa că o să vă arăt cum arată acestea. Așa că acum, îmi voi concentra atenția asupra descrierii tuturor șirurilor, cu excepția acestuia. Toate șirurile care încep cu ceva, cu excepția acestuia. Așa că nu uitați, delta este alfabetul pentru istoriile competiției. Și o notație aici, delta sub epsilon, am mai văzut asta , este că veți adăuga în epsilon ca lucru permis pentru delta. Deci, toate simbolurile, sau epsilon, sunt acum gândite ca un set aici. Și, în plus, va fi convenabil să vorbim despre toate simbolurile din delta, cu excepția unor simboluri. Deci, ca la început, q0. Vreau să vorbesc despre toate simbolurile, cu excepția simbolului q0. Pentru că asta o să folosesc pentru a începe R bad-start. Va fi orice, cu excepția q0. Deci, să vedem cum arată. Deci iată S0, prima parte a începutului nostru prost. O să spună... Încerc să colorez ingredientul activ aici în culoarea roz. Deci delta, cu q0 eliminat, urmat de orice. Așadar, această mică expresie regulată descrie toate șirurile care nu încep cu q0, așa cum am indicat aici. Toate șirurile care nu încep cu q0 sunt așa cum descrie S0. Trebuie să înțelegi asta, pentru că doar se va dezvolta de acolo. Deci, ce vrem să spunem pentru S1? Care vor fi toate șirurile care nu au w1 pe locul doi? Așa că o să scriu asta aici. S1 este ceva în primul rând -- Adică, dacă primul loc a fost greșit, S0 s-a ocupat de asta. Așa că îmi voi păstra viața simplă. Tot ce vreau să fac este să descriu toate locurile în care al doilea simbol este greșit. Și anume, nu este w1. Deci orice în primul rând, ceva în afară de w1 pe următorul loc, și apoi orice după. Toate acestea sunt șiruri care nu au-- [TAIURI AUDIO] Așa că o voi scrie aici așa. Acum, în mod similar, S2 va merge la d, deoarece am exponențiație, să folosim asta pentru comoditate. Delta delta, sau doar delta pătrat. Deci orice pe primele două locuri, apoi nu w2, apoi pe următorul loc și apoi orice. Deci asta va surprinde această parte. Așa că asta fac aceste S-uri și poți să-ți faci cumva ideea. Deci punct, punct, punct. Acest Sn va descrie totul, cu excepția lui wn în acea locație, care va fi de fapt prima locație n plus. Și acum trebuie să continui să fac asta pentru spații libere. Așa că acum, dacă te gândești cu mine, hai să ne uităm cum ar putea merge. Următorul simbol, care sări peste n plus 1 de care m-am ocupat deja, vreau să spun că nu este un simbol gol în această primă locație după introducere. Deci, din nou, descriu aceste non-- aceste șiruri care nu sunt configurația de pornire. Ar putea eșua pentru că nu există un gol unde ar trebui să fie un gol. Să presupunem că fac asta pentru fiecare dintre acești tipi. Asta ar merge. Dar. Dar ce? Gândi. De fapt, aceasta nu va fi o soluție bună pentru noi. Pentru că sunt exponențial multe spații libere aici. Aceasta este o configurație foarte lungă. Și astfel există exponențial multe spații libere. Dacă o fac în acest fel, voi ajunge cu o expresie regulată exponențial de mare. Și asta nu este realizabil în timp polinomial. Deci am o modalitate mai complicată de a obține același efect. Ceea ce este... Nu mă aștept cu adevărat să analizezi pe deplin asta chiar acum, în timp real în prelegere, dar lasă-mă să încerc să te ajut. Ceea ce voi face este să sări peste aceste primele n plus 1 locuri și apoi un număr variabil de locuri, care este indicat de următoarea piesă de aici. Și modul în care funcționează este - acestea sunt toate șirurile de lungime n plus 1 până la sfârșitul configurației. Și pentru a înțelege asta, este aproape puțin prea tehnic să încerci, dar să vedem. Dacă pun delta la 7, acestea sunt toate șirurile de lungime 7. Dar dacă pun delta sub epsilon la 7, dacă vă gândiți la ce înseamnă asta, sunt toate șirurile de lungime între 0 și 7. Pentru că o pot avea fie la fel de epsilon ca variabila mea sau un simbol din delta. Și asta fac aici. Obțin un spațiu de lungime variabilă , distanțier al deltelor, care vor ajunge apoi într-o anumită locație -- o să spun în acel loc. Apoi am un non-blank. Pentru că tot ce trebuie să fac este să descriu șirurile care nu reușesc să aibă un gol undeva în acest interval. Așa că trebuie să sortăm un distanțier variabil în acel loc, unde ar putea fi acel blank lipsă. Deci asta descrie. Dacă nu ai înțeles asta, nu-ți face griji. Acesta este un punct tehnic și puteți încerca să vă gândiți la el offline. Și apoi, la final, voi descrie ce se întâmplă. Descrieți șirurile care nu au un hashtag în acea locație. Așa descriu toate șirurile care nu încep corect. E multă muncă, doar pentru a face piesa aceea mică. Din fericire, următoarele două piese sunt mai ușoare, surprinzător. Puteți sări cu o întrebare, dar poate ar trebui să mă mișc, să continui. Așa că acum voi descrie mișcarea proastă și piesele respinse proaste. Și respingerea greșită generează toate șirurile care nu conțin simbolul q respingere. Deci asta va descrie cu siguranță toate șirurile care nu se termină corect. Și aceasta este pur și simplu delta cu simbolul de respingere q eliminat și apoi orice șir dintre acestea. Sunt toate șirurile care nu au q reject. Deci, asta va descrie toate șirurile care nu se termină cu un q reject, plus câteva alte șiruri nedorite pe parcurs. Dar asta este tot ceea ce nu este niciodată o problemă, să introduci și alte șiruri pe care le-ai putea captura într-o altă parte a expresiei obișnuite despre care știi că sunt șiruri proaste. Vrei doar să te asiguri că nu introduci acel șir unic bun, care este istoricul de calcul de respingere , șir bun. Și, în sfârșit, vom folosi noțiunea de cartiere. S- ar putea să crezi că aceasta este cea mai grea parte, dar de fapt nu chiar atât de grea. Deci acestea sunt toate șirurile care au undeva pe parcurs o încălcare conform regulilor lui M. Vrei să le descrii și pe toate. O să fac asta în ceea ce privește cartierele. Dar cartierele vor fi întinse. Nu mai avem tablou , așa că nu sunt atât de ușor de vizualizat, dar este aceeași idee, cartierul. Deci, acesta este abc și def. Dar acum este un cartier ilegal. def nu rezultă din abc. Dacă toate cartierele sunt legale, atunci întregul calcul este un calcul legitim, cu condiția să înceapă și să se termine corect. Deci, dacă nu este un calcul legitim, trebuie să existe undeva un cartier ilegal. Și voi descrie doar toate șirurile care au un cartier ilegal. Și partea interesantă este că trebuie să descrii - trebuie să plasezi acel separator între abc și def. Deci, acesta este un alt loc în care vom folosi în mod critic exponentiația și faptul că toate configurațiile au aceeași lungime. Asta folosim noi acolo. Știm exact cât de departe este partea de jos a cartierului 2 pe 3 de partea de sus a cartierului 2 pe 3. Așa că o să facem unire peste toate cartierele ilegale 2 câte 3. Setarile de cartier, ar trebui sa spun. Și există doar un număr fix din acestea, din același motiv pe care l-am avut în teorema Cook-Levin. Există un număr fix de acestea, în funcție de mașină. Și acum vom avea, să zicem, vom începe cu orice. Iată partea de sus a cartierului. Aici este separatorul care separă partea de sus de jos în cele două configurații consecutive, iată Ci merge C i plus 1 în istoricul meu de calcul. Și apoi după acel separator, am pus în a doua parte a cartierului, care este def. Trebuie să vă simțiți confortabil cu modul în care am prezentat aceste alte reduceri până acum, pentru a obține cu adevărat acest lucru. Oricum, cred că suntem la pauză. Așa că putem răspunde doar la întrebări în timpul pauzei, dacă aveți. Și, altfel, ne vedem în cinci minute. În descrierea mea de aici... lasă-mă să scot asta. Pentru o respingere proastă, se pare că fac ceva exagerat și poate că fac ceva greșit aici. Descriu toate șirurile care nu au un refuz nicăieri. Dar atâta timp cât nu descriu istoricul legitim de respingere a calculelor, descriu toate șirurile care nu se termină corect, sunt bine. Aș putea depune mai mult efort pentru a mă asigura că descriu aici doar ultima configurație ca neavând respingerea. Dar asta ar fi doar mai multă muncă și nu trebuie să fac asta. Așa că poate ar fi bine să înțeleg de ce este suficient, ceea ce am descris aici și nu- mi va crea probleme. Primesc o notă de la unul dintre AT-ul meu, Thomas, care spune că noțiunea „rău” poate este confuză, pentru că rău sună ca respingere. Da. Vreau să spun rău în sensul că nu descriu o istorie legală de calcul . Dacă vă puteți gândi la alt nume, sunt bucuros să îl schimb pentru anii următori. Prea târziu deocamdată. Dar, da. Nu vreau să spun că respingerea, vreau să spun că este... ei bine, nu știu care este termenul potrivit. Ilegal? Sau... Nu sunt sigur ce bun... Cum sunt definite cartierele aici? Care este tabloul aici? Cred că trebuie să te gândești la asta după prelegere. Dar tabloul, vă puteți gândi la tabloul acum aici doar scris liniar. Există toate rândurile acum, în loc să fie bine organizate într-un tabel. Ele apar consecutiv, pentru că doar încerc să descriu... Trebuie să o fac pentru a descrie un șir, indiferent dacă expresia mea regulată nu are sens să mă gândesc. Adică, poți să-l pliezi într-un tablou, dacă vrei. Și apoi abc și def se vor alinia. Dar aici, dacă te gândești la ele scrise consecutiv, exact așa de departe ajung să fie. Există doar polinomial multe cartiere ilegale? De aceea m-am cam corectat. Nu vorbim despre cartiere ilegale, pentru că numărul de cartiere din această imagine este mare. Dar numărul de setări de vecinătate, modul de a seta aceste valori la abc, def. Adică acestea sunt simboluri care pot apărea într-o configurație a mașinii. Există doar un număr fix de simboluri care pot apărea aici, care depind de definiția mașinii. Deci nu este doar polinom. Există un număr constant de aceste lucruri, care depinde doar de mașină. Așa că trebuie să te gândești la ce se întâmplă. Sunt multe... acestea sunt multe pe tobogan. Istoric prost pentru respingere. Este o istorie proastă pentru respingere, sugerează cineva. Da, este o istorie proastă. Știri false. Poate ar trebui să fim falși. Fals ar fi un termen bun. Nu, asta nu e atât de bine. Nu știu. Da, 2 cu 3. Motivul 2 cu 3, este corect... Cineva întreabă de ce 2 cu 3. 2 cu 3 este exact dimensiunea de care trebuie să spui asta, dacă toate cartierele 2 cu 3 sunt corecte peste tot în calcul istorie, atunci întreaga istorie va fi în concordanță cu regulile lui M. Va fi o reprezentare legală a unui calcul al lui M. Deci, dacă șirul, care se presupune că este un istoric de calcul, are o vecinătate proastă undeva, rău 2 cu 3 cartier undeva, atunci... ei bine, dacă nu este un istoric de calcul legal, trebuie să aibă un cartier prost, cartier 2 cu 3 undeva. OK, hai să mergem mai departe. Pentru că cred că nu avem timp aici. Cronometrul nostru este activat. Oricum vom schimba vitezele acum. Deci, dacă te-ai pierdut puțin în dovada anterioară, vom vorbi despre ceva diferit. Și în unele privințe, puțin, cred că puțin mai ușor, puțin mai tehnic. Și asta e despre oracole. Ce sunt oracolele? Oracolele sunt un lucru simplu. Dar sunt un concept util din mai multe motive. Mai ales pentru că ne vor spune ceva interesant despre metode, care poate sau nu poate fi util pentru a demonstra întrebarea P versus NP, când într-o zi cineva speră că va face asta. Ce este un oracol? Un oracol este informații gratuite pe care o vei oferi unei mașini Turing, care ar putea afecta dificultatea de a rezolva probleme. Și modul în care vom reprezenta aceste informații gratuite este că vom permite mașinii Turing să testeze calitatea de membru într-o limbă specificată, fără a percepe taxe pentru munca implicată. Îți voi permite să ai orice limbă, o limbă A. Și să spunem că o mașină Turing cu un oracol pentru A este scrisă astfel, M cu un superscript A. Este o mașină care are o cutie neagră care poate răspunde la întrebări . Un șir, pe care aparatul îl poate alege, este în A sau nu? Și primește răspunsul într-un singur pas, efectiv gratuit. Deci, vă puteți imagina, în funcție de limba pe care o furnizați mașinii, că poate fi sau nu util. De exemplu, să presupunem că vă dau un oracol pentru limba SAT. Asta poate fi foarte util. Ar putea fi foarte util pentru a decide SAT, de exemplu. Pentru că acum nu trebuie să treci printr-o căutare de forță brută pentru a rezolva SAT. Întrebați doar oracolul. Și oracolul va spune, da, este satisfăcător, sau nu, nu este satisfăcător. Dar poți folosi asta pentru a rezolva rapid și alte limbi. Pentru că orice puteți face în NP, puteți reduce la SAT. Deci, o puteți converti într-o întrebare SAT, pe care o puteți trimite apoi către oracol, iar oracolul vă va spune răspunsul. Cuvântul „oracol” transmite deja ceva magic. Nu ne vom preocupa cu adevărat de funcționarea oracolului, așa că nu mă întrebați cum funcționează oracolul sau cu ce corespunde în realitate. Nu este. Este doar un dispozitiv matematic care oferă aceste informații gratuite mașinii Turing, ceea ce îi permite să calculeze anumite lucruri. Se dovedește a fi un concept util. Este folosit în criptografie, unde vă puteți imagina că oracolul ar putea furniza factorii unui număr sau parola unui sistem sau ceva de genul. Informații gratuite. Și atunci ce poți face cu asta? Deci aceasta este o noțiune care apare și în alte locuri. Dacă avem un oracol, ne putem gândi la toate lucrurile pe care le puteți calcula în timp polinomial în raport cu acel oracol. Așa că asta e ceea ce noi... terminologia pe care o folosesc de obicei oamenii se numește uneori relativism, sau calcul relativ la a avea aceste informații suplimentare. Deci P cu un oracol A este tot limbajul pe care îl puteți decide în timp polinomial dacă aveți un oracol pentru A. Să vedem. Da. Cineva mă întreabă, este într-adevăr gratuit sau costă o unitate? Chiar și doar configurarea oracolului și notarea întrebării către oracol vă va lua un număr de pași. Deci nu veți putea face un număr infinit de apeluri oracol în timp zero. Deci încărcarea cu un pas sau zero pași, nu va face diferența. Pentru că mai trebuie să formulezi întrebarea. După cum am subliniat, P cu un oracol SAT - deci toate lucrurile pe care le faci în timp polinomial cu un oracol SAT includ NP. Poate include și alte chestii? Sau este egal cu NP? Ar fi fost o întrebare bună de check-in, dar nu am de gând să întreb asta. De fapt, se pare că conține și alte lucruri. Pentru că co-NP este, de asemenea, conținut în P, având în vedere un oracol SAT. Pentru că răspunsul oracolului SAT este atât da, cât și nu, în funcție de răspuns. Deci, dacă formula este nesatisfăcătoare, oracolul va spune nu, nu este în limbaj. Și acum puteți face și complementul problemei SAT . Problema de nesatisfăcibilitate. Deci, puteți face toate co-NP în același mod. De asemenea, puteți defini NP în raport cu un oracol. Deci, toate lucrurile pe care le puteți face cu o mașină Turing nedeterministă, unde toate ramurile au acces separat. Și pot pune mai multe întrebări, de altfel, oracolului. Independent. Să facem un alt exemplu, un pic mai provocator. Limbajul MIN-FORMULA, pe care sper să-l amintești din teme. Deci, acestea sunt toate formulele care nu au o formulă echivalentă mai scurtă. Sunt minime. Nu puteți face o formulă mai mică care să fie echivalentă care vă oferă aceeași funcție booleană. Așa că ați arătat, de exemplu, că acea limbă este în spațiul P, după cum îmi amintesc. Și au mai fost câteva... ați avut alte două probleme legate de limba respectivă. Complementul problemei MIN-FORMULA este în NP cu un oracol SAT. Deci, gândiți-vă la asta o secundă și apoi vom vedea de ce. Iată un algoritm, în NP cu un algoritm oracol SAT. Deci, cu alte cuvinte, acum vreau să implementez acea strategie, despre care am susținut că problema temelor nu era legală. Dar acum că am oracolul SAT, va face posibil acolo unde înainte nu era posibil. Deci, să înțelegem ce vreau să spun prin asta. Dacă încerc să fac formulele non-minimale, și anume formulele care au o formulă echivalentă mai scurtă. Voi ghici acea formulă mai scurtă, numită psi. Provocarea de dinainte a fost testarea dacă acea formulă mai scurtă era de fapt echivalentă cu phi. Pentru că acest lucru nu este în mod evident realizabil în timp polinomial. Dar problema echivalenței pentru formule este o problemă co-NP. Sau dacă îți place să te gândești la asta în alt mod, orice formulă de echivalență este o problemă NP, pentru că trebuie doar să-- martorul este misiunea cu care nu sunt de acord. Deci două formule sunt echivalente dacă nu sunt niciodată de acord. Și deci asta e o problemă de co-NP. Un oracol SAT poate rezolva o problemă co-NP. Și anume, echivalența celor două formule, formula de intrare și cea pe care ați ghicit-o acum determinist. Și dacă se dovedește că sunt echivalente, o formulă mai mică este echivalentă cu formula de intrare, știți că formula de intrare nu este minimă. Și astfel poți accepta. Și dacă obține formula greșită, se dovedește a nu fi echivalentă, atunci respingi pe acea ramură a non-determinismului, la fel cum am făcut înainte. Și dacă formula a fost într-adevăr minimă, niciuna dintre ramuri nu va găsi o formulă echivalentă mai scurtă. Deci, de aceea această problemă aici este în NP cu un oracol SAT. Așa că acum vom încerca să investigăm asta pe... ne apropiem de sfârșitul prelegerii. Ne vom uita la probleme precum, ei bine, să presupunem că compar P cu un oracol SAT și NP cu un oracol SAT. Ar putea fi aceleași? Ei bine, există motive să credem că acestea nu sunt la fel. Dar ar putea exista vreun A unde P cu A oracol este la fel cu NP cu un oracol A? Se pare că nu, dar de fapt este greșit. Există o limbă, există limbi pentru care NP cu acel oracol și P cu acel oracol sunt exact la fel. Și acesta este de fapt un interes - nu este doar o curiozitate, de fapt are relevanță pentru strategiile de rezolvare a P versus NP. Sper că voi putea avea timp să ajung. Ne putem gândi la un oracol ca o masă hash? Cred că hashingul este oarecum diferit în spirit. Înțeleg că există o oarecare asemănare acolo, dar nu văd că hashingul este o modalitate de a găsi un fel de nume scurt pentru obiecte, care are o varietate de scopuri diferite de ce ai putea dori să faci asta. Deci chiar nu cred că este la fel. Să vedem, o întrebare oracolă, OK, să vedem. Cum folosim oracolul SAT pentru a rezolva dacă două formule sunt echivalente? OK, asta se întoarce la acest punct. Cum putem folosi un oracol SAT pentru a rezolva dacă două formule sunt echivalente? Ei bine, putem folosi un oracol SAT pentru a rezolva orice problemă NP, deoarece este reductibilă la SAT. Cu alte cuvinte-- P cu un oracol SAT conține tot NP, așa că trebuie să vă asigurați că înțelegeți acea parte. Dacă aveți problema clicei, puteți reduce. Dacă vă dau o problemă de clic, care este o problemă NP, și vreau să folosesc oracolul pentru a testa dacă formula -- dacă graficul are o clică, reduc acea problemă la o problemă SAT folosind teorema Cook-Levin. Și știind că o clică de o anumită dimensiune va corespunde cu o formulă care este satisfăcătoare, acum pot să întreb oracolul. Și dacă pot face probleme NP, pot face probleme co-NP, deoarece P este o clasă deterministă. Chiar dacă are un oracol, este totuși determinist. Poate inversa răspunsul. Ceva pe care mașinile nedeterministe nu pot face neapărat. Deci nu știu, poate asta e... hai să mergem mai departe. Deci există un oracol în care P la A este egal cu NP la A, care pare cam uimitor la un anumit nivel. Pentru că aici este un oracol în care non-determinismul-- dacă vă dau acel oracol, non-determinismul nu ajută. Și este de fapt o limbă pe care am văzut-o. Este TQBF. De ce este asta? Ei bine, iată toată dovada. Dacă am NP cu un oracol TQBF. Să verificăm doar fiecare dintre acești pași. Susțin că pot face asta cu o mașină spațială polinomială nedeterministă, care nu mai are un oracol. Motivul este că, dacă am spațiu polinomial, pot răspunde la întrebări despre TQBF fără a avea nevoie de un oracol. Am suficient spațiu doar pentru a răspunde direct la întrebare . Și folosesc non-determinismul meu aici pentru a simula non-determinismul mașinii NP. Deci, de fiecare dată când mașina NP se ramifică nedeterminist, la fel și eu. De fiecare dată când una dintre acele ramuri pune oracolului o întrebare TQBF, îmi fac algoritmul de spațiu polinomial pentru a rezolva singur întrebarea. Dar acum NPSPACE este egal cu PSPACE prin teorema lui Savitch. Și pentru că TQBF este complet PSPACE, din același motiv pentru care un oracol SAT îmi permite să fac orice problemă NP, o problemă TQBF îmi permite să fac orice problemă PSPACE. Și astfel obțin NP conținut în P pentru un oracol TQBF. Și, bineînțeles, obții imediat reținerea inversă . Deci sunt egali. Ce legătură are asta cu... cineva a spus... Ei bine, eu doar... Nu vreau să rămân fără timp. Așa că voi răspunde la orice întrebări la sfârșit. Ce legătură are asta cu problema P versus NP? OK, deci aceasta este o conexiune foarte interesantă. Amintiți-vă, tocmai am arătat printr-o combinație dintre prelegerea de azi și prelegerea de ieri, și cred că prelegerea de joi , că această problemă, această problemă de echivalență, nu este în PSPACE și, prin urmare, nu este în P și, prin urmare, este insolubilă. Asta tocmai am făcut. Am arătat că este completă pentru o clasă, care se dovedește în afara lui P, probabil mai mare decât P. Acesta este genul de lucru pe care ne-am dori să putem face pentru a separa P și NP. Am dori să arătăm că o altă problemă nu este în P. O altă problemă este insolubilă. Și anume SAT. Dacă am putea face SAT, atunci suntem buni. Am rezolvat P și NP. Deci avem deja un exemplu de a putea face asta. Am putea folosi aceeași metodă? Ceea ce oamenii au încercat să facă în urmă cu mulți ani, pentru a arăta că SAT nu este în P. Deci, care este metoda cu adevărat? Curajul acestei metode vine într-adevăr din ierarhia de acolo. Acolo dovedeai de fapt probleme care sunt grele. Întâmpinați această problemă prin construcția ierarhiei care se poate dovedi în afara PSPACE. Și în afara lui P. Asta e o diagonalizare. Și dacă te uiți cu atenție la ce se întâmplă acolo, așa că vom spune, nu, nu vom fi capabili să rezolvăm SAT, să arătăm SAT-urile în afara lui P în același mod. Și motivul este, să presupunem că am putea. Ei bine, teoremele de ierarhie sunt dovedite prin diagonalizare. Ceea ce vreau să spun prin asta este că în teorema ierarhiei, există o mașină D, care simulează o altă mașină, M. Pentru a ne aminti ce se întâmplă acolo, amintiți-vă că am făcut o mașină care își va face limbajul diferit de limbaj. a fiecărei mașini care funcționează cu mai puțin spațiu sau cu mai puțin timp. Așa a fost definit D. Vrea să se asigure că limbajul său nu poate fi făcut în mai puțin spațiu. Deci se asigură că limbajul său este diferit. Simulează mașinile care folosesc mai puțin spațiu și face ceva diferit de ceea ce fac ei. Ei bine, acea simulare... dacă am avea un oracol, dacă încercăm să arătăm că dacă oferim atât un simulator, cât și mașina care este simulată cu același oracol, simularea funcționează în continuare. De fiecare dată când mașina pe care o simulați pune o întrebare, simulatorul are același oracol, așa că poate pune, de asemenea, aceeași întrebare și poate face în continuare simularea. Deci, cu alte cuvinte, dacă ați putea dovedi că P este diferit de NP folosind practic o simulare, ceea ce este o diagonalizare , atunci ați putea demonstra că P este diferit de NP pentru fiecare oracol. Deci, dacă puteți dovedi P diferit de NP printr-o diagonalizare, asta ar dovedi imediat că P este diferit de NP pentru fiecare oracol. Pentru că argumentul este transparent pentru oracol. Dacă doar puneți oracolul jos, totul funcționează în continuare. Dar-- aici este marele dar, nu poate fi că-- știm că PA este-- știm că acest lucru este fals. Doar expunem un oracol pentru care sunt egali. Nu este cazul că P este diferit de NP pentru fiecare oracol. Uneori sunt egali, pentru unele oracole. Deci, ceva care este în principiu o diagonalizare foarte simplă, ceva care se află în centrul său este o diagonalizare, nu va fi suficient pentru a rezolva P și NP. Pentru că altfel s- ar dovedi că sunt diferiți pentru fiecare oracol. Și uneori nu sunt diferite, pentru unele oracole. Aceasta este o perspectivă importantă pentru ce fel de metodă nu va fi adecvată pentru a demonstra P diferit de NP. Și asta apare tot timpul. Oameni care propun soluții ipotetice pe care încearcă să le arate P diferit de NP. Unul dintre primele lucruri pe care oamenii le întreabă este, ei bine, ar mai funcționa acel argument dacă ai pune un oracol acolo. Adesea o face, ceea ce arată că a existat un defect. Oricum, ultima înregistrare. Deci acesta este doar un mic test al cunoștințelor tale despre oracole. De ce nu... în minutul care ne rămâne aici. Să spunem 30 de secunde. Și apoi vom analiza asta și am să subliniez care dintre ele sunt corecte. O, băiete, suntem peste tot pentru asta. Îți plac pe toate. Ei bine, bănuiesc că cele care sunt false sunt ușor în urmă. OK, hai să încheiem. Ți-am acordat suficient timp acolo? Distribuiți rezultatele. Deci, de fapt... Da, deci a avea un oracol pentru complement este la fel cu a avea un oracol. Deci acest lucru este cu siguranță adevărat. NP SAT egal cu conP SAT, nu avem niciun motiv să credem că ar fi adevărat și nu știm că este adevărat. Deci B nu este o alegere bună și acesta este cel mai în urmă aici. MIN-FORMULA, ei bine, este în PSPACE și orice în PSPACE se poate reduce la TQBF, deci acest lucru este cu siguranță adevărat. Și același lucru pentru NP cu TQBF și conNP cu TQBF. Odată ce ai TQBF, vei primi tot PSPACE. Și așa cum am subliniat, și acest lucru va fi egal. Deci de ce nu ne oprim aici. Și cred că acesta este ultimul meu slide. Oh, nu, aici este rezumatul meu. Aceasta este ceea ce am făcut. Și vă voi trimite pe toți pe drumul vostru. Cum arată interacțiunea dintre mașina Turing și oracol? Da, nu am definit exact cum interacționează mașina cu un oracol. Vă puteți imagina că aveți o bandă separată în care scrie întrebarea oracol și apoi intră într-o stare specială de interogare. Puteți să o formalizați cum doriți. Toți vor fi... orice mod rezonabil de a-l oficializa va veni cu aceeași noțiune în cele din urmă. Arată că P cu un oracol TQBF este egal cu PSPACE. Da, este corect. Buna observatie. De ce avem nevoie ca oracolul să fie TQBF? Nu ar funcționa și SAT pentru că ar putea rezolva orice problemă NP? Deci vă întrebați, P cu un oracol SAT este egal cu NP cu un oracol SAT? Necunoscut. Și se crede că nu este adevărat, dar nu avem un motiv convingător pentru asta. Nimeni nu are idee cum să facă asta. Pentru că, de exemplu, am arătat că complementul MIN-FORMULA este în NP cu un oracol SAT. Dar nimeni nu știe cum să facă... pentru că există un fel de două niveluri de non-determinism acolo. Există ghicirea formulei mai mici și apoi ghicirea din nou pentru a verifica echivalența. Și chiar nu pot fi combinate, pentru că unul dintre ele este un fel de ghicire de tip existent, celălalt este un fel de ghicire pentru toate tipurile. Nimeni nu știe cum să facă asta în timp polinomial cu un oracol SAT. În general, credeau că nu sunt la fel. La check-in, de ce a fost B fals? B este aceeași întrebare. NP cu un oracol SAT este egal cu conp cu un oracol SAT? Nu spun că este fals, pur și simplu nu se știe că este adevărat. Nu rezultă din nimic din ceea ce am arătat până acum. Și cred că ar fi ceva care... ei bine, cred că nu implică imediat vreo problemă deschisă celebră. Nu m-aș aștepta neapărat să știi că este o problemă nerezolvată, dar este. Am putea avea oracole pentru limbajul indecidabil? Absolut. Ar fi de ajutor? Ei bine, dacă încerci să rezolvi o problemă indecidabilă, ar fi de ajutor. Dar oamenii studiază asta. De fapt, conceptul original de oracole a fost prezentat, a fost derivat în teoria computabilității. Și o notă secundară, puteți vorbi despre reductibilitate. Nu, nici nu vreau să merg acolo. Prea complicat. Ce nu se știe că este adevărat? Ceea ce nu se știe că este adevărat este că NP cu un oracol SAT este egal cu coNP cu un oracol SAT sau este egal cu P cu un oracol SAT. Nu se știe nimic în afară de relațiile evidente dintre aceștia. Toate acestea sunt necunoscute și pur și simplu nu se știe că sunt adevărate sau false. Este NP cu un oracol SAT egal cu NP? Probabil ca nu. NP cu un oracol SAT, în primul rând, conține conNP. Pentru că este și mai puternic. Am subliniat că P cu un oracol SAT conține coNP. Și astfel NP cu un oracol SAT va fi cel puțin la fel de bun. Și așa va conține coNP. Și așa, probabil că nu va fi egal cu NP decât dacă se întâmplă lucruri șocant de neașteptate în lumea noastră complexă.