|
|
libcats.org
A Survey of Lower Bounds for Satisfiability and Related ProblemsDieter Melkebeek vanNP-completeness arguably forms the most pervasive concept from computer science as it captures the computational complexity of thousands of important problems from all branches of science and engineering. The P versus NP question asks whether these problems can be solved in polynomial time. A negative answer has been widely conjectured for a long time but, until recently, no concrete lower bounds were known on general models of computation. Satisfiability is the problem of deciding whether a given Boolean formula has at least one satisfying assignment. It is the first problem that was shown to be NP-complete, and is possibly the most commonly studied NP-complete problem, both for its theoretical properties and its applications in practice. A Survey of Lower Bounds for Satisfiability and Related Problems surveys the recently discovered lower bounds for the time and space complexity of satisfiability and closely related problems. It overviews the state-of-the-art results on general deterministic, randomized, and quantum models of computation, and presents the underlying arguments in a unified framework. A Survey of Lower Bounds for Satisfiability and Related Problems is an invaluable reference for professors and students doing research in complexity theory, or planning to do so.
Скачать книгу бесплатно (pdf, 704 Kb)
Читать «A Survey of Lower Bounds for Satisfiability and Related Problems» EPUB | FB2 | MOBI | TXT | RTF
* Конвертация файла может нарушить форматирование оригинала. По-возможности скачивайте файл в оригинальном формате.
Популярные книги за неделю:
Тестирование Дот Ком, или Пособие по жестокому обращению с багами в интернет-стартапахАвтор: Роман Савин
Размер книги: 5.26 Mb
Система упражнений по развитию способностей человека (Практическое пособие)Автор: Петров Аркадий НаумовичКатегория: Путь к себе
Размер книги: 818 Kb
Сотворение мира (3-х томник)Автор: Петров Аркадий НаумовичКатегория: Путь к себе
Размер книги: 817 Kb
Только что пользователи скачали эти книги:
The Hydrogen AtomАвтор: S.G. Karshenboim, Автор: F.S. Pavone, Автор: F. Bassani, Автор: M. Inguscio, Автор: T.W. HänschКатегория: Physics, Lecture notes
Размер книги: 4.29 Mb
THE OMEGA FILE. Countdown to 1997 Northern ShutdownАвтор: BRANTONКатегория: Непознанное
Размер книги: 3 Kb
Angie Fox - 04 The Last of the Demon SlayersАвтор: Angie FoxКатегория: Paranormal
Размер книги: 241 Kb
|
|
|