Week 6
Topics covered in class
- More on r.e. sets; various closure properties and characterizations
- Parameter theorem (S-m-n theorem)
- Reductions of problems; Many-one reducibility
- m-complete sets; K is m-complete
Relevant sections in the textbook
Chapter 4: sections 4,5,6.
Recommended exercises from the book
Ch. 4.4: exercises 2,3,4,7,8,9,10a,11.
Ch. 4.5: exercises 1,2.
Ch 4.8: exercises 1,2,3,4,5,6,9,12.