Теорија за пресметливост и сложеност; EWSTпреведи

Стивен Хомер и Алан Л. Селман

Спрингер Верлаг, Newујорк, 2011 година

ISBN 978-1461406815

Ова ревидирано и проширено издание на теоријата за пресметливост и сложеност содржи основни материјали кои се основно познавање на компјутерската теорија. класичен до квантитативните аспекти на теоријата на сложеност. Посветените наслови за неодлучноста, комплетноста на НП и релативната пресметливост ја заокружуваат работата, која се фокусира на ограничувањата на пресметливоста и разликите помеѓу изводливо и невозможно да се решат.

теорија

Суштински новата содржина во ова издание вклучува:

* поглавје за нееднаквост што ги проучува буловите кола, часовите за советување и важниот резултат на Карп-Липтон

* дефиниции и својства на класи со основна веројатна сложеност

* студија за наизменичната машина Туринг и класите на униформни кола

* вовед во броење на часови, вклучувајќи ги и резултатите на Валиант и Вазирани и Тода

* темелен третман на доказ дека IP е идентична со PSPACE

Теми и карактеристики:

* Концизни, фокусирани материјали ги покриваат најосновните концепти и резултати од областа на современата теорија на комплексноста, вклучувајќи теорија на комплетност на НП, цврстина на НП, полиномска хиерархија и целосни проблеми за другите класи на сложеност

* Содржи информации што инаку постојат само во литературата и ги презентира на унифициран, поедноставен начин; на пример, за завршување на часови за сложеност, прашања за пребарување и средни проблеми во НП

* Обезбедува основни информации за математичка позадина, вклучувајќи делови за логика и теорија на броеви и алгебра

* Поддржано од бројни вежби и дополнителни проблеми за засилување и самостојно учење

Со пристапност и добро дизајнирана организација, овој текст/референца е одличен ресурс и водич за оние кои сакаат да развијат солидна основа во компјутерската теорија. Дипломирани студенти за почетници, напредни студенти и професионалци вклучени во компјутерската теорија, теоријата на комплексноста и пресметките ќе ја најдат книгата основна и практична алатка за учење.