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