PCP Flashcards
cos’è e come funzoina una MDT con oracolo?
è una macchina di touring che dispone di una stringa segreta detta oracolo. è possibile durante il procedimento consultare l’oracolo inserendo un numero in un nastro, detto nastro diquery. l’oracolo questo ritornerà il bit presente nella stringa segreta in corrispondenza della posizione inserita con la query
come possiamo usare le macchine di touring con oracolo per definire NP?
dicendo che un linguaggio L in 2* appartiene NP se e solo se esiste MDT con racolo tale che 1 V(x,w) -> tempo polinomiale |x|, esiste per ogni possibile input esiste un oracolo tale che V(x,w) = Si se x in L. considerano l’idea dell’albero l’oracolo ci dice che strada prendere
cosa sono i probabilistic checkers?
sono macchine di turing che hanno accesso diretto all’oracolo e che possono utilizzare una sorgene casuale di bit random. è possibile esprimerli come p[r,q] se utilizzano massimo r bit e q query all’oracolo.
quando un linguaggio è accettato da un oracolo?
un linguaggio è accettato da un oracolo quando il verificatore funziona tempo poly sulla lungehzza dell’input, effttua max q(|x|) query, chiede max r(|x|) random ed esite una stringa dell’oracolo w che per tuttti r ritorna l’appartenzena con P(1) se x è in L e per ogni w a prescindere da r la p. che ritorni appartenza a x è <= 1/2
cosa dice il teorema su PCP?
che per risolvere problemi NP è possibile utilizzare una quantita log n bit random per portare il numero di query da chiedere all’oracolo ad una costante
come viene utilizzato il teorema PCP nella pratica?
vengono fatte alcune assunzioni, per esempio vengono usatte essattamente r bit random, vengono svolte esattamente q query, e prima dell’esecuzioni vengono computate tutte le r stringhe random e fatte tuttte le q query. dato che è possibile che una query dipenda da quelle fatte precedentemente vengono fatte query per tutte le possibili combinazioni
