Ist Graphisomorphismus in UP coUP?

Ist (das Entscheidungsproblem) in ? Hier ist die Klasse von Entscheidungsproblemen, die von einer eindeutigen Turing-Maschine akzeptiert werden (siehe Komplexitätszoo ). $\mathsf{UP}\cap \mathsf{coUP}$ $\mathsf{UP}$

cc.complexity-theory graph-isomorphism Fayez Abdlrazaq Deab
quelle

Der Graphisomorphismus ist in UP. Allerdings , und wir wissen nicht , ob Graphisomorphie in ist , so lautet die Antwort: Wir wissen es nicht.

c o U P \subseteq c o N P

$coUP \subseteq coNP$

c o N P

$coNP$

Peter Shor

Kann ich eine Referenz für den Graphisomorphismus in UP erhalten?

SDCVVC

@PeterShor: Ich hatte den Eindruck, dass GI nicht in UP bekannt ist ... Die Menge der Isomorphismen zwischen zwei Graphen hat eine Kardinalität von entweder 0 oder entspricht der Größe der Automorphismusgruppe eines der Graphen, also der "natürlichen" "Der NP-Algorithmus ist sicherlich kein UP-Algorithmus. Hatten Sie einen anderen nicht deterministischen Algorithmus für GI im Sinn, der ein UP-Algorithmus ist?

Joshua Grochow

@ Joshua: Du hast recht. Es ist nicht bekannt, dass GI in UP ist.

Peter Shor

GI ist mindestens in SZK, der statistischen Zero-Knowledge-Klasse; nach bekannten Containments ist es daher auch in AM, coAM und coNP / poly (coAM ist in coNP / poly durch standardmäßige ungleichmäßige Derandomisierung). In diesem Artikel werden beispielsweise die bekannten Obergrenzen für SZK erörtert: cs.ucla.edu/~sahai/work/web/2003%20Publications/J.ACM2003.pdf

Andy Drucker

Antworten:

Es ist nicht bekannt, dass sich der in oder in . $\mathsf{UP}$ $\mathsf{coUP}$

Für : Der natürliche nichtdeterministische Algorithmus - erraten Sie eine Karte zwischen den beiden Graphen und prüfen Sie, ob es sich um einen Isomorphismus handelt - hat entweder 0 Zeugen (wenn die Graphen nicht isomorph sind) oderZeugen. Obwohl die meisten Graphen ( wenn Sie einen zufälligen Graphen auf Eckpunkten auswählen , steigt die Wahrscheinlichkeit, dass er nichttriviale Automorphsim enthält, mit ziemlich schnell auf ), ist dies nicht der Fall genug, um zu sagen, dass es immer höchstens einen Zeugen gibt. Dies schließt natürlich keinen anderen Algorithmus aus, der diesen in . (Schließlich ist es möglich, dass der Graphisomorphismus vorliegt $\mathsf{UP}$ $|\text{Aut}(G)|$ $|\text{Aut}(G)|=1$ $n$ $0$ $n$ $\mathsf{UP}$ $\mathsf{P} \subseteq \mathsf{UP}$ .)

Was , wissen wir, wie Peter Shor , nicht einmal, ob sich der in , also wissen wir sicherlich nicht, ob er sich in . (Unter einer plausiblen Derandomisierungsannahme steht es in , aber ich kenne keine natürliche Annahme, die es entweder in oder .) $\mathsf{coUP}$ $\mathsf{coNP}$ $\mathsf{coUP}$ $\mathsf{coNP}$ $\mathsf{UP}$ $\mathsf{coUP}$

Joshua Grochow
quelle