Теорія обчислюваності та складності; EWSTПерекласти
Стівен Гомер та Алан Л. Селман
Springer Verlag, Нью-Йорк, 2011
ISBN 978-1461406815
Це переглянуте та розширене видання теорії обчислюваності та складності містить основні матеріали, які є базовими знаннями обчислювальної теорії. класичний до кількісних аспектів теорії складності. Виділені заголовки про невизначеність, повноту NP та відносну обчислюваність завершують роботу, яка фокусується на обмеженнях обчислюваності та розрізненні між здійсненним та неможливим для вирішення.
По суті новий вміст цього видання включає:
* розділ про нерівномірність, який вивчає логічні схеми, класи консультування та важливий результат Карпа-Ліптона
* визначення та властивості класів фундаментальної імовірнісної складності
* вивчення змінного апарату Тьюрінга та класів однорідних ланцюгів
* вступ до підрахунку класів, включаючи результати Валіант, Вазірані та Тода
* детальна обробка доказу того, що ІС ідентичний PSPACE
Теми та особливості:
* Стислі, цілеспрямовані матеріали охоплюють найбільш фундаментальні концепції та результати в галузі сучасної теорії складності, включаючи теорію повноти NP, твердість NP, поліноміальну ієрархію та повні проблеми для інших класів складності
* Містить інформацію, яка в іншому випадку існує лише в літературі, та подає її в уніфікованій, спрощеній формі; наприклад, про заповнення класів складності, проблеми пошуку та проміжні проблеми в NP
* Надає базову математичну довідкову інформацію, включаючи розділи з логіки та теорії чисел та алгебри
* Підкріплюється численними вправами та додатковими проблемами для підкріплення та самостійного вивчення
Завдяки доступності та добре продуманій організації цей текст/довідник є чудовим джерелом та керівництвом для тих, хто хоче створити міцну основу в теорії комп’ютерів. Початківці, випускники, просунуті студенти та фахівці, які займаються теорією комп’ютера, теорією складності та розрахунками, знайдуть книгу важливим та практичним інструментом навчання.