Gibt es beschreibende Komplexitätsdarstellungen von Quantenkomplexitätsklassen?

20

Der Titel sagt mehr oder weniger alles, aber ich denke, ich könnte ein bisschen Hintergrundwissen und einige spezifische Beispiele hinzufügen, an denen ich interessiert bin.

Deskriptive Komplexitätstheoretiker wie Immerman und Fagin haben viele der bekanntesten Komplexitätsklassen mithilfe von Logik charakterisiert. Zum Beispiel kann NP mit existenziellen Abfragen zweiter Ordnung charakterisiert werden; P kann mit Abfragen erster Ordnung mit einem hinzugefügten Operator für den kleinsten Fixpunkt charakterisiert werden.

Meine Frage ist: Gab es Versuche, besonders erfolgreiche, solche Darstellungen für Quantenkomplexitätsklassen wie BQP oder NQP zu entwickeln? Wenn nein, warum nicht?

Vielen Dank.

Update (Moderator) : Diese Frage wird von diesem Beitrag auf mathoverflow vollständig beantwortet .

Philip White
quelle
1
Siehe Kavehs
Alessandro Cosentino
1
Als Duplikat schließen?
Suresh Venkat
3
Für diejenigen, die sich fragen, warum diese Frage (wie ich) als Off-Topic geschlossen wurde: Ignorieren Sie den engen Grund, weil er bedeutungslos ist (solange es sich um diese Frage handelt). Das Schließen einer Frage erfordert einen der verschiedenen Gründe. "Genaues Duplikat" wäre der geeignete Grund, aber das System erlaubt es uns nicht, eine Frage als genaues Duplikat einer Frage in MathOverflow zu schließen. Ich vermute daher, dass Suresh zufällig einen der verfügbaren Gründe ausgewählt hat.
Tsuyoshi Ito
1
ps: Ich halte es für vernünftig, diese Fälle in einer ähnlichen Weise wie Cross-Postings zu betrachten und sie nicht zu schließen. Jemand (zB das OP) postet eine CW-Antwort basierend auf der Antwort auf MO (oder nur einem Link zu dieser Antwort).
Kaveh
2
Ich habe die Frage erneut geöffnet.
Ryan Williams

Antworten:

7

Ich denke, Robins Antwort auf meine Frage zu MO beantwortet auch diese Frage .

Eine deskriptive Komplexitätscharakterisierung einer Komplexitätsklasse ergibt eine Sprache, deren Abfragen (dh Formeln) genau die in C berechenbaren Funktionen sind . Die Syntax der Sprache ist normalerweise sehr einfach, dh wenn eine Zeichenfolge q angegeben wird , ist es einfach zu überprüfen, ob q eine wohlgeformte Abfrage der Sprache ist, zumindest wird erwartet, dass sie entscheidbar ist (aber normalerweise kann die Syntaxprüfung in a durchgeführt werden kleine Komplexitätsklasse). Dies würde eine effektive Aufzählung der Probleme in der Klasse C nach sich ziehen und eine syntaktische Charakterisierung für C liefern . (Wenn die Komplexität der Syntaxprüfung gering ist, kann dies auch bedeuten, dass ein vollständiges Problem für die Klasse vorliegt.)CCqqCC

In den Kommentaren oben, verbunden Robin zu Kord Eickmeyer und Martin Grohe Papier „ Randomisierung und Derandomization in Beschreibende Komplexitätstheorie “ , die eine „deskriptive Komplexität“ Charakterisierung gibt . Die Autoren selbst stellen in der Einleitung fest, dass sich dies von dem unterscheidet, was üblicherweise mit einer deskriptiven Komplexitätscharakterisierung gemeint ist:BPP

Wir beweisen, dass , die probabilistische Version der Festkommalogik mit Zählen, die Komplexitätsklasse B P P auch auf ungeordneten Strukturen erfasst . Für geordnete Strukturen ist dieses Ergebnis eine direkte Konsequenz des Immerman-Vardi-Theorems [7, 8], und für beliebige Strukturen folgt aus der Beobachtung, dass wir in BPIFP + C eine zufällige Reihenfolge mit hoher Wahrscheinlichkeit definieren können. Dennoch ist das Ergebnis auf den ersten Blick überraschend, weil es mit der offenen Frage, ob es eine logische Erfassung von P gibt , vergleichbar ist und weil angenommen wird, dass P = Die Einschränkung ist, dass die Logik B P istBPIFP+CBPPP .P=BPP hat keine effektive Syntax und ist daher keine „Logik“ gemäß Gurevichs [9] Definition, die der Frage nach einer Logik, die P erfasst, zugrunde liegt. BPIFP+CPWir glauben jedoch, dass eine völlig angemessene Beschreibung der Komplexitätsklasse B P P gibt , da die Definition von B P PBPIFP+CBPPBPP inhärent unwirksam ist (im Gegensatz zur Definition von in Bezug auf das Entscheidbare) Satz polynomisch getakteter Turingmaschinen).P

Ich bin kein Experte für finite Modelltheorie / deskriptive Komplexität (und würde gerne persönlich mehr von Experten hören), aber ich habe das Gefühl, dass es hier ein bisschen Betrug gibt, wenn ich sage, dass dies eine deskriptive Komplexitätscharakterisierung ist. Der Grund für mein Gefühl ist, dass wir, wenn wir eine nicht effektive Syntax haben dürfen, beliebige semantische Einschränkungen verwenden können, um die Klasse wohlgeformter Abfragen einzuschränken, und für jede Komplexitätsklasse eine "beschreibende Komplexitäts" -Charakterisierung geben können. Betrachten Sie beispielsweise (das P S p a c e erfasst ) und nehmen Sie dann genau die Abfragen an, die in B Q P berechenbar sindSO(TC)PSpaceBQP , oder die Sprache zu berücksichtigen , die für jede Maschine in einem Funktionssymbol hat BQPBQP

Kaveh
quelle
8

PσσσMφMφσR1,R2,) This is a paraphrase of Definition 1.14 of this paper by Gurevich, which is reference [9] in the quote Kaveh gave.

The paper about BPP and randomized logic presents a significantly different framework. It starts with a finite vocabulary σ, and then considers a probability space of all vocabularies that extend σ with some disjoint vocabulary ρ. So a formula is satisfiable in the new randomized logic if it is satisfiable in "enough" logics based on extensions of σ by different ρ. This is my butchering of Definition 1 in the Eickmeyer-Grohe paper linked to by Robin Kothari. In particular, the vocabulary is not finite (well, each vocabulary is, but we have to consider infinitely many distinct vocabularies), the set of sentences of this logic is undecidable, and the notion of satisfiability is different from the one put forth by Gurevich.

Aaron Sterling
quelle