0 Introduction
0.1 Automata, Computability, and Complexity
0.2 数学概念和术语
0.3 定义，定理，证明
0.4 证明方法
Part 1
1 Regular Languages
1.1 Finite Automata
1.2 Nondeterminism
1.3 Regular Expressions
1.4 Nonregular Languages
2 Context-Free Languages
2.1 Context-Free Grammars
2.2 Pushdown Automata
2.3 Non-Context-Free Languages
2.4 Deterministic Context-Free Languages
Part 2: Computability Theory
3 The Church-Turing Thesis
3.1 Turing Machines
3.2 Variants of Turing Machines
3.3 The Definition of Algorithm
4 Decidability
4.1 Decidable Languages
4.2 Undecidability
5 Reducibility
5.1 Undecidable Problems from Language Theory
5.2 A Simple Undecidable Problem
5.3 Mapping Reducibility
6 Advanced Topics in Computability Theory
Part 3: Complexity Theory
7 Time Complexity
7.1 Measuring Complexity
7.2 The Class P
7.3 The Class NP
7.4 NP-completeness
7.5 Additional NP-complete Problems
Published with GitBook
5 Reducibility
5 Reducibility
The methods for proving that problems are computationally unsolvable.
反证，最终能推出
A
T
M
A_{TM}
A
T
M
decidable的矛盾
computation history
mapping reducibility
results matching "
"
No results matching "
"