Un'indagine sui limiti inferiori per la soddisfabilità e i problemi correlati

Titolo originale:

A Survey of Lower Bounds for Satisfiability and Related Problems

Contenuto del libro:

La completezza NP è probabilmente il concetto più pervasivo dell'informatica, in quanto cattura la complessità computazionale di migliaia di problemi importanti di tutte le branche della scienza e dell'ingegneria.

La domanda P contro NP chiede se questi problemi possono essere risolti in tempo polinomiale. La risposta negativa è stata ampiamente ipotizzata per molto tempo ma, fino a poco tempo fa, non erano noti limiti inferiori concreti su modelli generali di calcolo.

La soddisfabilità è il problema di decidere se una data formula booleana ha almeno un'assegnazione soddisfacente. È il primo problema che è stato dimostrato essere NP-completo ed è forse il problema NP-completo più studiato, sia per le sue proprietà teoriche che per le sue applicazioni pratiche. A Survey of Lower Bounds for Satisfiability and Related Problems esamina i limiti inferiori recentemente scoperti per la complessità temporale e spaziale della soddisfacibilità e dei problemi strettamente correlati.

Il documento passa in rassegna lo stato dell'arte dei risultati ottenuti su modelli generali di calcolo deterministici, randomizzati e quantistici e presenta le argomentazioni sottostanti in un quadro unificato. A Survey of Lower Bounds for Satisfiability and Related Problems è un riferimento prezioso per i professori e gli studenti che fanno ricerca sulla teoria della complessità o che intendono farla.