Complessità: Introduzione

Question 1

Definizione di complessità

Answer 1

Sia M MdT deterministico, complessità in tempo è definita come

tc_M: N -> N
n(lunghezza input) -> numero di transizioni eseguite da M nel caso peggiore

Question 2

Esempi di calcolo della complessità

Answer 2

1. Capire caso peggiore
2. prevedere caso pessimo
   (vedi esempi su notion)

Question 3

Notazione asintotica

Answer 3

f,g:ℕ→ℕ

• f∈O(g) quando∃c≥0,∃n₀∈ℕ t.c. ∀n≥n₀f(n)≤c⋅g(n)
• f∈Ω(g) quando∃c≥0,∃n₀∈ℕ t.c. ∀n≥n₀f(n)≥c⋅g(n)
• f∈Θ(g) quando∃c≥0,∃n₀∈ℕ t.c. ∀n≥n₀f(n)∈O(g(n)), f(n)∈Ω(g(n))

Question 4

O-piccolo e similarità

Answer 4

• f∈o(g(n)) quando lim(n→+∞){f(n)/g(n)}=0f∈o(g(n))⇒f∈O(g(n))
• f∼g(n) quando lim(n→+∞){f(n)/g(n)}=1f∼g⇒f∈Θ(g(n))

Question 5

Complessità MdT multitraccia

Answer 5

M MdT multitraccia
tc_M(n)=f(n)
->
M’ MdT standard
tc_M’(n)=f(n)

Question 6

Complessità MdT a k nastri (dim)

Answer 6

M a k nastri tc_M(n)=f(n) -> M’ std tc_M’\in O(f(n)^2)

Sia w stringa, |w|=n su cui esegue max #transizioni cioè f(n)
vediamo M’ std come simula t-esima transizione

k nastri -> 2k +1 tracce

1. Raccolta informazioni
   testina M’ si legge pos testina poi legge nastro
   (O(t) + O(t))*k = transizioni per trovare testina e tornare indietro (t perchè è il massimo numero di transizioni)
2. Simulazione transizione
   2*O(t+1) ricerca e scrittura nella cella accanto e tornare indietro

2kO(t) transizione -> k nastri per tc_M’=sum(1,f(n))2kO(t) -> O(f^2(n))

Question 7

t_{c_m}(n) di MdT non deterministica

Answer 7

Sia MdT non det. con tc_M=f(n) e d grado non determinismo
M’ MdT det equivalente
tc_M’=O(f^2(n)d^f(n))

Dim: si usano 3 nastri
generazione computazioni è #computazioni è d^f(n)
simulazione è f(n)

Quindi MdT 3 nastri tc_M(n) = O(f(n)*d^f(n))
Con MdT std O(f^2(n) d^f(n))

Question 8

Proprietà complessita MdT

Answer 8

A parità di lunghezza è sempre possibile trovare MdT che accetta stringa con #transizioni inferiore ma stesso carattere

Non esiste un limite superiore per la complessità

Esistono linguaggi per cui è possibile trovare sempre una MdT migliore (più efficiente)

Question 9

Esempi di tempi di MdT non deterministiche

Answer 9

(vedi notion, MdT non det. che accetta stringhe palindrome)

Question 10

Definizione di P e NP

Answer 10

P = {linguaggi per cui esiste M det t.c. li accetta in tc_M=O(n^r)}
NP = (linguaggio per cui esiste M NON det. t.c li accetta in tc_M=O(n^r)}