Il Prof. Rossi ha definito la TM come una macchina in cui, ad ogni transizione, la testina si muove o a destra o a sinistra. (TODO, mid)
Il Prof. Verdi ha definito la macchina di Turing come una macchina in cui, ad ogni transizione, la testina può muoversi di una cella a sinistra, oppure stare ferma, oppure muoversi di due celle a destra. (TODO, mid)
Definire la classe coP e spiegare la differenza con $\bar P$ (insieme complementare di P)
Definire la classe $coNP$ e spiegare la differenza con $\bar {NP}$ (cioè l’insieme complementare di NP).
Se si dimostrasse che $P = NP$ allora ne conseguirebbe che $NP = coNP$?
Problema Connectivity
Problema Connectivity e SAT
Connectivity è NP-hard
Connectivity in NP
Il vostro compagno riduce un problema $\Pi$ a SAT