Vyčíslitelnost a zložitosť teórie
Second Edition
Steven Homer a Alan L. Selman
Springer Verlag New York, 2011
ISBN 978-1461406815
Toto revidované a rozšírené vydanie vyčíslitelnosti a zložitosti teória zahŕňa základné materiály, ktoré sú hlavné poznatky v teórii počítanie. Kniha je sebestačný, s predbežným kapitola popisujúci kľúčové matematické pojmy a notácie a nasledujúcich kapitolách sa sťahujú z kvalitatívnych aspektov klasickej teórie vyčíslitelnosti na kvantitatívnych aspektov teórie zložitosti. Vyhradené kapitoly o nerozhodnutelnosti, NP-úplnosť, a relatívna vyčíslitelnosti završujú prvé vydanie, ktorá sa zameriava na obmedzenie vyčíslitelnosti a vyznamenania medzi uskutočniteľné a nepoddajný.
Podstatné nový obsah, v tomto druhom vydaní zahŕňa:
* Kapitola o nerovnomernosti štúdiu logických obvodov, rady triedy a dôležitý výsledok Karp-Lipton
* Definícia a vlastnosti základných pravdepodobnostných tried zložitosti
* Štúdia stroje striedajúcich sa Turing a jednotné obvod triedy
* Úvod do počítania tried vrátane výsledkov statočný a Vazirani a Toda
* Dôkladné ošetrenie dôkaz, že IP je totožný s PSPACE
Témy a funkcie:
* Stručné, zamerané materiály pokrývajú väčšinu základné pojmy a výsledky v oblasti modernej teórie zložitosti, vrátane teórie NP-úplnosti, NP-tvrdosť, polynomial hierarchie, a úplné problémy pre ostatných tried zložitosti
* Obsahuje informácie, ktoré inak existuje len v odbornej literatúre a prezentuje ich v jednotnom, zjednodušeným spôsobom, napríklad o dopĺňa tried zložitosti, vyhľadávanie problémov, a medziproduktov problémy v NP, nejednotné a paralelné zložitosti teórie, pravdepodobnostné triedy zložitosti, počítanie tried a interaktívne dôkazové systémy.
* Poskytuje kľúčové matematické pozadie informácie, vrátane sekcií na logike a teóriu čísel a algebre
* Podporované mnohých cvičení a doplnkových problémy pre výstuže a self-študijné účely
Vďaka svojej dostupnosti a dobre vymyslený organizácie, tento text / odkaz je vynikajúci zdroj a sprievodca pre tých, ktorí chcú rozvíjať solídne základy v teórii výpočtov. Začínajúci absolventi, pokročilé vysokoškolákov, a pracovníci zaoberajúci sa teoretickej informatike, teóriu zložitosti, a vyčíslitelnosti sa nájsť knihu základné a praktické učenie nástroj.
Obsah
- ÚVODNÁ
- Slová a jazyky
- K-ADIC zastúpenie
- Čiastkové funkcie
- Grafy
- Výrokovej logiky
- Mohutnosť
- Základné Algebra
- ÚVOD DO Vyčíslitelnost
- Turing stroje
- Turing-Machine koncepty
- Variácie Turingovej stroje
- Cirkvi práce
- RAM
- Nerozhodnutelnost
- Rozhodovacích problémov
- Nerozhodnutelné problémy
- Párovanie Funkcia
- Computably spočetné množiny
- Zastavenie Problém, zníženie, a Kompletné sady
- Smn veta
- Veta o rekurziu
- Riceovej teorém
- Turing Zníženie a Oracle Turing stroje
- Veta o rekurziu, Pokračovanie
- Referencie
- Ďalšie Domáce Problémy
- Úvod do zložitosti TEÓRIE
- Zložitosť Triedy a zložitosť Opatrenia
- Predpoklady
- ZÁKLADNÉ VÝSLEDKY teóriu zložitosti
- Lineárne kompresie a Zrýchlenie
- Konstruovatelné funkcie
- Tape Redukcia
- Inclusion Vzťahy
- Vzťahy medzi štandardné triedy
- Separačná Výsledky
- Preklad techniky a vypchávky
- Vzťahy medzi štandardné triedy - Pokračovanie
- Doplnky tried zložitosti: Immerman-Szelepcsenyi Veta
- Ďalšie Domáce Problémy
- Nedeterminismu A NP-úplnosť
- Charakterizujúce NP
- Trieda P
- Vyčíslenie
- NP-úplnosť
- Cook-Levin teorém
- Viac NP-úplných problémov
- Ďalšie Domáce Problémy
- Relatívna vyčíslitelnost
- NP-Tvrdosť
- Vyhľadávanie Problémy
- Štruktúra NP
- Kompozitný Počet a graf izomorfismu
- Odraz
- Polynóm Hierarchia
- Kompletné problémy ostatným tried zložitosti
- Ďalšie Domáce Problémy
- Nejednotné KOMPLEXNÁ
- Polynomiální Veľkosť Rodiny obvodov
- Nízke a Vysoké hierarchie
- Súbeh
- Striedanie Turing stroje
- Jednotná Rodiny obvodov
- Vysoko paralelizovatelné Problémy
- Jednotnosť podmienky
- Striedanie Turing stroje
- Pravdepodobnostné tried zložitosti
- Trieda PP
- Class RP
- Trieda BPP
- Náhodne vybrané Hash funkcie
- Graf problém izomorfismu
- Ďalšie Domáce Problémy
- ÚVOD DO POČÍTANIE TRIEDY
- Unikátny splniteľnosti
- Toda teorém
- Výsledky na BPP a parita P
- Ďalšie Domáce Problémy
- Interaktívne dôkazové systémy
- Formálne model
- Graf Non-problém izomorfismu
- Arthur-Merlin Games
- IP je zahrnutá v PSPACE
- PSPACE je zahrnuté v IP
- Ďalšie Domáce Problémy
Dôležité odkazy:
Preložené z http://cs-www.bu.edu/faculty/homer/complexitybook-vol2-webpg.html
Homepage |
|