Semantische vs. Syntaktische Komplexitätsklassen

In seinem Buch "Computational Complexity" schreibt Papadimitriou:

RP ist in gewisser Hinsicht eine neue und ungewöhnliche Art von Komplexitätsklasse. Nicht jede polynomial begrenzte nichtdeterministische Turingmaschine kann die Grundlage für die Definition einer Sprache in RP sein. Damit eine Maschine N eine Sprache in RP definiert , muss sie die bemerkenswerte Eigenschaft haben, dass sie bei allen Eingaben entweder einstimmig ablehnt oder mit Mehrheit akzeptiert . Die meisten nicht deterministischen Maschinen verhalten sich zumindest für einige Eingaben anders ... Es ist nicht einfach festzustellen, ob eine Maschine immer mit einer zertifizierten Ausgabe anhält. Wir bezeichnen solche Klassen informell als semantische Klassen im Gegensatz zu syntaktischen Klassen wie P und NP, wo wir durch eine oberflächliche Überprüfung sofort erkennen können, ob eine entsprechend standardisierte Maschine tatsächlich eine Sprache in der Klasse definiert.

Einige Seiten später weist er darauf hin, dass:

Die Sprache L gehört zur Klasse PP, wenn es eine nicht deterministisch polynomisch begrenzte Turing-Maschine N gibt, so dass für alle Eingaben x $x \in L$ wenn mehr als die Hälfte der Berechnungen von N bei Eingabe x akzeptiert werden. Wir sagen, dass N mit Mehrheit über L entscheidet .

Frage 1: Warum kommt Papadimitriou zu dem Schluss, dass PP eine syntaktische Klasse ist, während sich ihre Definition nur geringfügig von der von RP unterscheidet ?

Frage 2: Ob "semantisch" für eine Komplexitätsklasse bedeutet, KEINE vollständigen Probleme zu haben, oder ob das Fehlen vollständiger Probleme als eine Eigenschaft angesehen wird, die wir für semantische Klassen erachten?

Bearbeiten: Siehe verwandtes Thema Haben alle Komplexitätsklassen eine Blattsprachcharakterisierung?

RP beinhaltet ein Versprechen, dass entweder 0 Pfade akzeptieren oder mehr als die Hälfte akzeptieren, unabhängig davon, um welche Eingabe es sich handelt. Für PP gibt es kein solches Versprechen. Wenn mehr als die Hälfte der Pfade akzeptieren, dann , ansonsten x ∉ L . (PP kann so definiert werden , dass die Akzeptanzkriterien sind ≥ 1 / 2 und < 1 / 2 ist.)$x \in L$$x \notin L$$\geq 1/2$$< 1/2$

Mit anderen Worten, wenn ich Ihnen ein probabilistisches TM sage, dass es sich um eine PP-Maschine handelt, die eine Sprache entscheidet, können Sie sicher sein, dass sie eine Sprache entscheidet . Die Sprache, für die es sich entscheidet, ist eindeutig die folgende: Versuchen Sie, einzugeben . Prüfen Sie, ob mehr als die Hälfte der Pfade akzeptiert werden (oder mehr als die Hälfte der zufälligen Zeichenfolgen, die das Akzeptieren verursachen). Wenn ja, x ∈ L . Wenn nicht, x ∉ L . Also haben wir mit diesem TM eine Sprache definiert.$x$$x \in L$$x \notin L$

Auf der anderen Seite, wenn ich Ihnen ein probabilistisches TM gebe, das behauptet, es sei eine RP-Maschine, die eine Sprache entscheidet, können Sie nicht einmal sicher sein, dass sie eine Sprache entscheidet. Das Problem ist, dass Sie, wenn Sie nur einige akzeptierende Pfade beobachten, nicht wissen, ob in L ist oder nicht. Also, wenn ich dir eine RP-Maschine gebe, musst du nur mein Wort dafür nehmen. Die Überprüfung, ob dieser Computer eine Sprache definiert, ist in der Tat nicht ausführbar.$x$$L$

Was Ihre zweite Frage betrifft, gibt es für syntaktische Klassen normalerweise ein offensichtliches vollständiges Problem, das wie folgt lautet: "Entscheide bei gegebener Maschine M, ob sie in der Zeit T bei Eingabe x akzeptiert." Wenn Sie eine nicht deterministische Maschine haben, ist dieses Problem NP-vollständig, wenn es eine PP-Maschine ist, dann ist es PP-vollständig usw. Das offensichtliche vollständige Problem für semantische Klassen ist, wie ich bereits erwähnte, nicht zu entscheiden. Somit erhalten wir für semantische Klassen kein vollständiges Problem kostenlos. Aber eine semantische Klasse kann ein vollständiges Problem haben. Wenn beispielsweise P = BPP ist (wie allgemein angenommen wird), weist BPP eine syntaktische Charakterisierung auf.

EDIT : Da es einige Diskussionen darüber gibt, wie man semantische und syntaktische Klassen definiert, möchte ich darauf hinweisen, dass Papadimitriou in seinem Buch eine Definition gibt, wenn es um Blattsprachen geht. (Siehe meine Frage zu Blattsprachen für einige Referenzen.)

Er sagt, dass syntaktische Klassen diejenigen sind, für die es eine Sprache gibt, die die Klasse unter Verwendung der Blattsprachentechnik definiert. Semantische Klassen sind solche, für die alle derartigen Charakterisierungen Versprechungsprobleme erfordern. Dies ist eine strenge Definition, die jedoch nur für Sprachen mit Blattsprachcharakterisierungen gilt.

$PP$$RP$ $PP$$> 1/2$$x$

$P$$NP$$PP$$RP$$RP$$> 1/2$$RP$$Promise-RP$

$P=BPP$$P=BPP$

Wenn es wirklich keine leicht zu berechnende Liste von Maschinen (jeder vernünftigen Art) gibt, die genau Ihre Klasse akzeptieren, dann denke ich, dass Ihre Klasse möglicherweise keine vollständige Sprache haben kann. Aber das scheint sehr schwer zu formalisieren, geschweige denn zu beweisen.