Probabilistische Turing -Maschine

Im Theoretische Informatik, a Probabilistische Turing -Maschine ist ein Nichtdeterministische Turing-Maschine das wählt zwischen den verfügbaren Übergängen an jedem Punkt nach einigen Wahrscheinlichkeitsverteilung. Infolgedessen kann eine probabilistische Turing -Maschine - im Gegensatz zu einer deterministischen Turing -Maschine - - stochastisch Ergebnisse; Das heißt, auf einer bestimmten Eingabe- und Anweisungsstatusmaschine kann es unterschiedliche Laufzeiten haben oder es kann überhaupt nicht anhalten. Darüber hinaus kann es eine Eingabe in einer Ausführung akzeptieren und dieselbe Eingabe in einer anderen Ausführung ablehnen.

Bei gleichen Wahrscheinlichkeiten für die Übergänge können probabilistische Turing -Maschinen als deterministisch definiert werden Turing -Maschinen eine zusätzliche "Schreibanweisung" haben, bei der der Wert des Schreibens ist gleichmäßig verteilt Im Alphabet der Turing Machine (im Allgemeinen eine gleiche Wahrscheinlichkeit, ein "1" oder eine "0" auf das Band zu schreiben). Eine weitere häufige Neuformulierung ist einfach a deterministische Turing -Maschine mit einem zusätzlichen Band voller zufälliger Bits, das "Zufallsband" bezeichnet wird.

A Quantencomputer ist ein weiteres Berechnungsmodell, das von Natur aus wahrscheinlich wahrscheinlich ist.

Beschreibung

Eine probabilistische Turing -Maschine ist eine Art von Art von Nichtdeterministische Turing -Maschine In dem jeder nicht deterministische Schritt ein "Münzflip" ist, dh bei jedem Schritt gibt es zwei mögliche nächste Bewegungen und die Turing-Maschine wählt probabilistisch aus, welche Bewegungen zu übernehmen sind.[1]

Formale Definition

Eine probabilistische Turing-Maschine kann formell als 7-Tupel definiert werden , wo

  • ist eine endliche Reihe von Staaten
  • ist das Eingangsalphabet
  • ist ein Bandalphabet, das das leere Symbol enthält #
  • ist der Anfangszustand
  • ist der Satz von Akzeptieren (endgültige) Zustände
  • ist die erste probabilistische Übergangsfunktion. ist eine Bewegung eine Zelle links am Turing Machine Band und ist eine Bewegung eine Zelle rechts.
  • ist die zweite probabilistische Übergangsfunktion.

Bei jedem Schritt wendet die Turing Machine probabilistisch entweder die Übergangsfunktion an oder die Übergangsfunktion .[2] Diese Wahl wird unabhängig von allen früheren Entscheidungen getroffen. Auf diese Weise ähnelt der Prozess der Auswahl einer Übergangsfunktion in jedem Schritt der Berechnung einem Münzflip.

Die probabilistische Auswahl der Übergangsfunktion bei jedem Schritt führt einen Fehler in die Turing -Maschine ein. Das heißt, Zeichenfolgen, die die Turing -Maschine akzeptieren soll, dürfen bei einigen Gelegenheiten abgelehnt werden, und Zeichenfolgen, die die Turing -Maschine ablehnen soll, kann bei einigen Gelegenheiten akzeptiert werden. Um dies zu berücksichtigen, eine Sprache soll anerkannt werden mit Fehlerwahrscheinlichkeit durch eine probabilistische Turing -Maschine wenn:

  1. ein Faden in impliziert, dass
  2. ein Faden nicht in impliziert, dass

Komplexitätsklassen

Ungelöstes Problem in der Informatik:

Ist P = BPP?

Infolge des Fehlers, der durch die Verwendung von probabilistischen Münzentwurf eingeführt wird, kann der Begriff der Akzeptanz einer Schnur durch eine probabilistische Turing -Maschine auf unterschiedliche Weise definiert werden. Ein solcher Begriff, der mehrere wichtige Komplexitätsklassen enthält, ist die Ermöglichung einer Fehlerwahrscheinlichkeit von 1/3. Zum Beispiel die Komplexitätsklasse BPP ist definiert als die Klasse von Sprachen, die von einer probabilistischen Turing -Maschine in erkannt werden Polynomzeit mit einer Fehlerwahrscheinlichkeit von 1/3. Eine andere Klasse, die mit diesem Begriff der Akzeptanz definiert ist, ist Bpl, was das gleiche ist wie BPP Aber die zusätzliche Einschränkung, dass Sprachen lösbar sein müssen logarithmisch Platz.

Komplexitätsklassen Einzuziehen aus anderen Definitionen der Akzeptanz umfassen RP, Co-RP, und Zpp. Wenn die Maschine auf logarithmische Raum anstelle von Polynomzeit beschränkt ist, ist der Analog Rl, Co-RL, und Zpl Komplexitätsklassen werden erhalten. Durch Durchsetzung beider Beschränkungen, RLP, Co-RLP, BPLP, und Zplp werden nachgegeben.

Die probabilistische Berechnung ist auch für die Definition der meisten Klassen von entscheidend Interaktive Proof -Systeme, in dem die Verifiermaschine von der Zufälligkeit abhängt, um zu vermeiden, dass die Allmächtige Prover-Maschine vorhergesagt und ausgetrickst wird. Zum Beispiel die Klasse IP gleich PSPACEaber wenn Zufälligkeit aus dem Verifizierer entfernt wird, bleiben wir nur mit Np, was nicht bekannt ist, aber allgemein als erheblich kleinere Klasse angesehen wird.

Eine der zentralen Fragen der Komplexitätstheorie ist, ob Zufälligkeit Macht ergibt; das heißt, gibt es ein Problem, das in der Polynomzeit durch eine probabilistische Turing -Maschine gelöst werden kann, aber keine deterministische Turing -Maschine? Oder können deterministische Turing -Maschinen alle probabilistischen Turing -Maschinen effizient simulieren, wobei höchstens eine polynomiale Verlangsamung ist? Es ist bekannt, dass PBPPDa eine deterministische Turing -Maschine nur ein Sonderfall einer probabilistischen Turing -Maschine ist. Es ist jedoch ungewiss, ob (aber weithin vermutet wurde) BPPP, implizieren das BPP = P. Die gleiche Frage zum Protokollraum anstelle der Polynomzeit (tut L = BPLP?) Ist noch häufiger als wahr angesehen. Andererseits ergibt die Stromver- und die Zufälligkeit interaktiver Proofsysteme sowie die einfachen Algorithmen, die sie für schwierige Probleme wie Polynom-Zeit-Primalitätstests und Log-Space-Graphen mit Verbundenheitstests erzeugt, deutet darauf hin, dass Zufälligkeit Leistung hinzufügen kann.

Siehe auch

Anmerkungen

  1. ^ Sipser, Michael (2006). Introduction to the Theory of Computation (2. Aufl.). USA: Thomson -Kurs -Technologie. p. 368. ISBN 978-0-534-95097-2.
  2. ^ Arora, Sanjeev; Barak, Boaz (2016). Rechenkomplexität: ein moderner Ansatz. Cambridge University Press. p. 125. ISBN 978-0-521-42426-4.

Verweise

Externe Links