Zertifikat (Komplexität) - Certificate (complexity)

In der Berechnungskomplexitätstheorie ist ein Zertifikat (auch als Zeuge bezeichnet ) eine Zeichenfolge, die die Antwort auf eine Berechnung oder die Zugehörigkeit zu einer Zeichenfolge in einer Sprache zertifiziert. Ein Zertifikat wird oft als Lösungsweg innerhalb eines Verifikationsprozesses gedacht, mit dem überprüft wird, ob ein Problem mit „Ja“ oder „Nein“ beantwortet wird.

Im Entscheidungsbaummodell der Berechnung ist die Zertifikatskomplexität die minimale Anzahl der Eingangsvariablen eines Entscheidungsbaums , denen ein Wert zugewiesen werden muss, um den Wert der Booleschen Funktion definitiv festzulegen .

In Definitionen verwenden

Der Begriff des Zertifikats wird verwendet, um die Semientscheidbarkeit zu definieren : L ist semientscheidbar, wenn es ein zweistelliges Prädikat R ⊆ Σ∗ × Σ∗ gibt, so dass R berechenbar ist und für alle x ∈ Σ∗ gilt: 

   x ∈ L ⇔ there exists y such that R(x, y)

Zertifikate geben auch Definitionen für einige Komplexitätsklassen, die alternativ durch nichtdeterministische Turingmaschinen charakterisiert werden können . Eine Sprache L in ist NP , wenn und nur wenn es ein Polynom existiert p und eine Polynom-Zeit begrenzt Turing Maschine M , so dass jedes Wort x ist in der Sprache L genau , wenn ein Zertifikat vorhanden sind c der Länge höchstens p (| x | ) so dass M das Paar ( x , c ) akzeptiert . Die Klasse co-NP hat eine ähnliche Definition, außer dass es Zertifikate für die Wörter gibt, die nicht in der Sprache vorkommen.

Die Klasse NL hat eine Zertifikatsdefinition: Ein Problem in der Sprache hat ein Zertifikat polynomialer Länge, das durch eine deterministische, logarithmisch-raumbeschränkte Turingmaschine verifiziert werden kann, die jedes Bit des Zertifikats nur einmal lesen kann. Alternativ kann die deterministische Turing-Maschine im logarithmischen Raum in der obigen Aussage durch eine probabilistische Turing-Maschine mit begrenztem Fehler ersetzt werden, die nur eine konstante Anzahl von Zufallsbits verwenden darf.

Beispiele

Das Problem, für einen gegebenen Graphen G und die Zahl k zu bestimmen, ob der Graph eine unabhängige Menge der Größe k enthält, liegt in NP . Gegeben ein Paar ( G , k ) in der Sprache ist ein Zertifikat eine Menge von k Knoten, die paarweise nicht benachbart sind (und daher eine unabhängige Menge der Größe k sind ).

Ein allgemeineres Beispiel für das Problem der Bestimmung, ob eine gegebene Turingmaschine eine Eingabe in einer bestimmten Anzahl von Schritten akzeptiert, lautet wie folgt: 

 L = {<<M>, x, w> | does <M> accept x in |w| steps?}
 Show L ∈ NP.
 verifier:
   gets string c = <M>, x, w such that |c| <= P(|w|)
   check if c is an accepting computation of M on x with at most |w| steps
   |c| <= O(|w|3)
   if we have a computation of a TM with k steps the total size of the computation string is k2
   Thus, <<M>, x, w> ∈ L ⇔ there exists c <= a|w|3 such that <<M>, x, w, c> ∈ V ∈ P

Siehe auch

Verweise

Externe Links