[SCRÂTÂT][FOȘIT][CLIC]
ERIK DEMAINE: Astăzi vom acoperi
, într-o singură prelegere,
un întreg domeniu, care
este complexitatea computațională.
Este un fel de--
întâlnește algoritmii
într-un mod interesant, adică
algoritmii sunt în principal
despre a arăta cum să
rezolvi bine problemele
și să arăți că poți
rezolva bine o problemă.
Și complexitatea computațională
se referă mai mult la
marginea inferioară, demonstrând că
nu poți dovedi --
nu poți rezolva o
problemă foarte bine,
nu poți găsi un
algoritm bun pentru a o rezolva.
Am văzut puțin despre
limitele inferioare cu câteva prelegeri
în urmă, dovedind căutarea și
sortarea limitelor inferioare
într-un
model de arbore de decizie cu ramificare mărginită.
Dar acestea sunt noțiuni mult mai puternice
despre răutate.
Nu este vorba despre n față de n
log n sau constantă față de log n.
Este vorba despre polinom
versus exponențial,
care a fost genul
de model de pâine și unt
din această clasă.
Polinom este un
timp bun de rulare
și ne
străduim mereu pentru asta.
Exponențialul este de obicei
destul de banal de obținut.
Și așa că vom vorbi
despre unele diferite-- se
numesc
clase de complexitate
care vorbesc despre această
problemă și despre diferite moduri
de a dovedi duritatea.
Aceasta este o
prelegere la nivel înalt,
așa că nu va
fi de așteptat
să puteți dovedi duritatea.
Dar veți obține o aromă
a cum este,
iar acest lucru se va transforma frumos
în alte cursuri ulterioare,
adică... suntem aproape la
sfârșitul anului 006,
așa că firesc să vorbim despre ce
alte lucruri ați putea studia.  .
Un rezultat pe care îl vom demonstra astăzi
este că majoritatea problemelor
nu au, de fapt, un algoritm, ceea ce
este oarecum șocant
și multe alte lucruri distractive.
Deci, să începem
cu noțiunea de P.
Acesta este mulțimea tuturor problemelor
rezolvabile în timp polinomial.  Am
vorbit despre
ce înseamnă timpul polinomial
o strânsă ultima prelegere.
Amintiți-vă doar că
timpul polinom
înseamnă polinom în
dimensiunea problemei, pe care îl voi desemna n
aici, numărul de
cuvinte din intrarea dvs.
OK, deci acestea sunt problemele
care pot fi rezolvate eficient.
P este mulțimea tuturor acestora.
Și spre contrast, EXP este
setul tuturor problemelor rezolvabile
în timp exponențial.
Sunt problemele rezolvabile
în timp exponențial.
Exponențial aici
înseamnă ceva de genul 2
la n la constantă.
Aceasta este o
definiție rezonabilă a exponențialului,
deci doar exponențiarea
acestui - a polinomului.
Deci, așa cum v-ați putea aștepta, majoritatea...
fiecare problemă despre care am
vorbit în această clasă
până acum poate fi rezolvată în
timp exponențial destul de ușor.
Și algoritmii, într-
un anumit sens, se referă la
distingerea acestor două,
care probleme sunt în P
versus sunt, de exemplu, EXP minus P.
Așa că, pentru a oficializa
puțin acest lucru,
voi face
o imagine, ceea ce
este puțin o
simplificare.  de realitate,
dar pentru scopurile
acestei clase va fi suficient
și cred că este un
mod cu adevărat util
de a gândi la lucruri, și anume să
ai o axă mare pentru--
o singură axă pentru, cât de
grea este problema ta,
care este  dificultate in a-ti
rezolva problema?
Și vreau să fiu sigur că plec,
așa că cele mai ușoare
probleme sunt aici.
Și fiecare problemă este
un punct pe această axă.  Cele
mai grele probleme sunt chiar mai
jos.
Și vreau să mă asigur că las
suficient spațiu pentru toate lucrurile la
care țin.
Deci P, voi
numi acest segment din față.
Și apoi voi
avea un lucru mai mare
pentru timp exponențial.
Deci, acesta este doar pentru a spune că
P este imbricat în interiorul EXP.
Fiecare problemă care poate fi
rezolvată în timp polinomial
poate fi rezolvată și
în timp exponențial,
deoarece polinomul este mai mic
sau egal cu exponențial.
Acestea sunt doar limite superioare.
A fi EXP înseamnă că ești
undeva de la această linie
la stânga.
A fi în P înseamnă că ești
undeva din această linie
la stânga, în ceea ce
privește dificultatea.
Dar în mod formal, am scrie
P este conținut în EXP ca mulțimi.
De fapt, se știe că sunt
diferiți unul de celălalt.
Există probleme care pot fi
rezolvate în timp exponențial care
nu pot fi rezolvate
în timp polinomial.
De exemplu... O voi
pune aici, sigur.
De exemplu, n de n șah
este în timp exponențial,
dar nu în timp polinomial.
Deci, care este
problema n by șah?
Aceasta este, vă dau
o tablă de șah n cu n
și
vă descriu o poziție.
Aici sunt toate
piesele albe.
Aici sunt toate
piesele negre.
Puteți avea un număr arbitrar
de regine și episcopi și pioni
de fiecare culoare,
desigur, până la n
pătrat dintre ei, astfel încât să
nu se suprapună.
Și vreau să știu,
câștigă albul din această poziție?  Să
zicem că este alb să te miști.
Poate albul să câștige?
Și această problemă poate fi
rezolvată într-un timp exponențial
prin explorarea întregului
arbore al tuturor jocurilor posibile.
Dar nu poate-- dar poți
demonstra că nu poate fi rezolvată
în timp polinomial.
Deci ăsta e un exemplu frumos.
Un exemplu mai pozitiv
, ca să spunem așa,
este
detectarea ciclului negativ al greutății.
Bănuiesc că este literalmente negativ,
dar este moral pozitiv.
Detectarea ciclului de greutate negativă
este următoarea problemă.
Vă dau un grafic, un
grafic direcționat cu ponderi
și vreau să știu,
are un ciclu de greutate negativ
, da sau nu?
Și această problemă este în?
PUBLIC: P.
ERIK DEMAINE: P, pentru că am
văzut un algoritm de timp polinomial
pentru asta.
Rulați Bellman-Ford
pe un grafic augmentat.
Deci acesta este un exemplu de
problemă pe care știm să o rezolvăm.
Toată această clasă
este plină de exemple pe
care știm să le
rezolvăm în timp polinomial.
Dar acesta este unul frumos, non-trivial
și succint de exprimat.
Este, de asemenea, un exemplu
de problemă de decizie.
O mulțime de-- practic toate
problemele despre care voi vorbi astăzi
sunt probleme de decizie, așa cum am
vorbit despre ultima clasă,
adică răspunsul
este doar da sau nu.
Poate albul să câștige din această
poziție, da sau nu?
Există un
ciclu negativ al greutății, da sau nu?
Tetris îl putem
formula și ca o problemă.
Aceasta este o versiune de
Tetris pe care am putea-o numi
Tetris informația perfectă.  Să
presupunem că îți dau
o placă Tetris.
Are niște gunoi rămase
din jocul tău trecut,
sau poate a început așa.
Și vă dau secvența de
n piese care urmează să vină.
Și vreau să
știu, pot supraviețui
acestei secvențe de n piese?
Puteți plasa fiecare
dintre aceste piese pe măsură ce
cad astfel încât să
nu revărsați niciodată partea de
sus a tablei
pe o tablă n cu n?
Această problemă poate fi rezolvată
în timp exponențial.
Dar nu știm dacă poate
fi rezolvată în timp polinomial.
Vom vorbi
mai mult despre asta într-o clipă.
Este o problemă care
foarte probabil nu este în P,
dar nu
o putem dovedi încă.
Bine, deci mai există
o altă clasă pe care
vreau să o definesc în acest moment.
Și vom ajunge
și la al patrulea.
Dar R este clasa
tuturor problemelor care
pot fi rezolvate în timp finit.
R înseamnă finit.
R înseamnă
recursiv, de fapt.
Aceasta este o noțiune
a Bisericii de la
începutul calculului.
După cum știm, scriem
algoritmi recursivi pentru a rezolva probleme.
La început, acesta a
fost singurul mod de a face asta.
Acum avem alte
moduri cu bucle.
Dar toate sunt efectiv
recursive în cele din urmă.
Deci R reprezintă toate problemele
care pot fi rezolvate
în timp finit pe orice computer.
Deci, foarte general,
ar trebui să includă
tot ce ne pasă.
Și este mai mare decât
EXP, dar include
probleme care necesită
timp dublu exponențial sau orice altceva.
Așa că voi desena o regiune
pentru R. Deci totul--
include P. Include EXP.
Și deci avem și
izolare, dar nu
egal cu R. Există, desigur,
multe clase între ele.  Ai
putea vorbi
despre probleme care
iau timp exponențial dublu A
și care ar avea ceva
la mijloc aici.
Sau mai sunt...
între P și EXP
există o mulțime de
lucruri diferite.
Vom vorbi despre unul dintre ei.
Dar înainte de a ajunge la
partea mai fină a lucrurilor,
permiteți-mi să vorbesc în special despre
R. Deci avem un exemplu frumos,
noi fiind
teoria complexității computaționale --
sau cred că aceasta se numește de obicei doar
informatică teoretică --
are o problemă.
Și dacă ești interesat
de asta, poți lua 6041,
cred.
Asta nu sună corect.
Asta e o probabilitate.
O să vină la mine.
Avem o
problemă explicită care nu este în R.
Deci această clasă a fost vorba
despre probleme care
sunt în P. Aveți numărul?
AUDIENTĂ: 6045.
ERIK DEMAINE: 6045, mulțumesc.
Este atât de aproape de această clasă.
Sau este atât de aproape de 6046,
care este succesorul natural
al acestei clase.
Deci în 6045 vorbim despre asta.
Deci această clasă se
referă la probleme care
sunt în P, ceea ce este foarte ușor.
Dar, de fapt, există
probleme dincolo de R.
Și iată o
astfel de problemă, pe care
nu o vom demonstra aici astăzi.
Este nevoie de o
prelegere întreagă pentru a demonstra acest lucru.
Având în vedere un program de calculator, se
oprește vreodată?  Se
termină vreodată?
Acesta ar fi un lucru grozav
dacă am ști cum să rezolvăm.
Practic este un
detector cu buclă infinită.
Dacă problema ta
nu se oprește, atunci
are o
buclă infinită de un fel.
Și ați dori să
spuneți utilizatorului dvs., hei,
aveți o eroare în program.
Deci, aceasta este o parte
a detectării erorilor.
Și este imposibil.
Nu există un algoritm
care să
rezolve întotdeauna toate intrările
la această problemă.
Poate că având în vedere un program care,
să zicem, are 0 linii de cod, ar
putea rezolva asta.
Spune, da, acela se
termină.
Și poate puteți detecta
tipuri simple de bucle infinite.
Deci sunt niște intrări,
niște programe de calculator pe
care le-ai putea detecta.
Dar nu există un singur algoritm
care să rezolve toate intrările.
Aceasta este un fel de veste tristă.
Numim astfel de probleme
incalculabile.
Acesta este doar un alt
cuvânt pentru a nu fi în R.
OK, iar următorul lucru pe care aș
dori să-l fac
este să vă demonstrez
că majoritatea
problemelor de decizie sunt necalculabile
sau sunt dovezi de schiță.
Așa că nu uitați,
problemele de decizie sunt probleme la care
răspunsul este doar da sau nu.
Acesta este un tip foarte special
de problemă.
Și nici acestea, aproape toate
, nu pot fi rezolvate.
Așa că oprirea este un exemplu
de problemă pe care o dorim, pe care
nu o putem rezolva.
Toată această clasă, acest 006, este
despre probleme pe care le putem rezolva.
Dar astăzi am să
vă arăt că, de fapt, aceștia
sunt în minoritate.
Majoritatea problemelor
nu pot fi calculate.
Acest lucru este foarte ciudat și,
de asemenea, puțin deprimant.
Așa că vom vorbi mai multe
despre asta într-un moment.  Mai
întâi, permiteți-mi să argumentez
de ce este cazul.
Așa că voi fi
puțin informal
cu privire la ce
este exact un program de calculator
și ce este exact
o problemă de decizie.
Dar aproximativ, tot ce trebuie
să fac, singurul nivel
de precizie de care am nevoie este doar
să număr câte sunt acolo.
Ce este un program de calculator?  Ei
bine, de obicei este un fișier.
Ce este un dosar?
Este ca un șir
de caractere.
Ce este un personaj?
Este un șir de biți.
Deci un program este doar, în
cele din urmă, un șir de biți,
șir finit de biți.  Cu
toții înțelegem asta.
Indiferent de limbă
definiți, în cele din urmă,
fiecare program este doar
un șir de biți.
Și un șir de biți pe care îl putem
traduce într-un număr.
Deci putem face conversia între
șiruri de biți și numere.
Când spun număr, mă
refer la ceea ce se numește de obicei
un număr natural
sau un număr întreg nenegativ.
Acest lucru este de obicei reprezentat
de bord aldine aldine -
tablă aldină
capital N. Deci, acesta
este doar 0, 1, 2, și așa mai departe.
Acum, cum rămâne cu
problemele de decizie?
Problema de decizie
este o specificare
a ceea ce vrem să rezolvăm.
Așa că ne putem gândi la asta ca
spunând, pentru fiecare intrare,
răspunsul este da sau nu?
Cam asta
este o problemă de decizie.
Singura întrebare
este, ce este o intrare?
Și am vorbit despre intrări
și dimensiunea intrărilor.
Și există o mulțime de
moduri diferite de a le măsura.
Dar, în cele din urmă, ne putem gândi
la o intrare și la un șir de biți
.
Este doar un dosar.
Deci, o
problemă de decizie este o funcție
de la intrări la da sau nu.
Și intrările vom
spune, ei bine, acesta este
un șir de biți, pe care îl putem
asocia cu un număr în N.
Deci aici putem începe să
legăm lucrurile.
Deci, cu alte cuvinte, un program
este un șir finit de biți,
iar o problemă este, într-un anumit sens,
un șir infinit de biți,
deoarece există infinit de
intrări posibile.
Iar pentru fiecare dintre ele
precizăm da sau nu.
Deci acesta este practic un
șir infinit de biți.
Deci ne putem imagina
011010001110, la infinit.
Doar câțiva - pentru fiecare șir
de biți, putem spune, OK,
dacă intrarea dvs. este numărul
0, iată răspunsul -
nu.
Dacă introducerea dvs. este numărul
1, atunci răspunsul este da.
Dacă introducerea dvs. este
numărul 2, răspunsul dvs.
este da și așa mai
departe în acest rând.
Fiecare șir infinit
de biți corespunde
exact unei
probleme de decizie, care
specifică pentru fiecare
număr întreg de intrare posibil, care
corespunde unui șir de biți,
care este răspunsul, da sau nu?
Deci acest lucru poate părea subtil sau
poate părea că nu este mare lucru.
Acesta este un șir finit de biți.
Acesta este un
șir infinit de biți.
Dar matematica a
studiat bine această problemă.
Și șiruri infinite de biți,
sunt foarte multe,
infinite.
Nu este de mirare.
Există, de asemenea,
infinit de numere întregi.
Deci poate că nu
pare atât de profund.
Dar există o diferență
în infinitate.
Programele și numerele întregi
sunt infinit infinit.
Și șirurile infinite de biți
sunt ceea ce se numește nenumărabili.
Cred că cel mai
intuitiv mod de a vedea
acest lucru este, un
șir infinit de biți,
dacă pun o zecimală sau un
punct binar în față,
acesta codifică un
număr real între 0 și 1.
Deci acesta este aproximativ
un număr real în 01.
Și  când scriu
aproximativ egal aici,
acest lucru merge într-adevăr
în ambele direcții.
Având în vedere o problemă de decizie,
pot defini un șir de biți,
desigur, oferindu-mi
răspunsul pentru toate intrările.
Și îl pot converti într-un
număr real între 0 și 1.
Dar și cealaltă direcție,
dacă iau orice număr real,
aceasta este o
problemă de decizie corespunzătoare.
Acestea sunt 1 la 1
bijecție între ele.
Și vestea proastă este că
numerele reale sunt de nenumărat,
iar numerele naturale
sunt numărabile,
ceea ce înseamnă că sunt mult mai multe
dintre acestea decât sunt acestea.
Deci, un mod în care ați putea
formula acest lucru este, informal,
numărul de
numere naturale este mult mai mic
decât numărul de numere reale.
Și de aici, deducem că
majoritatea problemelor sunt de nerezolvat,
deoarece fiecare program rezolvă
exact o problemă de decizie.  De
asemenea, putem rula un
program, conceptual,
pe toate intrările posibile
și ne vom da seama
ce funcție la rezolvare.
Și dacă nu permitem
numere aleatoare în programul nostru, pe care
eu nu sunt aici, atunci fiecare program
rezolvă exact o
problemă de decizie.
Posibil, este și mai rău pentru
noi, deoarece mai multe programe
probabil rezolvă
aceeași problemă de decizie.
Sunt doar... adaugă
linii irelevante de cod
sau nu fac
nimic diferit.
Sau rulați Bellman-Ford
față de Bellman-Ford de
cinci ori, veți
obține același rezultat.
Și aceasta este de fapt
direcția proastă pentru noi.  Am
dori să știm dacă
există un program care
rezolvă orice problemă de decizie.
Și pentru că există
doar atât de multe programe
și atât de multe
probleme de decizie, pur și simplu...
nu sunt suficiente pentru a merge în jur.
Deci majoritatea... care este formularea?
Nu sunt suficiente programe pentru
toate problemele și, prin urmare, nu există nicio
atribuire a
programelor la probleme,
deoarece sunt
prea multe probleme.
Mai mulți bani, mai multe
probleme, cred.
Așa că, când am
văzut pentru prima dată acest rezultat, am
fost șocat și consternat că...
de ce facem chiar și
informatică dacă majoritatea problemelor nu pot
fi rezolvate?
Din fericire, se pare că majoritatea
problemelor la care ne pasă
pot fi rezolvate.

