Problemi di conteggio e test di primalità Flashcards
(12 cards)
Cosa sono i problemi di conteggio (#P)?
P = {f in F| esiste MdT non det t.c. tcM(n)=O(n^k) e forall w in {0,1}^k, f(w) è #computazioni accettanti di M su w}
Sia F={f:{0,1}^n->N| f funzione}
FP = {f in F| esiste mdt det che calcola f tcM(n)=O(n^k)}
Cosa significa FP ⊆ #P?
f in FP sia M mdt det pol che calcola f
Costruiamo N mdt non det
1. calcolo f(w)=k (in tempo det. pol)
2. genero k computazioni distinte che considero tutte accettanti
Cosa implica FP = #P? È vero che da ciò segue P = NP?
Sia L in NP, M mdt non det pol che accetta L
F funzione che conta numero di computazioni di M, allora f in #P => (hp) in FP
Esiste N mdt det pol. che calcola f
1) calcolo f(w)=k (N det. pol)
2) k> 0, accetto w altrimenti rifiuto
Se P = PSpace allora FP = #P?
Sia f in #P -> M mdt non det pol.
f conta computazioni accettanti di M
Definisco algoritmo polinomiale per f:
1. Dato w, eseguo M e registro le computazioni accettanti
Oss. Spazio per ogni comp. è pol. quindi algoritmo oper in spazio pol.
2. hp=> Pspace=P => tempo è polinomiale => f in FP
Quali sono degli esempi di problemi #P?
SAT: dato pol. booleano contare quanti sono gli assegnamenti che lo soddisfano
Cosa implica se il problema #CYCLE appartiene a FP?
Facciamo vedere che HAM in P (visto che HAM è NP, se fosse P allora P=NP)
G grafo diretto con n vertici -> costruiamo G’ grafo diretto
G ha circuito hamiltoniano <=> G’ ha almeno n^n^2 cicli
Per ogni coppia id vertici costruisci m nuovi vertici
Oss. ogni ciclo semplice di G di lunghezza l corrisponde a (2^m)^l cicli di G’ (ogni arco ha 2^m cammini)
Sia m=nlogn
1) G ha circuito hamiltoniano => G’ ha almeno num di cicli G’>=(2^m)^n=n^n^2 cicli
2) G non ha circuito hamiltoniano => G’ ha al più n^n^2-1 cicli
hp) ciclo di G ha al massimo lunghezza n-1 totale di cicli è <= n^n-1
Per G’ -> #cicli <= n^{n-1} (2^n)^{n-1} <= n^n^2
Problema PRIME e COMP
PRIME: Dato n in N, determinare se N è primo
COMP: dato n in N, determinare se n è composto
algoritmo con sqrt n
se n composto allora esiste d: 2 <= d <= sqrt(n)
deterministico, corretto, esponenziale.
per tutti i numeri fino a sqrt n
complessitá Sigma(2^l/2)
algoritmo con piccolo teorema di fermat
p primo => a in Z, a^p = a mod p
p primo => a^{p-1} = 1mod p
non viceversa
Dato n in N
1. trovo coprimo sia a in N t.c. (a,n)=1
2. a^{n-1}=1 mod n, n primo altrimenti composto
non det, non corretto polinomiale (potenza modulo si calcola in O(logn^3)
algoritmo con teorema di pratt
se esiste a in N t.c.
- (a,n)=1
- a^{n-1}=1 mod n
- forall q t.c. n-1, q primo a^{n-1/q} !+ 1 mod n, allora n è primo
algoritmo non det, corretto, polinoiale
Cosa sono i numeri di Carmichael
n in N si dice numero di Carmichael quando n è composto e per ogni a in N, (a,n)=1 e a^{n-1}= 1 mod n (ovvero numeri per quali piccolo teorema di fermat non funziona all’inverso)
Perchè PRIME è P?
(1,n) =1
n primo <=> (x+a)^n = x^n+a mod n
fissato a in N, se (x+a)^n = x^n+a mod n allora n è primo
L’idea è di ridurre il numero di congruenza da controllare (dividento entrambi i membri per x^r -1 con r opportuno)
PRIME in P
