libri scuola books Fumetti ebook dvd top ten sconti 0 Carrello


Torna Indietro
ARGOMENTO:  BOOKS > INFORMATICA > TESTI GENERALI

homer steven; selman alan l. - computability and complexity theory
Zoom

Computability and Complexity Theory

;




Disponibilità: Normalmente disponibile in 15 giorni
A causa di problematiche nell'approvvigionamento legate alla Brexit sono possibili ritardi nelle consegne.


PREZZO
91,98 €
NICEPRICE
87,38 €
SCONTO
5%



Questo prodotto usufruisce delle SPEDIZIONI GRATIS
selezionando l'opzione Corriere Veloce in fase di ordine.


Pagabile anche con Carta della cultura giovani e del merito, 18App Bonus Cultura e Carta del Docente


Facebook Twitter Aggiungi commento


Spese Gratis

Dettagli

Genere:Libro
Lingua: Inglese
Editore:

Springer

Pubblicazione: 03/2014
Edizione: 2nd ed. 2011





Trama

This revised and extensively expanded edition of Computability and Complexity Theory comprises essential materials that are core knowledge in the theory of computation. The book is self-contained, with a preliminary chapter describing key mathematical concepts and notations.  Subsequent chapters move from the qualitative aspects of classical computability theory to the quantitative aspects of complexity theory. Dedicated chapters on undecidability, NP-completeness, and relative computability focus on the limitations of computability and the distinctions between feasible and intractable.  Substantial new content in this edition includes:

  • a chapter on nonuniformity studying Boolean circuits, advice classes and the important result of Karp-Lipton.
  • a chapter studying properties of the fundamental probabilistic complexity classes
  • a study of the alternating Turing machine and uniform circuit classes.
  • an introduction of counting classes, proving the famous results of Valiant and Vazirani and of Toda
  • a thorough treatment of the proof that IP is identical to PSPACE

With its accessibility and well-devised organization, this text/reference is an excellent resource and guide for those looking to develop a solid grounding in the theory of computing. Beginning graduates, advanced undergraduates, and professionals involved in theoretical computer science, complexity theory, and computability will find the book an essential andpractical learning tool.

 

Topics and features:

  • Concise, focused  materials cover the most fundamental concepts and results in the field of modern complexity theory, including the theory of NP-completeness, NP-hardness, the polynomial hierarchy, and complete problems for other complexity classes
  • Contains information that otherwise exists only in research literature and presents it in a unified, simplified manner
  • Provides key mathematical background information, including sections on logic and number theory and algebra
  • Supported by numerous exercises and supplementary problems for reinforcement and self-study purposes





Sommario

Preliminaries.- Introduction to Computability.- Undecidability.- Introduction to Complexity Theory.- Basic Results of Complexity Theory.- Nondeterminism and NP-Completeness.- Relative Computability.- Nonuniform Complexity.- Parallelism.- Probabilistic Complexity Classes.- Introduction to Counting Classes.- Interactive Proof Systems.- References.- Author Index.- Subject Index.











Altre Informazioni

ISBN:

9781489989710

Condizione: Nuovo
Collana: Texts in Computer Science
Dimensioni: 235 x 155 mm
Formato: Brossura
Illustration Notes:XVI, 300 p.
Pagine Arabe: 300
Pagine Romane: xvi


Dicono di noi