Przegląd dolnych granic dla spełnialności i powiązanych problemów

Oryginalny tytuł:

A Survey of Lower Bounds for Satisfiability and Related Problems

Zawartość książki:

NP-zupełność jest prawdopodobnie najbardziej rozpowszechnionym pojęciem w informatyce, ponieważ obejmuje złożoność obliczeniową tysięcy ważnych problemów ze wszystkich dziedzin nauki i inżynierii.

Pytanie P versus NP dotyczy tego, czy problemy te można rozwiązać w czasie wielomianowym. Negatywna odpowiedź była powszechnie przypuszczana przez długi czas, ale do niedawna nie były znane żadne konkretne dolne granice dla ogólnych modeli obliczeniowych.

Satysfakcjonowalność to problem polegający na ustaleniu, czy dana formuła logiczna ma co najmniej jedno spełniające ją przyporządkowanie. Jest to pierwszy problem, dla którego wykazano, że jest NP-zupełny i jest prawdopodobnie najczęściej badanym problemem NP-zupełnym, zarówno ze względu na jego właściwości teoretyczne, jak i zastosowania w praktyce. Książka A Survey of Lower Bounds for Satisfiability and Related Problems zawiera przegląd niedawno odkrytych dolnych ograniczeń na czasową i przestrzenną złożoność problemu spełnialności i problemów blisko z nim związanych.

Przegląda najnowsze wyniki dotyczące ogólnych deterministycznych, losowych i kwantowych modeli obliczeń oraz przedstawia leżące u ich podstaw argumenty w ujednoliconych ramach. A Survey of Lower Bounds for Satisfiability and Related Problems jest nieocenionym źródłem informacji dla profesorów i studentów prowadzących badania w zakresie teorii złożoności lub planujących takie badania.