Modified Branching Programs and Their Computational Power
Etichete
Computere, Informatică, Teoria Mașinilor, Programare, Algoritmi, Interfețe Utilizator, Matematică, Matematică Discretă
Branching Programs reprezintă, alături de circuitele Boolean, unul dintre cele mai semnificative modele nonuniforme de calcul. Această lucrare oferă o sinteză a celor mai recente cercetări din acest domeniu, abordând teoria complexității prin prisma programelor ramificate. Începând cu o definiție clară a programelor ramificate și o revizuire a studiilor anterioare, autorul introduce și analizează programele ramificate nondeterministe, permițând astfel descrierea unor clase fundamentale de complexitate.
Volumul se concentrează apoi pe conceptul inovator de Omega-branching programs, care, pe lângă testele binare obișnuite, integrează caracteristici pentru evaluarea anumitor funcții booleene elementare, fiind adecvate pentru caracterizarea claselor de complexitate limitate de spațiu. Prin aceste caracterizări, autorul demonstrează separarea unor clase restricționate de complexitate. În anexă, sunt prezentate o serie de probleme extrem de restricționate de accesibilitate a graficelor, care, datorită descrierilor programelor ramificate din primele trei capitole, sunt complete p-proiecție în clasele avute în vedere.
DaniAI e uneori grăbită și poate face mici greșeli când traduce din alte limbi sau când scrie rezumatul unei cărți. Dacă vrei să semnalezi o greșeală, apasă stegulețul - noi vom revizui detaliile.
Dani te poate ajuta să înțelegi cartea, unde o găsești, cât durează de citit sau cine o are deja pe raft în comunitatea Cuvintești.
