The test will cover the follwing material.

* mapping reducibility (implications to decidability/recognizablility)
* Rice's theroem
* intro to Complexity: definition of time classes, P, NP and coNP
* the meaning of the P vs NP question.
* polytime reducibility, the relation <=p and its implications 
* NP-completeness. a reminder: here is the general template of a proof that A is NPC :
   - show that A is in NP. usually by showing a polynomial verifier.
   - find an NPC language B (you will get a list of relevant ones in the test)
  and show that B <=p A, that is "B is solvable polynomially if A is". This
  shows that A is NP-hard.
   - combining the fact that A is in NP and that it is NP-hard shows that A is NPC.
  one comment : try to look for a language B that seems relevant to A, as this
 will allow for a simpler reduction)