Despre asta este această clasă.
Și de fapt, chiar și
problemele care ni se par cu adevărat,
foarte greu de rezolvat,
cum ar fi n by n șah, unde putem
demonstra că durează
exponențial,
există un algoritm pentru a rezolva șahul.
Doar că este foarte lent.
Și aceasta este o afirmație
despre, majoritatea problemelor
pot fi rezolvate chiar
în timp finit,
indiferent de cât
timp le-ai acordat.
Deci nu este totul rău.
Din fericire, majoritatea
problemelor care ne pasă
sunt în R. Nu știu de ce.
Acesta este un fel de
mister al vieții.
Dar este o veste bună.
Sau de aceea continuăm să
încercăm să rezolvăm problemele
cu algoritmi.
AUDIENTĂ: Este pentru că
atunci când enunțăm probleme,
afirmația tinde să fie mică?
ERIK DEMAINE: Ei bine, asta--
deci întrebarea
a fost, poate este doar
pentru că aceste
probleme scurte de declarații sunt ușoare.
Dar aceasta este o afirmație destul de scurtă
și este dificilă.
Cred că... nu am
un motiv grozav pentru care.
Aș vrea să înțeleg.
Există un
rezultat general că, dacă
aveți întrebări despre
program în sine, atunci
nu există un algoritm
care să îl rezolve.
Practic, orice întrebare non-trivială
despre programe este
grea, nu este în R. Și
cred că dacă ați luat-- dacă
vă imaginați că luați o
declarație aleatorie a unei probleme,
atunci poate că aceasta va
fi în mijlocul ei
cu o oarecare probabilitate.
Poate de aceea majoritatea.
Dar aceasta este o
noțiune foarte puternică a celor mai mulți.
Există atât de mult mai multe
numere reale decât numere naturale
încât...
nu știu.
Vreau să mai adaug o clasă
la această imagine, care este NP.
Se cuibărește între P și EXP.
Deci știm că P este
conținut în sau egal cu NP.
Și NP este conținut
în sau egal cu EXP.
Nu știm dacă există
o calitate aici sau aici.
Probabil că nu, dar
nu putem dovedi.
Dar ce este această clasă?
Câteva
moduri diferite de a-l defini - s-ar
putea să găsești într-un fel sau
altul mai intuitiv.
Sunt echivalente.
Deci, atâta timp cât înțelegi cel
puțin una dintre ele, e bine.
NP este doar o clasă
de probleme de decizie.
Deci definesc P și
EXP și R arbitrare.
Pot fi probleme
cu orice tip de ieșire.
Dar NP are sens doar
pentru problemele de decizie.
Și va arăta aproape
ca definiția lui P -
problema rezolvabilă
în timp polinomial.  Ne-am
limitat
la probleme de decizie.
Dar vom
permite un tip ciudat
de computer sau
algoritm, pe care îmi
place să-l numesc un algoritm norocos.
Și aceasta se va lega
de noțiunea de ghicire despre
care am vorbit în
ultimele patru prelegeri de
programare dinamică.
Cu programarea dinamică,
am spus, oh,
sunt toate aceste
alegeri diferite pe care le-aș putea face.
Care este alegerea corectă?
Nu știu, așa că aș
vrea să fac o ghicire.
Și ceea ce înseamnă asta în ceea ce privește
un algoritm real este că am
încercat toate
posibilitățile
și apoi am luat maximul
sau SAU sau orice altceva
peste toate acele posibilități.
Și așa am fost...
dar ceea ce am
simulat este ceva pe
care eu îl numesc un algoritm norocos,
care poate face presupuneri
și face întotdeauna
ghicitul corect.
Acesta este un computer
imposibil de cumpărat.  Ar fi
grozav dacă ai putea
cumpăra un computer care să aibă noroc.
Dar nu știm cum să
construim un astfel de computer.
Deci, ce înseamnă asta?
Deci informal,
înseamnă că algoritmul tău
poate face ghiciri norocoase și
face întotdeauna ghicitul corect.
Și, în timp ce în DP, a trebuit să
încercăm toate opțiunile
și să petrecem timp pentru
toate, algoritmul norocos
trebuie să petreacă timp doar pe
presupunerea norocoasă, pe presupunerea corectă.
Mai formal, acesta se numește
un model nedeterminist
de calcul.
Și acest N este --
N în non-determinism
este N pentru NP.
Deci, acesta este un
timp polinomial nedeterminist.
Deci algoritmul poate face presupuneri.
Și apoi, în cele din urmă, ar
trebui să iasă da sau nu.
De exemplu, dacă explorezi un
labirint, acest algoritm ar putea spune,
ar trebui să merg la stânga sau la dreapta?  O să
ghicesc dacă să
merg la stânga sau la dreapta.
Și să spunem că ghicește stânga.
Și apoi merge doar la stânga.
Și apoi ajunge la o
altă intersecție.
Spune, ar trebui să
merg la stânga sau la dreapta?
Și va spune, voi
ghici, și va
spune, ghici bine de data asta.
Și până la urmă, dacă ajung într-o
fundătură poate și spun nu,
sau dacă ajung la destinația la care
încerc să ajung,
spun da.
Deci, acesta este un
algoritm nedeterminist.
Și ce înseamnă
să rulezi acel algoritm?
Ce înseamnă pentru
ghicitori să fie norocoși?
Iată ce înseamnă.
Aceste presupuneri sunt garantate - în
ce direcție ajungi să mergi este
garantat să te conducă la un da
dacă există --
dacă este posibil.
Așadar, în analogia mea cu labirintul,
dacă destinația mea
este accesibilă de la
sursa mea, atunci
sunt garantat că, ori de câte ori am
ghicit la stânga sau la dreapta,
voi alege o cale care
mă duce la destinație.
În timp ce, dacă destinația
este într-o parte deconectată
a labirintului și
nu pot ajunge acolo,
atunci nu știu
ce fac presupunerile.  Chiar
nu contează.
Pentru că orice aș face,
voi ajunge într-o fundătură
și voi spune nu.
Acesta este modelul.
Atâta timp cât aveți un algoritm
care scoate întotdeauna da sau nu
în timp polinomial -- pentru că
vorbim doar despre
timp polinom,
algoritmi norocoși --
dacă există vreo modalitate
de a ajunge la un da,
atunci mașina dvs.
îl va găsi magic
fără  trebuind să petreacă orice
timp pentru a lua aceste decizii.
Deci este un
computer destul de magic
și nu este un computer
care există în viața reală.
Dar este un computer pe care e
grozav de programat.
Este foarte puternic.
Ai putea rezolva multe
lucruri cu el.
Da.
PUBLIC: Dacă ai avea
acest computer magic,
poate ghici dacă
este da sau nu,
de ce nu
răspunde pur și simplu la întrebare?
ERIK DEMAINE: Corect.
Deci, dacă noi...
o verificare bună este,
face asta toate problemele
banale, toate problemele de decizie?
Poate ar trebui să
spun, ei bine, nu
știu dacă
răspunsul la problemă
este da sau nu, așa că voi
ghici doar da sau nu.
Acest lucru este problematic pentru că--
așa că aș putea spune,
va ghici A sau B,
iar dacă aleg
opțiunea A, voi scoate da,
iar dacă aleg
opțiunea B, voi scoate nu.
În acest model, acel algoritm
va scoate întotdeauna da.
Pentru că ceea ce
spune este că, dacă există
vreo modalitate de a ajunge la un
răspuns da, voi proceda așa.
Și astfel, un astfel de algoritm
care încearcă să înșele și doar să
ghicească întregul
răspuns la problemă
va sfârși de fapt prin a
spune întotdeauna
da, ceea ce înseamnă că
nu rezolvă
o problemă foarte interesantă.
Rezolvă doar
problema, care
este reprezentată de
vectorul de biți 1111111,
unde toate răspunsurile sunt da.
Dar o verificare bună.
Da.
AUDIENTĂ: Trebuie
să existe
o serie de lucruri
între care trebuie să aleagă atunci când
[AUDIO OUT]
ERIK DEMAINE: Da.
PUBLIC: Are un
număr exponențial dintre ele?
ERIK DEMAINE:
Numărul exponențial de opțiuni este OK.
De obicei, îmi place să mă gândesc
la asta, deoarece poți
ghici doar câte un pic pe rând.
Dar ni se permite
timpul polinom,
așa că de fapt aveți
voie să ghiciți
numărul polinom de biți.
În acel moment, puteți ghici
peste un spațiu de dimensiune exponențială,
dar nu mai mult decât exponențial.
Deci este... da,
timpul polinom să spunem în
modelul de ghicire pe un bit.
Ce am spus?
Face presupuneri - să
adăugăm binar aici.
Altfel primim o altă
clasă, pe care nu o vreau.
OK, hai să facem un exemplu, un
exemplu real de un astfel de algoritm
care este util, care este Tetris.  Așa
că susțin că Tetris este
în NP, deoarece
există un algoritm norocos și un

