P, np, and np-completeness: the basics of computational complexity
Auteur :
Goldreich, Oded
Éditeur :
Cambridge University Press
ISBN :
9780521192484
Date de publication :
16 août 2010
Dimensions :
22,9 x 14,7 x 1,8 cm
Poids :
490 g
Langue :
Anglais
Pays d'origine :
Grande Bretagne
This undergraduate introduction to computational complexity gives a wide perspective on two central issues in theoretical computer science. It starts with the relevant background in computability, including Turing machines, search and decision problems, algorithms, circuits, and complexity classes, and then focuses on the P versus NP Question and the theory of NP-completeness.