Schneller Zugriff als Browser!
26 Beziehungen: Abelpreis, Abgeschlossenheit (algebraische Struktur), Avi Wigderson, BQP, E (Komplexitätsklasse), Englische Sprache, Entscheidbar, Erwartungswert, Fehlerschranke, John T. Gill, Komplexitätsklasse, Komplexitätstheorie, Monte-Carlo-Algorithmus, NP (Komplexitätsklasse), P (Komplexitätsklasse), Polynom, Polynomialzeithierarchie, Probabilistische Polynomialzeit, Probabilistische Turingmaschine, PSPACE, Quantencomputer, Randomisierter Algorithmus, RP (Komplexitätsklasse), Russell Impagliazzo, Zeitkomplexität, ZPP (Komplexitätsklasse).
Abelpreis
Der Abelpreis ist eine seit 2003 jährlich durch die Norwegische Akademie der Wissenschaften verliehene internationale Auszeichnung für wissenschaftliche Arbeiten von außergewöhnlicher Tiefe und Einfluss auf dem Gebiet der Mathematik.
Neu!!: BPP (Komplexitätsklasse) und Abelpreis · Mehr sehen »
Abgeschlossenheit (algebraische Struktur)
In der Mathematik, insbesondere der Algebra, versteht man unter Abgeschlossenheit einer Menge bezüglich einer Verknüpfung, dass die Verknüpfung beliebiger Elemente dieser Menge wieder ein Element der Menge ist.
Neu!!: BPP (Komplexitätsklasse) und Abgeschlossenheit (algebraische Struktur) · Mehr sehen »
Avi Wigderson
Avi Wigderson, London 2012 Avi Wigderson (* 9. September 1956) ist ein israelischer Mathematiker und Informatiker.
Neu!!: BPP (Komplexitätsklasse) und Avi Wigderson · Mehr sehen »
BQP
Die Lage von BQP relativ zu anderen ProblemklassenMichael Nielsen and Isaac Chuang (2000). ''Quantum Computation and Quantum Information''. Cambridge: Cambridge University Press. ISBN 0-521-63503-9. Die Komplexitätsklasse BQP (von) ist ein Begriff aus der Komplexitätstheorie, einem Teilgebiet der Theoretischen Informatik.
Neu!!: BPP (Komplexitätsklasse) und BQP · Mehr sehen »
E (Komplexitätsklasse)
Die Komplexitätsklasse \mathbf E ist die Klasse aller Sprachen, die sich von einer deterministischen Turingmaschine in exponentieller Zeit mit linearem Exponenten lösen lassen.
Neu!!: BPP (Komplexitätsklasse) und E (Komplexitätsklasse) · Mehr sehen »
Englische Sprache
Die englische Sprache (Eigenbezeichnung: IPA) ist eine ursprünglich in England beheimatete germanische Sprache, die zum westgermanischen Zweig gehört.
Neu!!: BPP (Komplexitätsklasse) und Englische Sprache · Mehr sehen »
Entscheidbar
In der theoretischen Informatik heißt eine Eigenschaft auf einer Menge entscheidbar (auch rekursiv, rekursiv ableitbar), wenn es ein Entscheidungsverfahren für sie gibt.
Neu!!: BPP (Komplexitätsklasse) und Entscheidbar · Mehr sehen »
Erwartungswert
Der Erwartungswert (selten und doppeldeutig Mittelwert) ist ein Grundbegriff der Stochastik.
Neu!!: BPP (Komplexitätsklasse) und Erwartungswert · Mehr sehen »
Fehlerschranke
Fehlerschranken, auch Fehlergrenzen genannt, finden in der Fehlerrechnung, in der Messtechnik sowie in der Numerik Verwendung.
Neu!!: BPP (Komplexitätsklasse) und Fehlerschranke · Mehr sehen »
John T. Gill
John T. Gill (John Thomas Gill, III) ist ein US-amerikanischer Informatiker und Hochschullehrer an der Stanford University.
Neu!!: BPP (Komplexitätsklasse) und John T. Gill · Mehr sehen »
Komplexitätsklasse
Komplexitätsklassen In der Komplexitätstheorie werden Probleme oder Algorithmen darauf untersucht, wie aufwendig sie zu berechnen sind bezüglich einer bestimmten Ressource, meist bezüglich des Zeitaufwands oder des (Speicher-)Platzaufwands.
Neu!!: BPP (Komplexitätsklasse) und Komplexitätsklasse · Mehr sehen »
Komplexitätstheorie
Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität algorithmisch behandelbarer Probleme auf verschiedenen formalen Rechnermodellen.
Neu!!: BPP (Komplexitätsklasse) und Komplexitätstheorie · Mehr sehen »
Monte-Carlo-Algorithmus
Monte-Carlo-Algorithmen sind randomisierte Algorithmen, die mit einer nichttrivial nach oben beschränkten Wahrscheinlichkeit ein falsches Ergebnis liefern.
Neu!!: BPP (Komplexitätsklasse) und Monte-Carlo-Algorithmus · Mehr sehen »
NP (Komplexitätsklasse)
In der Informatik bezeichnet NP (für nichtdeterministisch polynomielle Zeit) eine fundamentale Komplexitätsklasse aus dem Bereich der Komplexitätstheorie.
Neu!!: BPP (Komplexitätsklasse) und NP (Komplexitätsklasse) · Mehr sehen »
P (Komplexitätsklasse)
In der Komplexitätstheorie ist P (auch: PTIME) diejenige Komplexitätsklasse, die alle Entscheidungsprobleme enthält, die in Polynomialzeit für deterministische Turingmaschinen lösbar sind.
Neu!!: BPP (Komplexitätsklasse) und P (Komplexitätsklasse) · Mehr sehen »
Polynom
Ein Polynom ist ein algebraischer Term, der sich als Summe von Vielfachen von Potenzen einer Variablen bzw.
Neu!!: BPP (Komplexitätsklasse) und Polynom · Mehr sehen »
Polynomialzeithierarchie
Die Polynomialzeithierarchie (PH, auch: polynomielle Hierarchie) ist die vermutete Struktur von Komplexitätsklassen zwischen NP und PSPACE.
Neu!!: BPP (Komplexitätsklasse) und Polynomialzeithierarchie · Mehr sehen »
Probabilistische Polynomialzeit
In der Komplexitätstheorie ist PP die Klasse der Entscheidungen, die in von einer probabilistischen Turingmaschine in Polynomialzeit lösbar ist und die Antwort in mindestens der Hälfte der Fälle richtig ist.
Neu!!: BPP (Komplexitätsklasse) und Probabilistische Polynomialzeit · Mehr sehen »
Probabilistische Turingmaschine
Eine probabilistische Turingmaschine, abgekürzt PTM, ist ein Konzept aus der theoretischen Informatik.
Neu!!: BPP (Komplexitätsklasse) und Probabilistische Turingmaschine · Mehr sehen »
PSPACE
In der Komplexitätstheorie bezeichnet PSPACE die Klasse der Entscheidungsprobleme, die von deterministischen Turingmaschinen mit polynomiellem Platz entschieden werden können.
Neu!!: BPP (Komplexitätsklasse) und PSPACE · Mehr sehen »
Quantencomputer
Ein Quantenprozessor bzw.
Neu!!: BPP (Komplexitätsklasse) und Quantencomputer · Mehr sehen »
Randomisierter Algorithmus
Ein randomisierter Algorithmus (auch stochastischer oder probabilistischer Algorithmus) ist ein Algorithmus, der versucht, durch die Wahl von zufälligen Zwischenergebnissen zu einem (im Mittel) guten bzw.
Neu!!: BPP (Komplexitätsklasse) und Randomisierter Algorithmus · Mehr sehen »
RP (Komplexitätsklasse)
RP im Verhältnis zu anderen probabilistischen Komplexitätsklassen RP (manchmal auch nur mit R bezeichnet) bezeichnet die Klasse der Entscheidungsprobleme, für die es einen randomisierten Algorithmus mit polynomieller Laufzeit gibt, der jede nicht zu akzeptierende Eingabe mit Wahrscheinlichkeit 1 ablehnt und für jede zu akzeptierende Eingabe eine Fehlerwahrscheinlichkeit von höchstens 1/2 hat.
Neu!!: BPP (Komplexitätsklasse) und RP (Komplexitätsklasse) · Mehr sehen »
Russell Impagliazzo
Russell Impagliazzo Russell Graham Impagliazzo (* 29. Mai 1963 in Providence, Rhode Island) ist ein US-amerikanischer Informatiker, der sich mit Komplexitätstheorie, Pseudozufall und Kryptographie befasst.
Neu!!: BPP (Komplexitätsklasse) und Russell Impagliazzo · Mehr sehen »
Zeitkomplexität
Unter der Zeitkomplexität eines Problems wird in der Informatik die Anzahl der Rechenschritte verstanden, die ein optimaler Algorithmus zur Lösung dieses Problems benötigt, in Abhängigkeit von der Länge der Eingabe.
Neu!!: BPP (Komplexitätsklasse) und Zeitkomplexität · Mehr sehen »
ZPP (Komplexitätsklasse)
Die Komplexitätsklasse ZPP beinhaltet alle Probleme, für die es eine nichtdeterministische Turingmaschine gibt, die an jeder Stelle mit gleicher Wahrscheinlichkeit unter den möglichen Alternativen auswählt und folgende Eigenschaften besitzt.
Neu!!: BPP (Komplexitätsklasse) und ZPP (Komplexitätsklasse) · Mehr sehen »