algoritm de timp polinomial nedeterminist care poate
rezolva jocul Tetris.
Deci, din nou, ți se
dă o tablă, ți se
oferă o secvență
de piese și
vrei să știi dacă există
o modalitate
de a plasa piesele
care te lasă să supraviețuiești.
Și, așadar, ceea ce voi
face este că, pentru fiecare piesă,
voi ghici
cum să o plasez.
Deci, pentru prima
piesă, voi
ghici cât de departe la stânga
sau la dreapta o mut.
Apoi am lăsat-o să cadă un pas.
Poate o rotesc.
Aleg o secvență de mișcări
între stânga, dreapta, jos,
rotește la dreapta, rotește la stânga.
Și pe tot parcursul,
verific, este acea mișcare valabilă?
Dacă mutarea este invalidă în orice
moment, spun doar, returnați nu.
Și apoi, dacă piesa ajunge
într-un loc bun,
continui cu următoarea bucată.
Eu fac același lucru, ghicesc
toate lucrurile posibile pe care le-
aș putea face pentru asta.
Din nou, trebuie doar să
ghicesc câte un pic pe rând.
Și va trebui să fac doar un
număr polinom de presupuneri,
cum ar fi un număr liniar de presupuneri,
pentru fiecare bucată despre locul în care
se încadrează, deci poate un
număr patratic de presupuneri în
general.
Și apoi, la
sfârșit, dacă am supraviețuit...
oh, trebuie să
verific și dacă o linie se șterge.
Apoi eliberez linia.
Și dacă până la urmă
supraviețuiesc, mă întorc da.
Deci acesta este un
algoritm nedeterminist.
Asa ca as spune, verifica
regulile jocului.
Și dacă supraviețuim, revenim da.
Și dacă la un moment dat încălcăm
regulile -- de exemplu,
ieșim din partea de sus a tablei --
returnăm nr.
Deci, acesta este un algoritm
care returnează uneori
nu și alteori
da, în funcție
de alegerile pe care le faci.
Și acest model
garantează că, dacă există
vreo modalitate de a ajunge la un
da, îl va găsi.
Dacă aș schimba aceste
răspunsuri, dacă aș reveni da
când am încălcat regulile și aș
returna nu dacă am supraviețuit,
acesta ar fi un
algoritm neinteresant.
Pentru că este foarte ușor
să pierzi în Tetris.
Partea grea este să supraviețuiești.
Dacă spun, există vreo modalitate de a
juca jocul în așa fel
încât să încalc regulile, atunci,
desigur, răspunsul este da.
Puteți doar să stivuiți bucăți
și să mergeți de sus.
Există o asimetrie în această
definiție a da versus nu.
Găsește întotdeauna
răspunsuri da, dacă este posibil.
Nu găsește întotdeauna
niciun răspuns, dacă este posibil.
Deci, este foarte important modul în care am
scris aceste întrebări.
Este important să definesc
Tetris ca fiind problema,
pot supraviețui?
Problema
nu pot supraviețui,
este imposibil să supraviețuiesc,
asta este o altă întrebare.  Probabil că
problema nu este
în NP.
OK, așa că o ușoară subtilitate
acolo, da versus nu.
Permiteți-mi să vă dau
cealaltă definiție a NP.
Deci, dacă acesta este
confuz, care--
deși prefer
această definiție.
Majoritatea oamenilor nu.
Deci acest lucru este confuz.
Să facem cealaltă definiție.
Deci, o altă definiție este că
NP este un set de probleme de decizie
care pot fi verificate
în timp polinomial.
Acest lucru a apărut de fapt
în ultima prelegere
în care am vorbit
despre suma subsetului.
Am spus, iată o
grămadă de numere întregi,
iată un număr întreg țintă
și vă pot demonstra
că acest număr întreg poate fi
reprezentat ca o sumă de numere
din submulțimea mea de numere din
setul meu, pentru că iată-le.
Ți-am dat asta plus asta plus
aceasta este egală cu suma țintă.
Și aceasta este o soluție,
într-un anumit sens, care poate
fi verificată pentru un exemplu de da.
Dacă îmi pot reprezenta numărul
ca o sumă de subset dintr-un anumit set,
îmi este ușor să
vă dovedesc asta.
Și îl puteți verifica doar
adunând numerele
și verificând dacă fiecare
număr a fost în set.
Deși nu există cazuri, am avut
un exemplu de sumă țintă
care nu a putut fi atinsă.
Și singurul motiv pentru care
știam asta este pentru că
am forțat chestia asta.
Și nu există nicio modalitate succintă de a-
ți demonstra că acel număr
nu poate fi reprezentat.
Un lucru similar cu Tetris,
ceea ce aș spune este--
deci aceasta este versiunea
1, versiunea 2--
pentru Tetris este
că, un certificat
pentru o introducere da a lui
Tetris este o secvență
de mișcări pentru piese.
Bine, dacă este posibil
să supraviețuiești în Tetris,
îți pot dovedi.
Pot să joc jocul și să-
ți arăt că am supraviețuit.
Fără răspunsuri, nu
știu, e greu să-
ți demonstrez că nu pot supraviețui
unei anumite secvențe de piese.
Dar răspunsurile da sunt ușoare.
Vă arăt doar, iată
secvența de apăsări de butoane pe care o voi
face pentru această piesă,
apoi pentru această piesă,
apoi pentru această piesă.
Observați că este exact
același lucru pe care l-am
ghicit la
începutul acestui algoritm.
Și apoi am făcut o altă
muncă pentru a implementa regulile.
Și, în mod similar, dacă ți-am dat
un certificat, care
sunt lucrurile pe care am vrut să le
ghicesc despre cum să joc jocul,
pot verifica acest certificat
doar implementând
regulile Tetris și
văzând dacă am supraviețuit.
Și dacă încalci regulile
în orice moment, spui nu.
Și dacă supraviețuiești, te
întorci da.
Acesta este ceea ce se numește
algoritm de verificare.
Deci, permiteți-mi să oficializez această noțiune.
Având în vedere o intrare de problemă
plus un certificat,
ca cel de acolo,
există un timp polinom --
deci aceasta este încă o
altă definiție.
Aceasta este ceea ce vreau să spun prin
această definiție a NP--
algoritm de verificare care
satisface două proprietăți.
Una este, pentru fiecare intrare da -
deci pentru fiecare intrare unde
răspunsul este da la problemă -
există un certificat astfel
încât verificatorul spune da.
Așadar, aceasta înseamnă că este
posibil să-mi demonstrezi
că un răspuns este da,
pentru că dacă
ai vreodată o intrare că
răspunsul se întâmplă să fie da,
poți să-mi dovedești mie
dându-mi un certificat.
Există întotdeauna un certificat
care dovedește că răspunsul este da.
Deoarece verificatorul, care rulează
în timp polinom obișnuit -
acesta este un algoritm de verificare obișnuit, de
modă veche, cu
picioarele pe pământ,

