Теорија за пресметливост и сложеност; EWSTпреведи
Второ издание
Спрингер Верлаг, Newујорк, 2011 година
ISBN 978-1461406815
Ова ревидирано и проширено издание на теоријата за пресметливост и сложеност содржи основни материјали кои ги претставуваат основните познавања на компјутерската теорија. Книгата е автономна, со прелиминарно поглавје кое ги опишува клучните математички концепти и нотации и последователните поглавја кои преминуваат од квалитативните аспекти на класичната пресметковна теорија кон квантитативните аспекти на теоријата на сложеност. Посветени наслови за не-изјавување, комплетноста на НП и релативната пресметливост го заокружуваат првото издание, кое се фокусира на ограничувањата на пресметливоста и разликите помеѓу изводливо и нерешено.
Суштински новата содржина во ова второ издание вклучува:
* поглавје за нееднаквост што ги проучува буловите кола, часовите за советување и важниот резултат на Карп-Липтон
* дефиниции и својства на класи со основна веројатна сложеност
* студија за наизменичната машина Туринг и класите на униформни кола
* вовед во броење на часови, вклучувајќи ги и резултатите на Валиант и Вазирани и Тода
* темелно третирање на доказот дека ИП е идентична со PSPACE
Теми и карактеристики:
* Концизни, фокусирани материјали ги покриваат најосновните концепти и резултати од областа на современата теорија на сложеност, вклучувајќи теорија на комплетност на НП, цврстина на НП, полиномска хиерархија и целосни проблеми за другите класи на сложеност
* Содржи информации што инаку постојат само во литературата и ги презентира на унифициран, поедноставен начин; на пример, за комплекси на сложеност на класи, проблеми со пребарување и средни проблеми во НП, нерамна и паралелна теорија на сложеност, класи на веројатност за сложеност, часови за броење и системи за интерактивно докажување.
* Обезбедува основни информации за математичка позадина, вклучувајќи делови за логика и теорија на броеви и алгебра
* Поддржано од бројни вежби и дополнителни проблеми за засилување и самостојно учење
Со пристапност и добро дизајнирана организација, овој текст/референца е одличен ресурс и водич за оние кои сакаат да развијат солидна основа во компјутерската теорија. Дипломирани студенти за почетници, напредни студенти и професионалци вклучени во компјутерската теорија, теоријата на комплексноста и пресметките ќе ја најдат книгата основна и практична алатка за учење.