Sipser: Chapter 7
From CSWiki
Contents |
[edit]
Time Complexity
From this point on, Sipser begins the discussion on complexity theory. This chapter introduces the concept of time complexity. Problems that are computationally solvable in theory might not be solvable in practice. For example, the process of solving the problem might take too long.
Relationship among classes of languages _______________________________________________ | Turing-recognizable | | _____________________________________________ | || Turing-decidable || || ___________________________________________ || ||| TIME(f(n)) ||| ||| _________________________________________ ||| |||| Context-Free Languages |||| |||| _______________________________________ |||| ||||| Regular Languages ||||| |||||_______________________________________||||| ||||_________________________________________|||| |||___________________________________________||| ||_____________________________________________|| |_______________________________________________|
[edit]
Sections
Section 7.1
Section 7.2
Section 7.3
Section 7.4
Section 7.5
[edit]
Selected solutions
Exercises 7.1(c), 7.1(d), 7.2(c), and 7.2(d) and Problems 7.15, 7.22, 7.31, and 7.38 only, please!
[edit]