timp polinom în
sensul nostru obișnuit -
va spune da.
Și, în plus,
răspunsurile da de la verificator
sunt de fapt semnificative, pentru că
dacă îi dau vreodată un nu,
întotdeauna spune nu, indiferent de
ce certificat îi dau.
Deci, acest lucru ar trebui să oficializeze cu adevărat
ceea ce înseamnă toate acestea.
Este echivalent cu
definiția anterioară.
Aceasta înseamnă că
există dovezi pentru cazurile da.
Și asta înseamnă că dovezile
nu există pentru niciun caz,
adică
nu există dovezi false.
Deci, dacă verificatorul
dă vreodată da,
știți că răspunsul
la problema dvs. este da.
Dar dacă iese
nu, nu ești sigur.
Poate ați greșit certificatul

pentru că știm doar că există
un certificat în care
verificatorul va spune da.
Sau poate a fost o
intrare fără, și apoi
nu a contat ce
certificat ai folosit.
Dar este frumos, pentru că
scrie pe, să zicem, Tetris,
dacă vă dau
secvența pieselor,
este foarte ușor să scrieți un
verificator care doar implementează
regulile Tetris.
Și astfel puteți măcar să
verificați dacă o soluție
este valabilă în cazul da.
În niciun caz, nu
avem nimic util.
Deci NP este o structură,
o structură suplimentară
despre intrările da
din problema ta.
Și multe
probleme de decizie sunt în NP.
Multe dintre problemele la
care ne pasă
pot fi formulate ca o problemă NP.
Atâta timp cât este o
problemă de decizie,
de obicei, răspunsul cu da sau nu
este demonstrabil, cum ar fi suma subsetului,
cum ar fi Tetris.
Toate acestea sunt probleme
la care, dacă răspunsul este da,
vă pot da o
dovadă convingătoare de ce.
Și se dovedește că
multe probleme se
încadrează în această setare NP.
Și astfel avem câteva instrumente
pentru a vorbi despre problemele care
sunt dificile în ceea ce privește NP.  Mai
întâi să vorbesc
puțin despre P.
Nu este egal cu
NP, semn de întrebare.
Mulți oameni presupun
că P nu este egal cu NP.
Este un fel de
presupunere standard
în informatica teoretică.
Dar nu știm cum să demonstrăm
dacă P este egal cu NP sau nu este
egal cu NP.
Și astfel, în această imagine,
am tras ipoteza,
care este că NP este o
regiune strict mai mare decât este P.
Dar nu
știm de fapt dacă
există probleme în această regiune.
Nu știm dacă
există probleme
în această regiune
între NP și EXP.
Presupunem că
există probleme aici
și există probleme aici.  Cu
siguranță există probleme
aici sau probleme aici,
dar nu știm care dintre ele.
Pentru că știm că P
nu este egal cu EXP,
dar nu știm
dacă P este egal cu NP
și nu știm
dacă P este egal cu EXP.
Dacă ai putea dovedi că P
nu este egal cu NP sau ai respinge,
ai câștiga 1 milion de dolari, ceea ce
nu atât de mulți bani în zilele noastre.
Dar ai fi faimos
pentru tot restul timpului
dacă ai putea dovedi vreodată asta.  În
fiecare an, există,
de obicei, o dovadă de crackpot
care nu funcționează.
Unii dintre ei merg la mine.
Vă rog să nu le trimiteți.
Și oricum, este o
problemă foarte grea.
Este un fel de problemă de bază
în informatica teoretică
, cum să demonstrăm că
P nu este egal cu NP.
Dar în cea mai mare parte,
doar presupunem asta.
Acum, ce
înseamnă această presupunere?
În esență, înseamnă că, așa cum îmi
place să spun,
nu poți crea norocul.
Deoarece problemele NP
sunt probleme pe care le
puteți rezolva prin algoritmi norocoși.
P sunt probleme pe care le puteți rezolva
cu algoritmi vechi obișnuiți.
Și deci dacă P este egal cu
NP, înseamnă că
norocul nu îți cumpără
nimic, ceea ce pare ciudat.
Dacă pot face magic
aceste presupuneri super-puternice,
atunci pot rezolva
problema că acesta este
NP, care pare
super puternic, mult
mai puternic decât
algoritmii obișnuiți,
în care trebuie să facem de fapt cu
forța brută și să încercăm
toate alegerile.
Și așa pare destul de solid
că P nu este egal cu NP.  Asta e...
desigur,
nu știm cum să dovedim asta.  O
altă formulare
este că este mai greu
să vii cu dovezi
decât să le verifici,
din perspectivă matematică.
Acest lucru este echivalent cu
P nu este egal cu NP.
Deci de aceea ar
trebui să crezi.
Acum, să mergem aici.
Următoarea noțiune este duritatea NP.
Deci, în special,
vreau să susțin --
aceasta este o teoremă care
există în literatură --
că dacă P nu este egal cu
NP, atunci Tetris nu este NP.
Așa că am spus chiar aici,
Tetris este în EXP,
dar nu știm
dacă este în NP.
Dar, de fapt,
presupunem că nu este NP
deoarece presupunem
că P nu este egal cu NP.
Dacă ați putea demonstra
această presupunere -
și există o mulțime de teoreme
care sunt condiționate presupunând că P
nu este egal cu NP -
atunci obținem niște rezultate frumoase,
cum ar fi Tetris nu poate fi rezolvat
în timp polinomial.
Nu își poate da seama dacă
pot câștiga un joc Tetris
în timp polinomial
în dimensiunea de intrare.
De ce?
Aceasta este o consecință a unei
alte teoreme, care
este că Tetris este NP-hard.
Voi defini
mai întâi NP-hard informal,
apoi îl voi defini puțin
mai formal într-o secundă.
Dar asta înseamnă,
aproximativ, că Tetris este la fel de
greu ca toate problemele din NP.
Așa că lasă-mă să desenez asta
în imagine.
Deci NP-hard este această parte.
Mi-am lăsat suficient loc?
Poate nu.
Ei bine, o vom strânge.
Există o altă regiune
aici pentru EXP-hard.
Deci problema ta de a fi în
NP a fost un rezultat pozitiv.
Spune că nu ești mai
dificil decât această linie.
Ești fie în această
poziție, fie în stânga.
A fi în P a fost și
o declarație pozitivă.
Spune că ești aici
sau în stânga.
A fi în P este mai bine
decât a fi în NP,
deoarece acesta este
un subset al acestuia.
NP-hard este o limită inferioară.
Se spune că ești în acest punct,
la acest nivel de dificultate
sau la dreapta.
Și așa merge de aici până
la infinit în dificultate.
Și EXP-hard spune că
ești cel puțin la fel de
dur ca
măsura corectă a setului EXP,
sau ești mai greu decât
atât, într-un sens pe care îl
vom oficializa într-un moment.
Și acest loc chiar aici,
după cum vă puteți imagina,
este destul de interesant.
Este exact locul în care
NP se întâlnește cu NP-hard.
Acest lucru se
numește NP-complet.
Probabil ați auzit
de NP-completeness,
o noțiune celebră.
Și asta înseamnă.
Este, problemele
care sunt în NP--
deci au un
algoritm norocos care le rezolvă,
pot fi verificate,
există certificate
care pot fi verificate--
și sunt NP-hard.
Deci sunt în NP și
sunt cele mai grele dintre problemele
din NP.
Acum, nu sunt cea
mai grea problemă.
Există de fapt multe
probleme chiar aici
la acest singur nivel de
dificultate numit NP-complet.
Printre ei se numără și Tetris.
Sunt multe altele, pe care le
voi enumera în scurt timp.
Deci aceasta este NP-completitudine.
Deci, deoarece aceste probleme sunt cele mai
grele probleme din NP,
dacă există probleme
aici între--
în NP minus P, atunci
acestea trebuie să fie printre ele.
Și așadar, dacă presupuneți
că P nu este
egal cu NP, așa cum o
fac majoritatea oamenilor, atunci
știți că toate problemele
de la această extremă dreaptă
a NP, cea mai grea dintre
problemele din NP,
nu trebuie să fie NP.
Și de aceea pot spune,
dacă P nu este egal cu NP,
Tetris nu este NP și, de asemenea, orice
problemă NP completă nu este NP.
OK, ce înseamnă „la fel de greu ca”?
Acestea sunt reducerile noastre de bun
prieten.
Am vorbit mult despre reduceri
la această clasă.
Reducerile sunt
modalitatea ușoară de a utiliza algoritmi.
Doar iei problema ta
și o reducă la o problemă pe care
deja știi cum să o rezolvi.
Luați intrarea pentru o
problemă pe care doriți să o rezolvați
și o transformați într-o
intrare la o altă problemă,
cum ar fi cele mai scurte căi cu o singură sursă
sau ceva de genul pe care
aveți deja un
algoritm pentru rezolvare.
Deci, dacă aveți un algoritm
care rezolvă problema B,
îl puteți converti
într-o soluție pentru B.
Și o reducere ar trebui,
de asemenea, să-mi spună cum să--
având o soluție pentru B,
cum să o convertesc înapoi
într-o soluție pentru A. Și
când spun soluție aici,
mă refer de fapt la certificat
de acolo.
Deci, cum-- deci dacă eu-- deci dacă
am-- deci reducerea
constă din aceste două bucăți--
cum să convertesc o intrare
de la A într-o intrare pentru B
și, având o soluție
pentru B, cum să o convertesc într-
o  soluție la A.
Permiteți-mi să vă dau câteva exemple de
reduceri pe care le-ați văzut deja.
Ai văzut multe dintre ele.
Dacă am cele mai
scurte căi neponderate în stânga-- cele mai scurte căi
neponderate cu o singură
sursă--
pot reduce asta la cele mai
scurte căi ponderate.
Cum?
PUBLIC: Setați toate
ponderile la 1.
ERIK DEMAINE: Setați
toate ponderile la 1.
Așa că aici mi se oferă un
grafic fără ponderi.
Dacă am setat toate
greutățile la 1, asta
o transformă într-o intrare pentru o
singură sursă ponderată căile cele mai scurte
.
Deci, dacă nu știai
cum să rezolvi asta,
ai putea să o rezolvi
conversia.
Dacă ați scris deja, de
exemplu, un algoritm Dijkstra, l-ați
putea aplica pentru a rezolva cele mai

