|
UPPSALA UNIVERSITET Matematiska institutionen Vera Koponen |
In order to pass the course it is necessary to supply a correct explanation in
each assignment of the exam. One does not necessarily have to give formal
definitions or supply full algorithms, but the essential thing, by which I will
judge your explanations, is that you have explained in a clear and coherent way the essential
idea(s). In addition to this exam one also has to solve assignments as
explained on the home page of the course and this will determine the grade,
according to the rule explained on the home page.
This is what you must be able to explain on the exam:
1. What it means for a deterministic or non-deterministic Turing machine to compute within time/space bound f(n).
2. Why every problem in NTIME(f(n)) belongs to TIME(c^f(n)) for some c > 1, and why
NTIME(f(n)) is included in SPACE(f(n)).
3. What the Gap theorem says.
4. The notion of proper complexity function and to explain roughly what
the Time hierarchy theorem says.
5. Characterize the class NP in terms of polynomialy decidable and
polynomially bounded relations; and what these notions mean.
6. Know what the problem CLIQUE is (as explained in the book) and be able to explain how to
reduce CLIQUE to the problem asking whether a given graph is isomorphic to a subgraph of another graph;
and why this shows that the later problem is NP-complete if the first is.
7. Describe the Solovay-Strassen randomized primality test (which you can find in my notes). You don't
need to know by heart how to define the Legendre/Jacobi-symbol, but you must be able to explain how
a certain congruence relation (involving that symbol) is relevant for the algorithm.
8. Explain the notion of an oracle machine M^? and explain what the class P^NP is.