Probleme in AM oder in MA

Welche Beispiele für Probleme sind in (bzw. ) bekannt, die weder in noch in ? $\mathsf{AM}$ $\mathsf{MA}$ $\mathsf{NP}$ $\mathsf{BPP}$

Für kenne ich die folgenden zwei Beispiele: $\mathsf{AM}$

Nicht-Isomorphismus des Graphen : Sind zwei gegebene Graphen und bis zur Permutation der Eckpunkte der gleiche Graph? $G$ $H$
Protokoll der unteren Grenze: Sie erhalten eine Menge , sodass Sie wissen, dass entwederoderfür einige und so, dass ( wenn , wird geprüft, ob in gelöst werden kann ) und Sie müssen entscheiden, ob. $S\subset\{0,1\}^m$ $|S|\le\alpha|U|$ $|S|\ge 4\alpha|U|$ $0\le\alpha\le 1$ $S\in\mathsf{AM}$ $y\in U$ $y\in S$ $\mathsf{AM}$ $|S\ge 4\alpha|U|$

Für kenne ich kein Beispiel. $\mathsf{MA}$

Meine verfeinerte Frage: Kennen wir andere Probleme in oder , von denen nicht bekannt ist, dass sie in ? $\mathsf{AM}$ $\mathsf{MA}$ $\mathsf{NP}\cup\mathsf{BPP}$

Ich bin nicht an Problemen interessiert, für die der einzige Beweis, dass sie zu gehören, die Verwendung eines dieser beiden Protokolle ist. $\mathsf{AM}$

Bearbeiten: Meine Hauptmotivation ist es, Beispiele für oder -Algorithmen geben zu können, um zu erklären, was diese Klassen sind. $\mathsf{AM}$ $\mathsf{MA}$

cc.complexity-theory complexity-classes Bruno
quelle

Dies wird wahrscheinlich nicht zu Ihrer Motivation beitragen (und deshalb füge ich es nicht als Antwort hinzu), aber das quantenstoquastische Sat-Problem ist MA-vollständig. Das heißt: Hat ein stoquastischer Hamiltonianer mit lokalen Begriffen einen frustrationsfreien Grundzustand ? Frustrationsfrei bedeutet, dass sich alle Begriffe in ihrem niedrigsten Energiezustand befinden. lokal bedeutet, dass jeder Term des Hamilton-Operators nur Qubits enthält ; stoquastisch bedeutet, dass alle nicht diagonalen Einträge der Hamilton-Matrix nicht positiv sind. Siehe dieses Papier .

k

$k$

k

$k$ $k$

k

$k$

Peter Shor

Danke Peter! Ich denke , dass dies eine perfekt gültige Antwort ist , auch wenn es vielleicht nicht das beste Beispiel ist als Hilfe für Intuition zu geben ... Aber ich war nicht bewusst jedes Problem in (das ist in nicht bekannt ist )!

M A

$\mathsf{MA}$

N P

$\mathsf{NP}$

Bruno

Es ist schwer, natürliche Probleme in MA zu finden. Hier ist ein Blogeintrag von Lance Fortnow aus dem Jahr 2002, in dem er sagt, dass keine natürlichen Probleme in MA bekannt sind, die nicht in NP BPP enthalten sind. Und das war auch 2006 noch der Fall, als Bravyi et al. zeigten, dass stoquastisches Sat darin war. (Und falls Sie sich gefragt haben, es ist in der Tat ein natürliches Problem für die Quantenberechnung.) Ich glaube nicht, dass sich in den letzten acht Jahren etwas geändert hat, aber ich könnte leicht Dinge übersehen haben.

\cup

$\cup$

k

$k$

Peter Shor

Würden Sie Antworten akzeptieren, die sich in oder befinden und von denen nicht bekannt ist, dass sie sich in ? Ich habe das Gefühl, dass solche Probleme oft gute Beispiele für - oder -Stil haben. Es ist nur so, dass sie nur dann funktionieren, wenn das Versprechen gilt ... (Aber wenn dies für a ist formeller Kurs Dies ist möglicherweise kein gutes Beispiel, da Versprechen oft dazu dienen, Anfänger zu verwirren ...)

P r o m i s e M A

$\mathsf{PromiseMA}$

P r o m i s e A M

$\mathsf{PromiseAM}$