scurte căi neponderate cu o singură sursă.
Acum, știm o modalitate mai rapidă
de a rezolva acest lucru,
dar este doar un
factor de logare mai rapid.
Și aici vorbim despre
polinom versus exponențial.
Deci aceasta este o reducere valabilă.
Nu este
cel mai interesant
din punct de vedere algoritmic,
dar este un algoritm.
Un alt lucru pe care l-am
văzut este că, dacă aveți

ponderi întregi în stânga,
puteți să
le convertiți în ponderi întregi
pozitive neponderate din dreapta
,
subdivând fiecare
muchie a greutății W
în muchii W fără greutate.
Deci poate că este
puțin mai puțin eficient.
Depinde care
este suma greutăților.  O
altă versiune pe care am văzut-o
este cea mai lungă cale dintr-un grafic.
Putem-- calea ponderată pe care o
putem reduce la cea mai scurtă cale
dintr-un grafic, ponderată prin
negarea tuturor ponderilor.
Am făcut asta în unele dintre
lucrurile de programare dinamică.
Cum ar fi oh, cea mai lungă cale pe un DAG?
Putem converti asta în
calea cea mai scurtă pe un DAG
doar prin anularea
tuturor ponderilor.
Deci toate acestea sunt exemple
de conversie a unei probleme
în alta.
De obicei, convertiți din...
pentru algoritmi,
convertiți dintr-o problemă pe care
doriți să o rezolvați într-o
problemă pe care deja
știți cum să o rezolvați.
Dar se pare că aceleași
reduceri de instrumente pot fi folosite
și pentru a dovedi rezultate negative.
Și în acest caz, vom
reduce de la o problemă care
credem că nu poate fi rezolvată și
o vom reduce la problema pe care
suntem interesați să o rezolvăm.
Așa că permiteți-mi să scriu mai
precis ce înseamnă asta.
Dacă puteți găsi o
reducere ca aceasta,
înseamnă că
rezolvarea lui A este cel puțin la fel de
ușoară ca și rezolvarea lui B. Pentru că
aș putea rezolva A, în special,
transformându-l în B, rezolvând
B și apoi transformându-l înapoi
într-o soluție la  A. Cu
alte cuvinte, dacă pot să rezolv B,
pot să rezolv A, pe care îl
pot exprima informal ca,
A este cel puțin la fel de ușor ca B.
Și acum, folosind gramatica,

