Script: http://www.cse.buffalo.edu/~selman/book/

Steven Homer és Alan L. Selman

Springer Verlag New York, 2011

ISBN 978-1461406815

Ez átdolgozott és kibővített kiadása Computability és komplexitás elmélet tartalmaz alapvető anyagok, amelyek az alapvető ismeretek elméleti számítási. A könyv önálló, egy előzetes bemutató fejezetben kulcsfontosságú matematikai fogalmak és jelölések és az azt követő fejezetek mozog a minőségi szempontok a klasszikus Kiszámolhatóság elmélet a mennyiségi szempontok a komplexitás elmélet. Dedikált fejezetek döntésképtelenség, NP-teljesség, és a relatív kiszámíthatóság egészítik ki a mű, melynek középpontjában a korlátozásokat a kiszámíthatóság és a különbséget a megvalósítható és kezelhetetlen.

Jelentős új tartalom ebben a kiadás tartalmazza:

* Egy fejezetet az egyenetlenség tanul logikai áramkörök, tanácsadás osztályok és a fontos eredménye Karp-Lipton

* Meghatározások és tulajdonságainak alapvető valószínűségi bonyolultsági osztályok

* Egy tanulmányt a váltakozó Turing-gép és egységes áramkör osztályok

* Bevezetést számítva osztályok eredményeit is beleértve Valiant és Vazirani és Toda

* Alapos kezelés a bizonyíték arra, hogy az IP azonos PSPACE

Témák és funkciók:

* Tömör, koncentrált anyag terjed a legalapvetőbb fogalmakat és eredményeket terén a modern komplexitás elmélet, beleértve az elmélet a NP-teljesség NP-, a polinom hierarchia, és teljes problémák más bonyolultsági osztályok

* Információkat tartalmaz, ami egyébként létezik, csak a szakirodalom és bemutatja, hogy egy egységes, egyszerűsített módon; például mintegy kiegészíti a bonyolultsági osztályok, keresési problémák, és a köztes problémák NP

* Biztosítja kulcs matematikai háttér-információk, beleértve a szakaszok a logikán és számelmélet és az algebra

* Támogató különféle gyakorlatokat és a kiegészítő problémákat megerősítés és önálló tanulás céljából

A hozzáférhetőség és jól kialakított szervezet, ez a szöveg / referencia kiváló segítség és útmutató azok számára, akik fejleszteni szilárd alapokat az elmélet a számítástechnika. Kezdve a diplomások, a fejlett egyetemisták, és szakemberek az elméleti számítógép-tudomány, a komplexitás elmélet, és a számítási fogja találni a könyv egy alapvető és gyakorlati tanulási eszköz.

Tartalomjegyzék

1.BEVEZETŐ
*A szavak és nyelvek
*K-adikus képviselet
*részleges funkciók
*grafikonok
*propozicionális logika
*számosságú
*elemi algebra
2.BEVEZETÉS A kiszámíthatóság
*Turing-gépek
*Turing-gép fogalmak
*Variációk Turing gépek
*Egyház tézis
*RAM
3.döntésképtelenség
*döntési problémák
*eldönthetetlen problémák
*A párosítás funkciók
*Computably Enumerable szettek
*Megállási probléma, Kedvezmények, és a teljes készlet
*S-M-N-tétel
*rekurzió tétele
*Rice tétele
*Turing Kedvezmények és az Oracle a Turing-gép
*Rekurzió tétele, folytatás
*Referenciák
*További házi problémákat
4.BEVEZETÉS komplexitás elmélet
*Bonyolultsági osztályok és komplexitás
*Előfeltételek
5.BASIC EREDMÉNYEI bonyolultságelmélet
*Lineáris tömörítés és gyorsulása
*beépíthető funkciók
*Tape Reduction
*Inclusion kapcsolatok
*Közötti kapcsolatok, a Standard osztályok
*Válás Eredmények
*Fordítás technikák és kitöltés
*Közötti kapcsolatok, a Standard osztályok – folytatás
*Kiegészíti a bonyolultsági osztályok: A Immerman-Szelepcsenyi tétel
*További házi problémákat
6.NONDETERMINISM ÉS hogy NP-teljes
*jellemző NP
*A P. osztály
*felsorolások
*NP-teljesség
*A Cook-Levin-tétel
*További NP-teljes problémák
*További házi problémákat
7.Relatív kiszámíthatóság
*NP-keménység
*Keresés problémák
*A felépítése NP
*Összetett szám és gráfizomorfizmus
*VisszaverődésA Polinomiális hierarchiája
*Teljes problémák Egyéb bonyolultsági osztályok
*További házi problémákat
*egyenetlen KOMPLEXITÁS
*Polinom mérete családjait áramkörök
*Tanácsadás tanfolyamok
*Az alacsony és magas hierarchiák
PÁRHUZAMOSSÁG
Váltakozó Turing gépek
Egységes családjait áramkörök
Erősen párhuzamosítható problémák
egységesség feltételek
Váltakozó Turing gépek
VALÓSZÍNŰSÉGI bonyolultsági osztályok
A Class PP
RP osztály
A Class ZPP
A Class BPP
Véletlenszerűen kiválasztott Hash függvények
Az üzemeltetők
A gráfizomorfizmus probléma
További házi problémákat
BEVEZETÉS vennék CLASSES
egyedi Kielégíthetőség
Toda tétele
Eredmények a BPP és $ \ oplu $ P
További házi problémákat
INTERAKTÍV PROOF SYSTEMS
Formális modell
A Graph Non-izomorfizmus Problem
Arthur Merlin Games
IP tartalmazza PSPACE
PSPACE tartalmazza IP
További házi problémákat
Első kérdést Előszó és tartalomjegyzék

[postscript]
[PDF]