22C:131: Limits of Computation
On the midterm
The midterm is on Friday, March 9th, 5:00-7:00 pm in
105 MLH. It is open notes/textbook and you are free
to bring printouts of solutions posted on the coursepage
or from elsewhere on the internet.
There will be four problems on the exam.
Each problem involves a short proof or construction.
Here is a list of topics that each of the problem covers.
- Problem 1: Decidability, Turing-recognizability, proving
a language undecidable, proving a language Turing-unrecognizable.
- Problem 2: P, NP, NP-completeness, consequences of P and
NP being equal.
- Problem 3: Countable and uncountable sets, diagonalization,
proving languages undecidable via counting/diagonalization arguments.
- Problem 4: Undecidability of PCP and MPCP.