Teorija računanja in kompleksnosti

Steven Homer in Alan L. Selman
Springer Verlag New York, 2011

ISBN 978-1461406815

Ta revidirana in razširjena izdaja teorije računanja in kompleksnosti vsebuje bistvene materiale, ki so osnovno znanje iz teorije računanja. Knjiga je samostojna, s predhodnim poglavjem, ki opisuje ključne matematične koncepte in notacije ter naslednja poglavja, ki se gibljejo od kvalitativnih vidikov klasične teorije računanja do količinskih vidikov teorije kompleksnosti. Namenska poglavja o neodločljivosti, popolnosti NP in relativne izračunljivosti zaokrožujejo delo, ki se osredotoča na omejitve izračunljivosti in razlike med izvedljivimi in nepremagljivimi.

Precej novih vsebin v tej izdaji vključuje:

* poglavje o neenotnosti, ki preučuje Boolove kroge, nasvete in pomemben rezultat Karp-Lipton

* definicije in lastnosti osnovnih verjetnostnih razredov kompleksnosti

* študija izmeničnega Turingovega stroja in razredov enotnega vezja

* uvod v štetje razredov, vključno z rezultati Valiant in Vazirani ter Toda

* temeljita obravnava dokaza, da je IP enak PSPACE

Teme in značilnosti:

* Kratki, osredotočeni materiali pokrivajo najbolj temeljne koncepte in rezultate na področju sodobne teorije kompleksnosti, vključno s teorijo popolnosti NP, trdoto NP, polinomsko hierarhijo in popolnimi problemi za druge razrede kompleksnosti

* Vsebuje informacije, ki sicer obstajajo le v raziskovalni literaturi in jih predstavljajo na enoten, poenostavljen način; na primer o dopolnitvah razredov kompleksnosti, iskalnih težavah in vmesnih težavah v NP

* Zagotavlja ključne matematične informacije o ozadju, vključno s poglavji o logiki in teoriji števil in algebre

* Podprto s številnimi vajami in dopolnilnimi težavami za namene krepitve in samostojnega učenja

S svojo dostopnostjo in dobro zasnovano organizacijo je to besedilo / referenca odličen vir in vodilo za tiste, ki želijo razviti trdno podlago v teoriji računalništva. Začetni diplomanti, napredni dodiplomci in strokovnjaki, vključeni v teoretično računalništvo, teorijo kompleksnosti in računanje, bodo knjigo našli bistveno in praktično učno orodje.

 

Kazalo

  1. PRELIMINARIJE
    Besede in jeziki
    K-adic predstavljanje
    Delne funkcije
    Grafi
    Procesna logika
    Kardinalnost
    Elementarna algebra
  2. UVOD V OBVEZNOST
    Turing Machines
    Turing-Machine koncepti
    Variacije strojev Turing
    Cerkvena teza
    RAM-ji
  3. NEPOSREDNOST
    Odločitvene težave
    Nepredvidljive težave
    Funkcije pare
    Izračunljivo število računov
    Zaustavitev težave, zmanjšanja in dokončanja kompleta
    S-m-n izrek
    Recursion izrek
    Rižev izrek
    Turing Reductions in Oracle Turing Machines
    Izrek izreka, nadaljevanje
    Reference
    Dodatne težave v domači nalogi
  4. UVOD V TEORIJO KOMPLEKSNOSTI
    Kompleksnostni razredi in kompleksnostni ukrepi
    Predpogoji
  5. OSNOVNI REZULTATI TEORIJE KOMPLEKSIJE
    Linearna kompresija in hitrost
    Konstruktivne funkcije
    Zmanjševanje traku
    Vključenost odnosov
    Odnosi med standardnimi razredi
    Rezultati ločevanja
    Prevajalske tehnike in obloge
    Odnosi med standardnimi razredi – Nadaljevanje
    Dodatek razredov kompleksnosti: Immerman-Szelepcsenyi izrek
    Dodatne težave v domači nalogi
  6. NONETERMINIZEM IN NP-COMPLETENESS
    Karakterizacija NP
    Razred P
    Enumeracije
    NP-popolnost
    Cookov-Levinov izrek
    Več NP-Complete Težave
    Dodatne težave v domači nalogi
  7. RELATIVNA OBDOBRITEV
    NP-trdota
    Težave pri iskanju
    Struktura NP
    Kompozitna številka in izomorfizem grafov
    Refleksija
    Polinomska hierarhija
    Popolne težave za druge razrede kompleksnosti
    Dodatne težave v domači nalogi

NEONIFORMNA KOMPLEKSNOST
Polinomske velikosti družine vezij
Nasveti razredov
Nizke in visoke hierarhije

  • PARALLELISM
    Nadomestni Turing Machines
    Enotne družine vezij
    Visoko vzporedni problemi
    Pogoji izenačevanja
    Nadomestni Turing Machines
    PROBABILISTIČNE KOMPLEKSNOSTNE RAZREDE

Razred PP
Razred RP
ZPP razreda
Razred BPP
Naključno izbrane funkcije Hash
Operaterji
Problem izomorfizma grafov
Dodatne težave v domači nalogi

  • UVOD V ŠTEVILO RAZREDOV
    Unikatna zadovoljivost
    Toda je izrek
    Rezultati na BPP in $ \ oplu $ P
    Dodatne težave v domači nalogi
  • INTERACTIVE PROOF SYSTEMS
    Formalni model
    Problem neizomorfizma grafov
    Igre Arthur-Merlin
    IP je vključen v program PSPACE
    PSPACE je vključen v IP
    Dodatne težave v domači nalogi

Prednja stvar s predgovo in vsebino

[postscript]
[PDF]

Pomembne povezave:

 

Original v angleščini Alan Selman : https://www.cse.buffalo.edu//~selman/book/

Leave a Reply

Your email address will not be published. Required fields are marked *