LEZIONE del 31 10 2018

La lezione di oggi sarà annullata per mia indisposizione e recuperata con un'altra lezione la settimana prossima.

Per favore fatemi sapere via email un paio di giorni possibili e due ore
per poter recuperare la lezione la settimana prossima.

Tenendo in conto che io ho altre lezioni il Martedi eil Venerdi dalle 1400 alle 16:30.

Nicola Galesi

Notice 31/10/2018
Today's class of Complexity Theory 8:30--10:30 is canceled due to a health problem of mine. Please if possible find
an agreement between you to recover the class during next or the other week considering I am teaching already Tue and Fri from
14:00 to 16:30.

Post has attachment
Some exercises I left to work on during classes and you might be interested to work on during this week.

Topics of 10-10-18

Time hierachy thms
NSpace hierarchy thm
Translational lemma I
Savitch thm

Topics of 8-10-18

Cook's theorem (II part)
Space hierarchy theorem

topics o f 3 -10-18

SAt to 3 SAT
Cook's Theorem

1-10-18: Topics (room alfa)
- Intro to course topics:
- Polynomial Verifier
- Def of NP and Co-NP using verifier algorithms and their equivalence with TM's def.

Books suggested for readings:
S. Arora B. Barak: Computational Complexity: A Modern Approach .
M. Sipser: Introduction To The Theory Of Computation
H. Vollmer: Introduction to Circuit Complexity - A Uniform Approach
Ding-Zhu Du, Ker-I Ko: Theory of Computational Complexity
S. Jukna: Boolean Function Complexity - Advances and Frontiers

Le lezioni iniziano dalla settimana del 1 Ottobre.

Giorni: Lun, Merc
Luogo: Aula α - Via Salaria
Ora: 08:00 -- 10:30

Classes start on the 1st October

Days: Mon + Wed
Place: Aula α - Via Salaria
Time: 8:00-10:30
Wait while more posts are being loaded