orice contrapozitiv, este același lucru
cu a spune că  B este cel puțin la fel de
greu ca A. Și asta vreau să spun
prin cel puțin la fel de greu ca.
Deci aceasta este definiția mea
a cel puțin la fel de greu,
în această noțiune de duritate NP.
Deci ceea ce înseamnă NP-hard
este că sunt cel puțin la fel de
greu ca toate problemele din NP.
Deci, ceea ce înseamnă că
fiecare problemă din NP
poate fi redusă la Tetris,
ceea ce este oarecum amuzant.
Dar, în special, asta
înseamnă că, dacă există
un algoritm pentru Tetris,
există un algoritm
pentru toate problemele din NP.
Și deci acesta este de fapt
contrapozitivul
acestei afirmații.
Deci, aceasta înseamnă că, dacă
există un polinom --
dacă iau contrapozitivul
acestuia, aceasta înseamnă că
dacă există un
algoritm de timp polinomial pentru Tetris,
atunci P este egal cu NP, există
un algoritm de timp polinom
pentru fiecare problemă din NP.
Și modul în care dovedim
asta este prin reduceri.
Luăm o problemă arbitrară în
NP și o reducem la Tetris.
Din fericire, nu este atât de greu pe cât
pare, pentru că a
fost deja făcut o dată.
Există deja o
reducere de la NP la...
de la toate problemele din NP la
probleme singulare,
problemele NP-complete.
Există o primă
problemă NP-completă, care
cred că este mașina Turing.
Practic, simulează
un algoritm norocos,
deci este o
problemă nu foarte interesantă.
Dar din această problemă,
dacă o poți reduce
la orice altă problemă,
știi că problema
este și NP-grea.
Și pe scurt, vreau să
vă arăt câteva exemple în acest sens aici.
Așa că vreau să
încep cu o problemă
pe care doar o să
presupun că este NP-completă.
Și se numește 3-partiții.
O modalitate de a-l formula este,
vă dau o grămadă de numere întregi...
Cred că am scris-o
aici, de asemenea, tabla.
Vă dau n numere întregi și
aș dori să le împart
în n peste 3 grupuri de dimensiunea 3,
astfel încât fiecare grup de dimensiunea 3 să
aibă aceeași sumă.
Și e scris
acolo, pe tablă.
Deci, vă puteți gândi și la aceasta
ca la următoarea problemă.
Vă dau o grămadă de dreptunghiuri
care au lungimea unei laturi --
sau o grămadă de bețe, să
zicem, de lungimi diferite
și vreau să le grupez
ca în diagrama din dreapta,
deci în grupuri de câte 3, astfel încât
totalul  lungimea fiecărui grup
este exact aceeași.
Aceasta este doar o problemă.
Și credeți deocamdată
că este NP-complet.
Nu voi dovedi asta.
Dar ceea ce aș vrea să vă arăt
este o reducere de la această problemă
la o altă problemă -
rezolvarea puzzle-urilor.
Așa că ați putea crede că
puzzle-urile
sunt foarte ușoare și mai ales
dacă pierd proiectorul.
Dar, de fapt, dacă
aveți un puzzle
în care unele dintre
potriviri sunt ambigue,
dacă există mai multe piese care s-
ar putea potrivi cu o anumită filă
sau buzunar, atunci
susțin că pot reprezenta
această problemă cu 3 partiții
construind bastoane mici,
ca aici  .
Deci, dacă vreau să reprezint
un baston de lungime ai, voi
construi doar un ai--
nu am menționat că
toate sunt numere întregi
și sunt
numere întregi de dimensiuni polinomiale.
Voi reprezenta asta
prin diferite piese aici.
Și filele și
buzunarele roșii sunt proiectate
pentru a fi unice la nivel global
pentru puzzle,
ca un puzzle obișnuit.
Având în vedere această piesă din stânga
și această filă din dreapta,
există un buzunar unic, există
o piesă cu buzunar unic
care se potrivește perfect
în piesa respectivă.
Deci această unire este forțată.
Și, de asemenea, această alăturare este forțată.
Dar filele albastre și
buzunarele sunt diferite.
Toate sunt la fel.
Toate sunt identice.
Și așadar, dacă construiesc
acest cadru folosind
atribuțiile unice roșii
și construiesc aceste dreptunghiuri,
dacă vreau să împachetez aceste
dreptunghiuri în acest dreptunghi,
aceasta este exact problema cu 3 partiții
, cu câteva detalii
pe care nu le-am completat.
Dar  se dovedește că ai fi
forțat să le grupezi
în grupuri de mărimea 3,
ceva de genul acesta,
cu lungimi diferite.
OK, deci acesta este un
exemplu de reducere.
Dacă credeți că
3-partiția este NP-hard,
acest lucru vă dovedește că
puzzle-urile sunt NP-hard,
ceva ce poate
nu știați.
De fiecare dată când rezolvi
un puzzle, te
poți simți bine cu
tine,
mai ales dacă
are parteneri ambigui.
Următorul este Tetris.
Deci iată o reducere de la
aceeași problemă cu 3 partiții,
care este una dintre problemele mele preferate
, la Tetris.
Începe cu
această tablă ciudată.
Are o grămadă de coloane
aici unde aș putea pune bucăți.
Deci nu am voie să pun
bucăți în aceste regiuni întunecate.
Toate au înălțimea
T. T este suma țintă la
care vrem să se


