Introduction to theory of computation, an: an algorithmic approach
Auteur :
Ogihara, Mitsunori
Éditeur :
Springer International Publishing AG
ISBN :
9783031847394
Date de publication :
8 avr. 2025
Dimensions :
23,5 x 15,5 cm
Langue :
Anglais
Pays d'origine :
Suisse
The book extends to space complexity classes, discussing PSPACE complete problems, NL-complete problems, and proving that NL=coNL.Finally, the text ventures beyond NP-completeness, discussing Ladner’s construction of non-NPC sets, randomized complexity classes, and concepts such as BPP and the polynomial hierarchy.