P r o m i s e N P \cup P r o m i s e B P P

$\mathsf{PromiseNP} \cup \mathsf{PromiseBPP}$

M A

$\mathsf{MA}$

A M

$\mathsf{AM}$

Joshua Grochow

@ Joshua: Wenn Sie irgendwelche natürlichen Probleme in PromiseMA haben, würde ich sie wirklich gerne sehen. Ich denke, das OP würde auch, da sein Problem mit der unteren Grenze des Protokolls für AM tatsächlich ein vielversprechendes Problem ist. Ich sollte wahrscheinlich auch beachten, dass das stochastische Sat-Problem auch ein Versprechungsproblem ist (wir versprechen, dass entweder ein frustrationsfreier Grundzustand vorliegt oder dass der Grundzustand eine 1 / poly ( ) höhere Energie aufweist als ein frustrationsfreier Grundzustand hätte).

k

$k$

n

$n$

Peter Shor

[Ich poste dies als Antwort, obwohl ich in bin, weil a) es einen anderen Algorithmus im Stil aufweist und b) @PeterShor gefragt hat und es zu lang für einen Kommentar war .] $\mathsf{PromiseMA}$ $\mathsf{MA}$

Über jedem endlichen Feld liegt das folgende Problem in : $\mathbb{F}$ $\mathsf{PromiseMA}$

Eingabe : Eine Menge von Polynomen $\mathbb{F}$ $F_1(\vec{x}), \dotsc, F_m(\vec{x})$

Entscheide : Gibt es keine Lösung für über den algebraischen Abschluss $F_1(\vec{x}) = \dotsb = F_m(\vec{x}) = 0$ $\overline{\mathbb{F}}$

Versprechen : Entweder gibt es eine Lösung über , oder es ist eine poly-Größe -algebraic Schaltung , so dass und (identisch mit Polynomen) $\overline{\mathbb{F}}$ $\mathbb{F}$ $C(\vec{x}, y_1, \dotsc, y_m)$ $C(\vec{x}, \vec{0}) = 0$ $C(\vec{x}, \vec{F}(\vec{x})) = 1$

Der -Stil-Algorithmus errät die Schaltung und überprüft dann die beiden Bedingungen unter Verwendung eines Polynomidentitätstests, der von Schwarz-Zippell-DeMillo-Lipton in wird. $\mathsf{MA}$ $C$ $\mathsf{coRP}$

$C$ $\mathsf{NP} \not\subseteq \mathsf{coMA}$

(Dies ist die Grundlage eines algebraischen Beweissystems aus der jüngsten gemeinsamen Arbeit mit Toniann Pitassi , aber für die Zwecke dieser Antwort gehen ähnliche Ideen auf ein früheres Papier von Pitassi sowie auf ihren ICM-Vortrag von 1998 und auf den sogenannten Nullstellensatz zurück und Polynomrechnung Berechnungssysteme .)

Joshua Grochow
quelle

Ich finde es faszinierend, dass dieses Ergebnis (im Geiste) einem Ergebnis von Koiran sehr nahe kommt, das zeigt, dass die Entscheidung, ob ein Bündel ganzzahliger Polynome eine gemeinsame Wurzel in hat, in , allerdings mit einem scheinbar nicht verwandten Beweis . (Koirans Ergebnis basiert auf dem von Goldwasser-Sipser festgelegten Protokoll für die untere Grenze.) Während ich versuchte, ein Beispiel für ein Problem in , spielte ich mit ähnlichen Problemen: Grundsätzlich wollte ich irgendwann das DLSZ-Lemma verwenden.

C

$\mathbb C$

A M

$\mathsf{AM}$

M A

$\mathsf{MA}$

Bruno

@ Bruno: Ich fand das gleiche faszinierend :). Tatsächlich erhalten wir auch ein ähnliches Ergebnis wie oben über Felder mit dem Merkmal Null, jedoch mit anstelle von , und der Beweis verwendet Koirans Ergebnis in Black-Box-Weise als Unterprogramm (siehe Satz 2.4 im gemeinsamen Papier mit Pitassi).

P r o m i s e A M

$\mathsf{PromiseAM}$

P r o m i s e M A

$\mathsf{PromiseMA}$

Joshua Grochow

Probleme in AM oder in MA

Antworten: