Metraipolis › archive › dc_0e63fe668367
ZPP (complessità) — Wikipedia
- Source
- Wikipedia (it)
- Original
- https://it.wikipedia.org/wiki/ZPP_(complessit%C3%A0)
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-11-10T17:07:28.802Z
- SHA-256 of the archived text
9829b0392f3f4effecbbf4afa7a2833e301b8c225e8be38c8a163e0385d7aab0- Stable URL of this page
https://metraipolis.com/documento/dc_0e63fe668367
How to cite
ZPP (complessità) — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/ZPP_(complessit%C3%A0) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_0e63fe668367 (Metraipolis archive dc_0e63fe668367, sha256 9829b0392f3f4effecbbf4afa7a2833e301b8c225e8be38c8a163e0385d7aab0)
BibTeX
@misc{dc0e63fe668367,
title = {ZPP (complessità) — Wikipedia},
howpublished = {Wikipedia (it)},
url = {https://it.wikipedia.org/wiki/ZPP_(complessit%C3%A0)},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_0e63fe668367; sha256 9829b0392f3f4effecbbf4afa7a2833e301b8c225e8be38c8a163e0385d7aab0},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/ZPP_(complessit%C3%A0). Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in italiano, in ordine alfabetico). Fonte: Wikipedia in italiano, voce «ZPP (complessità)» — https://it.wikipedia.org/wiki/ZPP_(complessit%C3%A0) Wikidata Q136355: «classe di complessità» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q136355 Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/ZPP_(complessit%C3%A0)?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 138076566, consultata il 2026-11-10T17:04:39.994Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: b4e1740da899eab79231b0251087a11228eced84c5269aed80e9544a36ade7db