Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Melkebeek D. — A Survey of Lower Bounds for Satisfiability and Related Problems
Melkebeek D. — A Survey of Lower Bounds for Satisfiability and Related Problems



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: A Survey of Lower Bounds for Satisfiability and Related Problems

Автор: Melkebeek D.

Аннотация:

NP-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.


Язык: en

Рубрика: Разное/

Статус предметного указателя: Неизвестно

ed2k: ed2k stats

Год издания: 2007

Количество страниц: 125

Добавлена в каталог: 18.12.2016

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте