Was ist Komplexitätsklasse

12

Was bedeutet die Komplexitätsklasse ? Ich weiß, dass die Komplexitätsklasse ist, die Sprachen enthält, für die es eine polynomielle zeitlich nicht deterministische Turing-Maschine so dass wenn die Anzahl der Akzeptanzzustände der Maschine am Eingang ungerade ist.PPPAMxAMx

Aber was bedeutet ? Ich kann einfach nicht folgen, was es tatsächlich tut :)PP

Was sind praktische Konsequenzen einer solchen Komplexitätsklasse und wie lässt sich zeigen, dass ?PP=P

Stewenson
quelle
2
Diese (imho umständliche) Notation kennzeichnet relative oder Orakelkomplexitätsklassen. Siehe Wikipedia für eine Definition. Beantwortet das die Frage? Wenn nicht, bitte bearbeiten, um zu klären.
Raphael
7
Sie finden den Beweis von unter cs.rutgers.edu/~allender/538/murata3.pdfPP=P
sdcvvc

Antworten:

11

bezeichnet die KlasseP, die mit einem sogenanntenOrakelfürP ausgestattet ist - wir sagen, es wurde die Möglichkeit gegeben, zu bestimmen, ob eine Zeichenfolge s Mitglied einer Sprache L ist, die in der KlasseP enthalten ist in einem Arbeitsgang.PPPPsLP

Ich sehe, dass ein anderer Kommentator (sdcwc) mit dem Beweis von verknüpft hat (siehe diese Anmerkungen zu einer Vorlesung aus CS 538 bei Rutgers ). Eine Komplexitätsklasse C , die ein Orakel für eine Klasse B ist, so dass B C = B ist , wird für die Klasse B als niedrig bezeichnet . In diesem Fall sagen wir, dass P für sich selbst niedrig ist.PP=PCBBC=BBP

Josh Lockhart
quelle
Ein weiterer Link für Sie, diesmal zur Wikipedia-Seite über 'Lowness' von Komplexitätsklassen: en.wikipedia.org/wiki/Low_%28complexity%29
Josh Lockhart
Ihr Erklärungsstil reicht zum Verständnis der Grundprinzipien aus und ist leicht zu befolgen.
Stewenson
Was meinst du damit, dass mit dem Orakel ausgestattet ist, das im Einzelschritt die Zugehörigkeit zur Sprache L bestimmen kann ? Wenn Sie aus meiner Sicht ein Problem in in P P lösen möchten, fragen Sie das Orakel zu Beginn der Berechnung ab, damit Sie nach dem ersten Schritt wissen, wie das Orakel Sie antwortet? Sie wissen also, dass, seit Sie einen Akzeptanzzustand erreicht haben, die Anzahl solcher Zustände nur einer ist, also die ungerade Anzahl, also akzeptieren Sie? PLPP
Stewenson
3
"ein Orakel für - wir sagen, es wurde die Möglichkeit gegeben, in einer einzigen Operation zu bestimmen, ob eine Sprache L ein Mitglied von P ist oder nicht ." - das ist falsch: Ein Orakel gibt die Möglichkeit zu bestimmen, ob ein String s Mitglied einer Sprache L in P ist . Ohne Verlust der Allgemeinheit kann L als S A T (da es P -komplett ist)PLPsLPLSATP
sdcvvc
Ich versuche den Beweis wirklich hart zu verfolgen, aber es ist mir ziemlich unklar. Was bedeutet zum Beispiel die Funktion ? Ich weiß, es ist "1 i-mal wiederholen ( 1 3 = 111 )", aber wofür ist es in diesem Zusammenhang gut? Was bedeutet speziell 1 ich meine? Und was ist mit dem k in n k überall? Wenn i n k , dann ist f ( 1 i , x ) = f ( 1 n k , x )f(1i,x)13=1111iknkink . Was bedeutet es? Warum haben Sie eine Funktion f & egr ; P mitsolchen Eingabe? f(1i,x)=f(1nk,x)=f(1|x|k,x)fP
Stewenson