O analiză a limitelor inferioare pentru satisfactibilitate și probleme conexe

Titlul original:

A Survey of Lower Bounds for Satisfiability and Related Problems

Conținutul cărții:

Completitudinea NP reprezintă, fără îndoială, cel mai răspândit concept din informatică, deoarece surprinde complexitatea de calcul a mii de probleme importante din toate ramurile științei și ingineriei.

Întrebarea P versus NP este dacă aceste probleme pot fi rezolvate în timp polinomial. Un răspuns negativ a fost conchis pe scară largă pentru o lungă perioadă de timp, dar, până de curând, nu au fost cunoscute limite inferioare concrete pe modele generale de calcul.

Satisfiabilitatea este problema de a decide dacă o formulă booleană dată are cel puțin o atribuire satisfăcătoare. Aceasta este prima problemă care s-a dovedit a fi NP-completă și este probabil cea mai frecvent studiată problemă NP-completă, atât pentru proprietățile sale teoretice, cât și pentru aplicațiile sale practice. A Survey of Lower Bounds for Satisfiability and Related Problems analizează limitele inferioare recent descoperite pentru complexitatea în timp și spațiu a satisfiabilității și a problemelor strâns legate de aceasta.

Acesta trece în revistă rezultatele de ultimă oră privind modelele generale de calcul deterministe, randomizate și cuantice și prezintă argumentele care stau la baza acestora într-un cadru unificat. A Survey of Lower Bounds for Satisfiability and Related Problems este o referință neprețuită pentru profesorii și studenții care fac cercetare în teoria complexității sau intenționează să facă acest lucru.