Spring 2022 exam questions from "Logic and complexity".

---

You will get a randomly chosen question from the following four.

(1) Fagin's theorem and the characterization of spectra as NE sets.

(2) Nepomnjascij's theorem.

(3) Herbrand's theorem and the KPT theorem.

(4) Quantitative Godel's Second incompleteness theorem.