A kiszámíthatóság és a komplexitás elmélete; EWSTranslate
Második kiadás
Springer Verlag, New York, 2011
ISBN 978-1461406815
A kiszá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 alapismereteit képviselik. A könyv önálló, egy előzetes fejezet leírja a legfontosabb matematikai fogalmakat és jelöléseket, valamint az azt követő fejezetek, amelyek a klasszikus számítási elmélet kvalitatív aspektusaitól a komplexitáselmélet kvantitatív aspektusai felé mozdulnak el. A nem deklarálhatóságról, az NP-teljességről és a relatív kiszámíthatóságról szóló külön címek egészítik ki az első kiadást, amely a kiszámíthatóság korlátaira, valamint a megvalósítható és megoldatlan közötti különbségekre összpontosít.
A második 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 alapos kezelése, hogy az IP azonos 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 komplexitási osztály komplexekről, keresési problémákról és köztes problémákról az NP-ben, nem egységes és párhuzamos komplexitáselméletről, valószínűségi komplexitási osztályokról, számlálási osztályokról és interaktív bizonyítási rendszerekről.
* 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.