Metraipolis › archive › dc_99ec1a858828
BPP (Komplexitätsklasse) — Wikipedia (de)
- Source
- Wikipedia (de)
- Original
- https://de.wikipedia.org/wiki/BPP_(Komplexit%C3%A4tsklasse)
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-31T11:22:18.584Z
- SHA-256 of the archived text
bdae086cce5105756aea81cade5dd5894d0e364b43b670758da5c8fc149083d1- Stable URL of this page
https://metraipolis.com/documento/dc_99ec1a858828
How to cite
BPP (Komplexitätsklasse) — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/BPP_(Komplexit%C3%A4tsklasse) (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_99ec1a858828 (Metraipolis archive dc_99ec1a858828, sha256 bdae086cce5105756aea81cade5dd5894d0e364b43b670758da5c8fc149083d1)
BibTeX
@misc{dc99ec1a858828,
title = {BPP (Komplexitätsklasse) — Wikipedia (de)},
howpublished = {Wikipedia (de)},
url = {https://de.wikipedia.org/wiki/BPP_(Komplexit%C3%A4tsklasse)},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_99ec1a858828; sha256 bdae086cce5105756aea81cade5dd5894d0e364b43b670758da5c8fc149083d1},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (de), https://de.wikipedia.org/wiki/BPP_(Komplexit%C3%A4tsklasse). Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In der Komplexitätstheorie steht BPP (englische Abkürzung für bounded error probabilistic polynomial time) für eine Komplexitätsklasse von Entscheidungsproblemen. Ein Problem liegt in BPP, wenn es einen polynomiell zeitbeschränkten probabilistischen Algorithmus gibt, der das Problem löst und dessen Fehlerwahrscheinlichkeit höchstens 1/3 beträgt. Die Verwendung einer beliebigen anderen konstanten Fehlerschranke kleiner als 1/2 ändert nichts an der Definition der Klasse BPP, durch mehrmalige Anwendung eines gegebenen BPP-Algorithmus lässt sich jede beliebige Fehlerschranke erreichen. BPP-Algorithmen sind Monte-Carlo-Algorithmen, da sie mit einer geringen Wahrscheinlichkeit ein falsches Ergebnis liefern. Sie wurde 1977 mit anderen probabilistischen Komplexitätsklassen von John T. Gill eingeführt. Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico). Fonte: Wikipedia in tedesco, voce «BPP (Komplexitätsklasse)» — https://de.wikipedia.org/wiki/BPP_(Komplexit%C3%A4tsklasse) Wikidata Q796890: «classe di complessità» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q796890 Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/BPP_(Komplexit%C3%A4tsklasse)?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 262411104, consultata il 2026-10-31T11:10:35.134Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 43d3d7ceaa9e99a47f484210de17318e28e11d3a4cdff39d88488e23677b3e03