Computational Complexity Theory

 

Exercises

In order to take the course's exam, one must submit all but one of the home-assignments!
 

Exe #

PS file

PDF file

Sol  PS file

Sol PDF file

Due

Remarks

1

ex01.ps

ex01.pdf

sol01.ps

sol01.pdf

30/10/02

In question 3 – Lpal is the language of

palindromes we saw in class.

2

ex02.ps

ex02.pdf

sol02.ps

sol02.pdf

13/11/02

- All the reductions in the exercise are

polynomial time Karp reductions.

- Question 3 – SGI – the graphs are

undirected.

3

Ex3 on exercise site

13/11/02

Solutions will be on the site on 10/11.

4

ex04.ps

ex04.pdf

sol04.ps

sol04.pdf

27/11/02

 

5

ex05.ps

ex05.pdf

sol05.ps

sol05.pdf

11/12/02

 

6

Ex6 on exercise site

14/12/02

 

7

ex07.ps

ex07.pdf

sol07.ps

sol07.pdf

1/1/03

 

8

ex08.ps

ex08.pdf

sol08.ps

sol08.pdf

15/1/03