Teoria Computabilității și Complexității

Sursă originală: https://cse.buffalo.edu/~selman/book/

Steven Homer și Alan L. Selman

Springer Verlag, New York, 2011

ISBN 978-1461406815

Această ediție revizuită și extinsă a teoriei computabilității și complexității cuprinde materiale esențiale care sunt cunoștințele de bază ale teoriei de calcul.Cartea este autonomă, cu un capitol preliminar care descrie concepte matematice cheie și notații și capitole ulterioare care se mută din aspectele calitative ale teoriei computabilității clasice la aspectele cantitative ale teoriei complexității. Titlurile dedicate privind nedecidabilitatea, NP-completitudinea și computabilitatea relativă rotunjesc activitatea, care se concentrează asupra limitărilor computabilității și a distincțiilor dintre fezabile și imposibil de rezolvat.

Conținutul nou substanțial în această ediție include:

* un capitol despre neuniformitate care studiază circuitele booleene, clase de consiliere și rezultatul important al lui Karp-Lipton

* definiții și proprietăți ale claselor de complexitate probabilistică fundamentală

* un studiu al mașinii Turing alternante și al claselor circuitelor uniforme

* o introducere în numărarea claselor, inclusiv rezultatele lui Valiant și Vazirani și ale lui Toda

* un tratament amănunțit al dovezii că IP-ul este identic cu PSPACE

Subiecte și caracteristici:

* Materialele concise, concentrate, acoperă cele mai fundamentale concepte și rezultate în domeniul teoriei complexității moderne, inclusiv teoria NP-completitudine, duritatea NP, ierarhia polinomală și probleme complete pentru alte clase de complexitate

* Conține informații care altfel există doar în literatura de specialitate și o prezintă într-o manieră unificată, simplificată; de exemplu, despre completarea clase de complexitate, probleme de căutare și probleme intermediare în NP

* Oferă informații fundamentale matematice de fond, inclusiv secțiuni privind logica și teoria numărului și algebra

* Sprijinit de numeroase exerciții și probleme suplimentare pentru întăriri și auto-studii

Cu accesibilitatea și organizarea bine concepută, acest text / referință este o resursă și un ghid excelent pentru cei care doresc să dezvolte o bază solidă în teoria computerizării. Absolvenții începători, studenții avansați și profesioniștii implicați în teoria informaticii, teoria complexității și calculele vor găsi cartea un instrument esențial și practic de învățare.

Cuprins

  1. PRELIMINARII
    • Cuvinte și limbi
    • Reprezentarea K-adică
    • Funcții parțiale
    • Grafice
    • Logica propozițională
    • cardinality
    • Algebra elementară
  2. INTRODUCERE LA COMPUTABILITATE
    • Mașinile Turing
    • Turing-Machine Concepte
    • Variațiile mașinilor Turing
    • Teza de doctorat
    • RAMs
  3. impreciziei
    • Probleme de rezolvare
    • Probleme nedecidibile
    • Funcțiile de asociere
    • Seturi computabile enumerabile
    • Probleme de oprire, reduceri și seturi complete
    • Teorema lui Smm
    • Teorema de recurs
    • Teorema lui Rice
    • Turing Reductions și Oracle Turing Machines
    • Teorema de recurs, continuată
    • Referințe
    • Probleme suplimentare la temele de acasă
  4. INTRODUCERE LA TEORIA DE COMPLEXITATE
    • Clasele de complexitate și măsurile de complexitate
    • Cerințe preliminare
  5. REZULTATELE DE BAZĂ A TEORIEI DE COMPLEXITATE
    • Compresie și accelerare liniară
    • Funcții constructive
    • Reducerea benzii
    • Relațiile de incluziune
      • Relațiile dintre clasele standard
    • Rezultatele separării
    • Tehnici de traducere și împachetare
    • Relațiile dintre clasele standard – continuare
      • Completări ale claselor de complexitate: Teorema lui Immerman-Szelepcsenyi
    • Probleme suplimentare la temele de acasă
  6. NEDETERMINISMUL ȘI NP-COMPLETE
    • Caracterizarea NP
    • Clasa P
    • enumerările
    • NP-Completitudine
    • Teorema lui Cook-Levin
    • Mai multe probleme NP-complete
    • Probleme suplimentare la temele de acasă
  7. COMPUTABILITATEA RELATIVĂ
    • NP-Duritate
    • Probleme de căutare
    • Structura PN
      • Numărul compozit și izomorfismul grafic
      • Reflecţie
    • Ierarhia polinomilor
    • Probleme complete pentru alte clase de complexitate
    • Probleme suplimentare la temele de acasă
      • COMPLEXITATE NONUNIFORMĂ
        • Familii de circuite cu dimensiuni polinomiale
          • Ierarhiile joase și înalte
          • PARALELISM
            • Alternarea mașinilor Turing
            • Familii familiale de circuite
            • Probleme foarte paralelizabile
            • Condiții de omogenitate
            • Alternarea mașinilor Turing
            • CLASE DE COMPLEXITATE PROBABILISTICĂ
              • Clasa PP
              • Clasa RP
                • Clasa ZPP
              • Clasa BPP
              • Alegerea funcțiilor de ștergere aleatorie
                • operatorii
              • Problema izomorfismului grafic
              • Probleme suplimentare la temele de acasă
                • INTRODUCERE LA CALCULAREA CLASELOR
                  • Satisfiabilitate unică
                  • Teorema lui Toda
                    • Rezultate pe BPP și $ \ oplu $ P
                  • Probleme suplimentare la temele de acasă
                    • SISTEME INTERACTIVE DE PROBE
                      • Modelul formal
                      • Problema non-isomorfismului grafic
                      • Jocurile Arthur-Merlin
                      • IP-ul este inclus în PSPACE
                      • PSPACE este inclus în IP
                      • Probleme suplimentare la temele de acasă

    Materia primă cu prefață și cuprins

    postscript ] 
    PDF ]

    Link-uri importante:


    Alan Selman