Теория на изчислимостта и сложността; EWST Превод
Стивън Хоумър и Алън Л. Селман
Springer Verlag, Ню Йорк, 2011
ISBN 978-1461406815
Това преработено и разширено издание на теорията на изчислимостта и сложността съдържа основни материали, които са основните знания на изчислителната теория. класически към количествените аспекти на теорията на сложността. Специални заглавия за неразрешимост, NP-пълнота и относителна изчислимост завършват работата, която се фокусира върху ограниченията на изчислимостта и разграниченията между осъществимо и нерешено.
По същество ново съдържание в това издание включва:
* глава за неравномерността, която изучава булеви схеми, класове за консултиране и важния резултат от Karp-Lipton
* определения и свойства на класове с основна вероятностна сложност
* изследване на променливата машина на Тюринг и класовете на еднородни вериги
* въведение в преброяването на класовете, включително резултатите от Valiant и Vazirani и Toda
* задълбочено третиране на доказателството, че IP е идентичен с PSPACE
Теми и функции:
* Кратки, фокусирани материали обхващат най-фундаменталните концепции и резултати в областта на съвременната теория на сложността, включително NP теория за пълнота, NP твърдост, полиномиална йерархия и пълни проблеми за други класове на сложност
* Съдържа информация, която иначе съществува само в литературата и я представя по унифициран, опростен начин; например за попълване на класове на сложност, проблеми с търсенето и междинни проблеми в NP
* Предоставя основна математическа основна информация, включително раздели по логика и теория на числата и алгебра
* Подкрепено от множество упражнения и допълнителни проблеми за подсилване и самообучение
С достъпността и добре проектираната организация този текст/справка е отличен ресурс и ръководство за тези, които искат да развият солидна основа в компютърната теория. Завършилите начинаещи, напреднали студенти и специалисти, занимаващи се с компютърна теория, теория на сложността и изчисления, ще намерят книгата като основен и практичен инструмент за обучение.