ZPP (complessità)

Nella teoria della complessità computazionale, ZPP (Zero-error Probabilistic Polynomial time, "tempo polinomiale probabilistico con errore zero") è la classe di complessità dei problemi per i quali esiste una macchina di Turing probabilistica con queste proprietà

• Restituisce sempre la risposta corretta SÌ o NO.
• Il tempo di esecuzione è polinomiale in termini di aspettativa per ogni input.

In altre parole, se l'algoritmo può lanciare una moneta veramente casuale mentre è in esecuzione, restituirà sempre la risposta corretta e, per un problema di dimensione n, c'è un qualche polinomio p(n) tale che il tempo medio di esecuzione sarà minore di p(n), anche se potrebbe essere occasionalmente molto più lungo. Tale algoritmo è chiamato algoritmo Las Vegas.

Alternativamente, ZPP può essere definita come la classe dei problemi per i quali esiste una macchina di Turing probabilistica con queste proprietà:

• Funziona sempre in tempo polinomiale.
• Restituisce una risposta SÌ, NO o NON SO.
• La risposta è sempre o NON SO o la risposta corretta.
• Restituisce NON SO con probabilità al massimo 1/2 (e la risposta corretta altrimenti).

Le due definizioni sono equivalenti.

La definizione di ZPP si basa sulle macchine di Turing probabilistiche, ma, per chiarezza, si noti che altre classi di complessità basate si di esse includono BPP ed RP. La classe BQP è basata su un'altra macchina dotata di casualità: il computer quantistico.

Definizione d'intersezione

La classe ZPP è esattamente all'intersezione delle classi RP e co-RP. Per tale ragione questa è spesso assunta come definizione di ZPP. Per dimostrare questo, si noti anzitutto che ogni problema che è sia RP sia co-RP ha un algoritmo Las Vegas nel modo seguente:

• Si supponga che abbiamo un linguaggio L riconosciuto sia dall'algoritmo A di RP sia dall'algoritmo B di co-RP (probabilmente completamente diverso)
• Dato un input in L, si esegua A sull'input. Se restituisce SÌ, la risposta deve essere SÌ. Altrimenti si esegua B sull'input. Se restituisce NO, la risposta deve essere NO. Se non si presenta nessuno dei due, si ripeta questo passo.

Si noti che soltanto una sola macchina può dare una risposta sbagliata e la probabilità che quella macchina dia la risposta sbagliata durante ogni ripetizione è al massimo del 50%. Questo significa che la probabilità di raggiungere il ko turno si contrae esponenzialmente in k, mostrando che il tempo di esecuzione atteso è polinomiale. Questo dimostra che RP intersecato co-RP è contenuto in ZPP.

Per dimostrare che ZPP è contenuto in RP intersecato co-RP, si supponga che abbiamo un algoritmo Las Vegas C per risolvere un problema. Possiamo allora costruire il seguente algoritmo RP:

• Si esegua C per almeno il doppio del suo tempo di esecuzione. Se dà una risposta, si prenda quella risposta. Se non dà nessuna risposta prima che lo fermiamo, si prenda NO.

Per la disuguaglianza di Markov, la probabilità che fornirà una risposta prima che lo fermiamo è 1/2. Questo significa che la probabilità che avremo la risposta sbagliata su un'istanza di SÌ, fermando l'algoritmo e dando NO, è solo 1/2, che si adatta alla definizione di un algoritmo RP. L'algoritmo co-RP è identico, tranne che dà SÌ se per C "il tempo scade".

Testimone e prova

Le classi NP, RP e ZPP si possono pensare in termini di prova di appartenenza a un insieme.

Definizione: Un verificatore V per un insieme X è una macchina di Turing tale che:

• se x è in X allora esiste una stringa w tale che V(x,w) accetta;
• se x è non in X, allora per tutte le stringhe w, V(x,w) rifiuta.

La stringa w può essere pensata come la prova di appartenenza. Nel caso di prove corte (di lunghezza limitata da un polinomio della dimensione dell'input) che possono essere verificate in modo efficiente (V è una macchina di Turing deterministica in tempo polinomiale), la stringa w è chiamata testimone.

Note:

• La definizione è molto asimmetrica. La prova che x è in X è una stringa singola. La prova che x non è in X è la collezione di tutte le stringhe, nessuna delle quali è una prova di appartenenza.
• La disponibilità del testimone è uniforme. Per tutti gli x in X ci deve essere un testimone. Non accade dove certi x in X sono troppo difficili da verificare, mentre la maggior parte nono lo sono.
• Non occorre che il testimone sia una prova costruita tradizionalmente. Se V è una macchina di Turing probabilistica che potrebbe forse accettare x se x è in X, allora la prova è la stringa di lanci di monete che porta la macchina, in base alla fortuna, all'intuizione o al genio, ad accettare x.
• Il co-concetto è una prova di non appartenenza, o di appartenenza all'insieme complemento.

Le classi NP, RP e ZPP sono insiemi che hanno testimoni per l'appartenenza. La classe NP richiede soltanto che esistano i testimoni. Essi possono essere molto rari. Delle 2^f(|x|) possibili stringhe, con f che è un polinomio, soltanto una deve far sì che il verificatore accetti (se x è in X. Se x non è in X, nessuna stringa farà sì che il verificatore accetti).

Per le classi RP e ZPP qualsiasi stringa scelta a caso sarà probabilmente un testimone.

Le co-classi corrispondenti hanno un testimone per la non appartenenza. In particolare, co-RP è la classe di insiemi per la quale, se x non è in X, è probabile che qualsiasi stringa scelta casualmente sia un testimone per la non appartenenza. ZPP è la classe di insiemi per la quale è probabile che qualsiasi stringa casuale sia un testimone di x in X, o di x non in X, qualunque possa essere il caso.

Connettere questa definizione con altre definizioni di RP, co-RP e ZPP è facile. La macchina di Turing probabilistica in tempo polinomiale V*_w(x) corrisponde alla macchina di Turing deterministica in tempo polinomiale V(x, w), sostituendo il nastro casuale di V* con un secondo nastro di input per V su cui è scritta la sequenza di lanci di monete. Selezionando il testimone come stringa casuale, il verificatore è una macchina di Turing probabilistica in tempo polinomiale la cui probabilità di accettare x quando x è in X è grande (diciamo maggiore di 1/2), ma zero se x ∉ X (per RP); di rifiutare x quando x non è in X è grande ma zero se x ∈ X (per co-RP); e di accettare o rifiutare correttamente x come membro di X è grande, ma zero di accettare o rifiutare scorrettamente x (per ZPP).

Mediante la selezione casuale ripetuta di un possibile testimone, la grande probabilità che una stringa casuale sia un testimone dà un algoritmo in tempo polinomiale stimato per accettare o respingere un input. Per converso, se la macchina Turing è attesa in tempo polinomiale (per qualsiasi x dato), allora una considerevole frazione delle esecuzioni deve essere limitata in tempo polinomiale, e la sequenza delle monete usata in tale esecuzione sarà un testimone.

ZPP dovrebbe essere messa a confronto con BPP. La classe BPP non richiede testimoni, sebbene i testimoni siano sufficienti (quindi BPP contiene RP, co-RP e ZPP). Un linguaggio BPP fa accettare V(x, w) su una maggioranza (chiara) di stringhe w se x è in X, e per converso lo fa respingere su una maggioranza (chiara) di stringhe w se x non è in X. Non occorre che una singola stringa w sia definitiva, e perciò in generale esse non possono essere considerate prove o testimoni.

Connessione con altri classi

Dal momento che ZPP = RP ∩ co-RP, ZPP ovviamente è contenuta sia in RP che in co-RP.

La classe P è contenuta in ZPP, e alcuni informatici hanno congetturato che P = ZPP, cioè, ogni algoritmo Las Vegas ha un equivalente deterministico in tempo polinomiale.

Una prova per ZPP = EXPTIME implicherebbe che P ≠ ZPP, in quanto P ≠ EXPTIME (vedi teorema della gerarchia temporale).

Collegamenti esterni

• (EN) Classe ZPP Archiviato il 3 dicembre 2018 in Internet Archive. su Complexity Zoo