Computability And Complexity Theory Book

	Preface
1	Preliminaries	1
1.1	Words and Languages	1
1.2	K-adic Representation	2
1.3	Partial Functions	3
1.4	Graphs	4
1.5	Propositional Logic	6
1.6	Cardinality	8
1.7	Elementary Algebra	11
2	Introduction to Computability	22
2.1	Turing Machines	23
2.2	Turing-Machine Concepts	26
2.3	Variations of Turing Machines	28
2.4	Church's Thesis	34
2.5	RAMs	36
3	Undecidability	41
3.1	Decision Problems	41
3.2	Undecidable Problems	43
3.3	Pairing Functions	46
3.4	Computably Enumerable Sets	47
3.5	Halting Problem, Reductions, and Complete Sets	50
3.6	S-m-n Theorem	53
3.7	Recursion Theorem	55
3.8	Rice's Theorem	57
3.9	Turing Reductions and Oracle Turing Machines	59
3.10	Recursion Theorem, Continued	66
4	Introduction to Complexity Theory	72
4.1	Complexity Classes and Complexity Measures	74
4.2	Prerequisites	77
5	Basic Results of Complexity Theory	78
5.1	Linear Compression and Speedup	80
5.2	Constructible Functions	86
5.3	Tape Reduction	90
5.4	Inclusion Relationships	97
5.5	Separation Results	107
5.6	Translation Techniques and Padding	111
5.7	Relations between the Standard Classes - Continued	115
6	Nondeterminism and NP-Completeness	122
6.1	Characterizing NP	123
6.2	The Class P	124
6.3	Enumerations	126
6.4	NP-Completeness	128
6.5	The Cook-Levin Theorem	130
6.6	More NP-Complete Problems	136
7	Relative Computability	145
7.1	NP-Hardness	147
7.2	Search Problems	151
7.3	The Structure of NP	153
7.4	The Polynomial Hierarchy	162
7.5	Complete Problems for Other Complexity Classes	170
	References	181
	Author Index	187
	Subject Index	191