Limitele inferioare ale complexității utilizând algebra liniară

Titlul original:

Complexity Lower Bounds using Linear Algebra

Conținutul cărții:

În timp ce s-au înregistrat progrese rapide în ceea ce privește limitele superioare (algoritmi), progresele privind limitele inferioare ale complexității problemelor explicite au rămas lente, în ciuda eforturilor intense depuse de-a lungul mai multor decenii.

Așa cum este firesc în cazul rezultatelor tipice de imposibilitate, întrebările privind limitele inferioare sunt probleme matematice dificile și, prin urmare, este puțin probabil să fie rezolvate prin atacuri ad hoc. În schimb, sunt necesare tehnici bazate pe noțiuni matematice care surprind complexitatea computațională.

Complexity Lower Bounds using Linear Algebra analizează mai multe tehnici de demonstrare a limitelor inferioare în complexitatea booleană, algebrică și de comunicare pe baza anumitor abordări algebrice liniare. Tema comună a acestor abordări este studierea măsurilor de robustețe ale rangului matricei care captează complexitatea într-un anumit model. Limitele inferioare suficient de puternice ale acestor funcții de robustețe ale matricelor explicite conduc la consecințe importante în modelele de circuit sau de comunicare corespunzătoare.

Înțelegerea complexității computaționale inerente a problemelor este de o importanță fundamentală în matematică și informatică teoretică. Complexity Lower Bounds using Linear Algebra este o referință inestimabilă pentru oricine lucrează în domeniu.