The forum of the Computer Science students of the University of Pisa

Domande Orale Degano

Domande orale Masetti:
- Dim. che I={1} è completo per R
- Teorema del passaggio da una MdT non det. ad una MdT det
- Che cos'è NP? Ed un esempio
- Come si classificano due classi? (le 4 proprietà)
- Qual è la F nella riduzione <=F checlassifica P ed NP ? (logspace)
- Dim. le 4 proprietà sopra nel caso <=LOGSPACE tra P ed NP
- Dim. che K è RE e non R
- Definizione insieme R ed RE
- Perché K not<= K segnato e K segnato not<= K ?
- INF <= CONST
- CONST è R ? (no)
- Dim. che CONST non è R
- K <= CONST

Devo dire che personalmente Masetti mette a proprio agio e ti fa aiuta sempre quando può, a differenza del Degano che non sempre lo fa.
Orale con degano
- sia f calcolabile totale, dire se A_f={i| per ogni x phi_i(x) = f(x)} e' R, R.E, i.i.r.f e darne una motivazione
- enunciare e dimostrare teorema di rice
- enunciare e dimostrare teorema pre-rice (1.10.19 delle dispense)
- dimostrare che le riduzioni tramite P classificano sia P che NP, si dimostra sulla falsa riga del teorema 3.5.2