Számíthatóság és komplexitás elmélet; EWSTranslate
Steven Homer és Alan L. Selman
Springer Verlag, New York, 2011
ISBN 978-1461406815
A számíthatóság és a komplexitás elméletének ez a felülvizsgált és kibővített kiadása olyan alapvető anyagokat tartalmaz, amelyek a számítási elmélet alapismeretei. a komplexitáselmélet kvantitatív vonatkozásaihoz klasszikus. A dedikálhatatlanság, az NP-teljesség és a relatív kiszámíthatóság külön címei egészítik ki a tevékenységet, amely a kiszámíthatóság korlátozásaira és a megvalósítható és megoldatlan közötti különbségekre összpontosít.
A kiadás lényegében új tartalma a következőket tartalmazza:
* az egyenlőtlenségről szóló fejezet, amely a logikai áramköröket, a tanácsadási osztályokat és a Karp-Lipton fontos eredményét tanulmányozza
* az alapvető valószínűségi komplexitás osztályainak meghatározása és tulajdonságai
* a váltakozó Turing-gép és az egységes áramkörök osztályainak tanulmányozása
* bevezetés az osztályszámlálásba, beleértve a Valiant és Vazirani és Toda eredményeit
* annak részletes igazolása, hogy az IP megegyezik a PSPACE-vel
Témák és jellemzők:
* A tömör, koncentrált anyagok a modern komplexitáselmélet legalapvetőbb fogalmait és eredményeit fedik le, ideértve az NP-teljesség elméletét, az NP keménységét, a polinomiális hierarchiát és a többi komplexitás osztály teljes problémáit
* Olyan információkat tartalmaz, amelyek egyébként csak az irodalomban léteznek, és azokat egységes, egyszerűsített módon mutatják be; például a bonyolultsági osztályok teljesítéséről, a keresési kérdésekről és a köztes kérdésekről az NP-ben
* Alapvető matematikai háttérinformációt nyújt, beleértve a logika és a számelmélet és az algebra szakaszait
* Számos gyakorlat és további megerősítési és önálló tanulási problémák támogatják
Az akadálymentesítéssel és a jól megtervezett szervezettel ez a szöveg/hivatkozás kiváló forrás és útmutató azok számára, akik szilárd alapot akarnak kialakítani a számítógépelméletben. Kezdő diplomások, haladó hallgatók és a számítógépelméletben, a komplexitáselméletben és a számításokban részt vevő szakemberek a könyvet alapvető és gyakorlati tanulási eszköznek találják.