adună toate triplele de numere.
Și sunt n peste
3 dintre aceste sloturi
în care pot încerca să pun piese.
Și este... din cauza acestui
lucru din dreapta,
nu există nicio modalitate de a curăța
liniile în acest joc.
Și acum, pentru a reprezenta
un singur număr ai,
vă voi oferi
această secvență de piese,
care începe cu o piesă L.
Și apoi are
repetări ale acestui model
și apoi se termină cu
aceste două piese.
Și, așadar, ceea ce se
întâmplă este că -
asta se află în
soluția dorită -
mai întâi așezi un L în
partea de jos a uneia dintre aceste găleți,
apoi repeți acest
model în acest mod frumos.
Și umple aia,
aproximativ, înălțimea acestei găleți.
Și apoi, la sfârșit,
trebuie să pui eu aici.
Și ceea ce ajunge să garanteze acest lucru

este că toate aceste piese
merg într-o singură găleată.  Poti sa
verifici.
Este plictisitor.
Dar dacă ai încerca să pui
unele dintre aceste piese
într-o găleată și alte
bucăți într-o găleată diferită,
ai pierde ceva spațiu
și atunci ai muri.
Deci, dacă vrei să supraviețuiești,
trebuie să pui toate aceste piese
într-o găleată.
Și din nou, doar
stivuim dreptunghiuri.
Punem o grămadă
de dreptunghiuri într-un buzunar
și apoi o grămadă de
dreptunghiuri în alt buzunar.
Putem comuta înainte și înapoi
cum vrem.
Dar singura modalitate de a
câștiga, se dovedește,
este dacă obțineți ca toate
acele dreptunghiuri
să se adună exact la
înălțimea potrivită.
Atunci ai o
imagine ca asta.
Dacă nu primești o
astfel de poză,
poți dovedi că ajungi să mori.
Atunci o să-ți dau
o grămadă de Ls.
Apoi, în sfârșit, vă voi da acest
T, care șterge câteva linii.
Și apoi îți voi oferi-- cel
mai satisfăcător
joc Tetris vreodată-- îți voi
da o
tonă de I-uri, iar tu
obții Tetris, Tetris, Tetris
și ștergi întreaga tablă.
Și așa că, dacă poți rezolva
problema cu 3 partiții,
poți șterge
tabla și poți câștiga jocul
și să fii cel mai bun
jucător Tetris vreodată.
Și dacă nu există o
soluție pentru 3 partiții,
ești garantat că vei pierde.
Și asta dovedește că
Tetris este NP-hard.
Misto.
Deci, ce mai
vreau să spun, pe scurt?
Cred că asta e ideea principală.
Deci un alt exemplu...
deci acest punct
se numește EXP-completitudine.
Și aceasta include probleme
precum șahul n cu n.
Așa că știm că șahul
necesită timp exponențial
pentru că, de fapt,
este printre cele mai grele
probleme în timp exponențial.
Dar cele mai obișnuite sunt...
asta se datorează cumva
naturii jocului cu doi jucători.
Cele mai frecvente sunt
problemele NP-complete.
Și avem o grămadă de
exemple de probleme NP-complete pe care le
voi menționa pe scurt aici.
Așa că am văzut
problema sumei submulțimii, pentru
care am avut un
algoritm de timp polinomial pentru --
îmi pare rău, un
algoritm de timp pseudo polinomial pentru ultima clasă --
de fapt nu are
algoritm de timp polinomial,
presupunând că P este egal cu NP.
Deci pseudo poli este cel mai bun la care
poți spera pentru suma subset.
Există o noțiune înrudită
numită duritate NP slabă,
pe care nu voi intra aici.
3-partiție este una pe care am văzut-o.  Am
văzut unele reduceri
la alte probleme.
Deci toate acestea sunt NP complete.  Cea
mai lungă subsecvență comună este o
altă problemă de programare dinamică pe care am
văzut-o
cu două secvențe.
Am menționat că poți
rezolva asta pentru trei
sau patru sau orice număr constant.
Dar dacă vă dau n
secvențe fiecare cu lungimea n,
acea problemă este
NP-hard, NP-complet.
Cea mai lungă cale simplă
dintr-un grafic -
știm cum să rezolvăm cea mai lungă cale.
Doar rezolvați calea cea mai scurtă
și greutățile negative.
Dar cea mai lungă cale simplă, în care
nu repeți vârfurile,
este NP-complet.  În
mod similar, una dintre cele mai
faimoase probleme NP-complete
este problema vânzătorului ambulant
, găsirea celei
mai scurte căi care vizitează
toate vârfurile dintr-un grafic dat.
Deci, în loc să
merg doar de la A la B,
vreau să vizitez toate
vârfurile din grafic.
Multe dintre aceste
probleme le exprim
drept probleme de optimizare.
Dar când spun
NP-complet, mă refer de fapt la o

versiune de decizie a problemei.
De exemplu, cu
acesta, întrebarea de decizie
este cea mai scurtă cale care
vizitează toate vârfurile dintr-un grafic
mai mici sau egale
cu o valoare dată x.
Dacă puteți rezolva acest lucru,
atunci prin căutare binară
puteți rezolva
greutatea totală.
3-colorarea unui grafic este dificilă,
chiar dacă 2-colorarea unui grafic
este polinom.
3-colorarea este NP-complet.
Atribuirea a trei
culori nodurilor
astfel încât niciun vârf adiacent să nu
aibă aceeași culoare,
găsirea celei mai mari clicuri
într-un anumit grafic, ceea ce
ar fi util pentru analiza
rețelelor sociale, indiferent.
Acesta este unul distractiv
pentru mine ca geometru.
Dacă te afli într-o
lume tridimensională, ceea ce sunt și eu
și vreau să găsesc cea mai scurtă
cale de aici până acolo care
să nu se ciocnească
de niciun obstacol,
cum ar fi acest birou și toate
scaunele și așa mai departe, în 3D,
această problemă--
dacă poți zbura, așa că dacă
ești o dronă care zboară
printre toate aceste
obstacole, vrei
să găsești cea mai scurtă cale de la
A la B, aceasta este NP-complet.
Este destul de surprinzător.
În două dimensiuni,
este polinom.
Îl puteți reduce la
graficul celor mai scurte căi.
Dar în 3D, este NP-greu.
Aceasta este o problemă cu formula
care apare mult.
Având în vedere o formulă booleană
cu ȘI, SAU sau NU, o
puteți face vreodată adevărată,
dacă are unele variabile care
nu sunt alocate?
Și câteva exemple mai distractive
sunt Minesweeper sau Sudoku.
Practic, orice puzzle de hârtie și creion pe care l-
ați jucat vreodată,
probabil că există
o hârtie care
dovedește că este NP-complet.
Și din partea jocurilor video
, Super Mario Brothers
este NP-hard.
Legend of Zelda este NP-hard.
Pokemon este NP-hard.
Aceste probleme sunt de fapt
un pic mai dificile decât NP,
într-o clasă diferită numită
P-space, în care nu voi intra.
Dar dacă sunteți interesat
de aceste lucruri,
există o întreagă clasă dedicată
acestuia, care are prelegeri video online
, astfel încât să le puteți urmări
oricând doriți,
numită 6.892, care oferă
o grămadă de exemple deosebit de distractive
de duritate NP
și  alte tipuri de
dovezi de duritate dintr-un fel de
perspectivă a algoritmului pentru o mulțime
de jocuri și puzzle-uri care
ți-ar putea interesa.
Si asta e.