Complessità computazionale

Algoritmi:

• efficienti: soluzione in tempo polinomiale rispetto alla dim. dell’input
• non efficienti: soluzione in tempo esponenziale

Problemi:

• facili / trattabili (algoritmo efficiente)
• difficili / intrattabili (algoritmo non efficiente)
  • difficilissimi / probabilmente intrattabili
• dim. difficili (algoritmo non efficiente e posso dimostrare che non esiste alg. efficiente)
• impossibili / indecidibili (non esiste algoritmo che li risolve)

Macchina di Turing

• $M = (Q, \Sigma, q_0, \delta)$

• Tesi di Church-Turing: non esiste nessun formalismo di calcolo che sia più potente della TM

  → se un problema è umanamente calcolabile, allora esisterà una TM in grado di risolverlo

• configurazione: $($stato, simbolo sotto testina, stringa a sx, stringa a dx$)$

• tempo di calcolo $t_M(x)$: lunghezza della sequenza di configurazioni che la macchina attraversa con input $x$

• funzione di complessità temporale $T_M(n) = \max(\{t_M(x) \ | \ |x|=n\})$

Macchina di Turing multi-nastro

• $k$ nastri di lettura e scrittura
• $\delta: Q \times \Sigma ^ k \rarr Q \times \Sigma^k \times \{\larr, \rarr, \sqcup\}^k$
• sono più veloci MA non più potenti (esiste sempre una traduzione verso la TM a singolo nastro)