Ein Beispiel, bei dem die Äquivalenz einfach ist, es jedoch schwierig ist, einen Klassenvertreter zu finden

Angenommen, wir haben eine Klasse von Objekten (z. B. Graphen, Zeichenfolgen) und eine Äquivalenzbeziehung für diese Objekte. Bei Diagrammen kann dies ein Isomorphismus sein. Für Zeichenfolgen können zwei Zeichenfolgen als äquivalent deklariert werden, wenn sie Anagramme voneinander sind.

Ich interessiere mich für die Berechnung eines Vertreters für eine Äquivalenzklasse. Das heißt, ich möchte eine Funktion f (), so dass für zwei beliebige Objekte x, y, f (x) = f (y) gilt, wenn f x und y äquivalent sind. (*)

Für das Beispiel von Anagrammen könnten f (s) Buchstaben in der Zeichenfolge sortieren, d. H. f ('cabac') = 'aabcc'. Für den Graphisomorphismus können wir f (G) als einen Graph G 'annehmen, der isomorph zu G ist und der lexikoraphisch der erste Graph ist, der diese Eigenschaft aufweist.

Nun die Frage: Gibt es ein Beispiel, bei dem das Problem der Bestimmung, ob zwei Elemente äquivalent sind, "einfach" (polyzeitlösbar) ist, während es schwierig ist, einen Repräsentanten zu finden (dh es gibt keinen polyzeitalgorithmus zur Berechnung von f (), der erfüllt ( *)).

Ok, wie wäre es mit: Zahlen und sind äquivalent, wenn entweder oder beide und Faktorisierungen und wobei , und alle Primzahlen sind und . Das heißt: Produkte zweier Primzahlen sind äquivalent, wenn sie den kleinsten Primfaktor gemeinsam haben; andere Zahlen entsprechen nur sich selbst.y x = y x $x$$y$$x=y$$x$$y$$x=pq$$y=pr$$p$$q$$r$$p < \min(q,r)$

Es ist einfach zu testen, ob zwei verschiedene Zahlen äquivalent sind: Berechnen Sie ihren GCD, testen Sie, ob er nicht trivial ist, testen Sie, ob der GCD kleiner als die Cofaktoren ist, und testen Sie, ob der GCD und seine Cofaktoren alle Primzahlen sind.

Aber es ist nicht klar , wie eine repräsentative Funktion berechnen in Polynomialzeit, und wenn Sie die Anforderung hinzufügen , dass muss gleichwertig sein dann jede repräsentative Funktion würde uns erlauben , zu Faktor der meisten Produkte von zwei Primzahlen (jeden, der isn 't seinen eigenen Vertreter).f ( x ) $f$$f(x)$$x$

Zwei ganze Zahlen mod sind äquivalent, wenn mod . Wenn man leicht eine Klasse berechnen könnte, die für diese Funktion repräsentativ ist, dann kann Factoring in probabilistischer Polynomzeit durchgeführt werden.n x 2 ≤ y 2$x,y$$n$$x^{2} \equiv y^{2}$$n$

Im Allgemeinen würde ein solches Beispiel bedeuten, dass . Angenommen, ist eine Äquivalenzrelation, die in Polynomzeit entscheidbar ist. Dann kann man durch lexikografische Suche mit einem Orakel das lexikografisch kleinste Element in der Äquivalenzklasse einer beliebigen Zeichenfolge finden. Wenn , wird dies zur Polynomzeit, sodass Sie die lexikographisch am wenigsten äquivalente Zeichenfolge als Klassenrepräsentant verwenden können. Diese Beobachtung stammt ursprünglich von Blass und Gurevich [1].R N P P = N $P \neq NP$$R$$NP$$P=NP$

Ein solches Beispiel würde auch implizieren (und daher insbesondere ).P ≠ U $UP \not\subseteq BQP$$P \neq UP$

Die Frage, die Sie gestellt haben, ist genau das, was wir als in unserer Arbeit mit Lance Fortnow [2]. Dieses Papier enthält auch die Ergebnisse, die ich hier angegeben habe, sowie das Beispiel von Hash-Funktionen, auf das Peter Shor hingewiesen hat, einige andere mögliche Beispiele und verwandte Ergebnisse und Fragen.$PEq =? Ker(FP)$

[1] Blass, A. und Gurevich, Y. Äquivalenzbeziehungen, Invarianten und Normalformen . SIAM J. Comput. 13 (4): 682 & ndash; 689, 1984.

[2] Fortnow, L. und Grochow, JA Überarbeitung der Komplexitätsklassen von Äquivalenzproblemen . Informieren. und Comput. 209 (4): 748-763, 2011. Auch im arxiv erhältlich .

Muss der "Vertreter" in der Äquivalenzklasse sein?

Wenn dies der Fall ist, nehmen Sie eine kryptografisch starke Hash- Funktion mit Kollisionsresistenz.$f$

Let wenn . Es ist einfach zu testen, ob zwei Dinge äquivalent sind. Wenn Sie jedoch , könnten Sie ein kanonisches Vorbild von , dann könnten Sie zwei Zeichenfolgen und so dass ,. Das soll hart sein (das ist Kollisionssicherheit).f ( x ) = f ( y $x \simeq y$$f(x) = f(y)\,$h x y f ( x ) = f ( y $f(x) = h$$h$$x$$y$$f(x)=f(y)\,$

Informatiker können natürlich nicht nachweisen, dass kryptografisch starke Hash-Funktionen mit Kollisionsresistenz existieren, aber sie haben eine Reihe von Kandidaten.

Erstens wird das, wonach Sie wirklich fragen, in der Regel als vollständige Invariante bezeichnet. Eine kanonische oder Normalform erfordert auch , dass äquivalent ist für alle . (Die Frage nach einem "Repräsentanten" ist etwas mehrdeutig, da einige Autoren meinen, dass dies die Bedingung der kanonischen Form einschließt.)$f(x)$$x$$x$

Zweitens, bitte verzeihen Sie die schamlose Eigenwerbung, aber dies ist genau eine der Fragen, an denen Fortnow und ich gearbeitet haben [1]. Wir haben gezeigt, dass, wenn jede Äquivalenzbeziehung, die in entschieden werden kann, auch eine vollständige Invariante in , schlimme Dinge passieren. Insbesondere würde dies . Wenn eine Versprechensversion dieser Aussage gilt (siehe Satz 4.6), dann und .$\mathsf{P}$$\mathsf{FP}$$\mathsf{UP} \subseteq \mathsf{BQP}$$\mathsf{NP} \subseteq \mathsf{BQP} \cap \mathsf{SZK}$$\mathsf{PH} = \mathsf{AM}$

Wenn Sie nun tatsächlich eine kanonische Form wünschen (ein Vertreter jeder Äquivalenzklasse, die auch in der Äquivalenzklasse enthalten ist), zeigen wir, dass noch schlimmere Dinge passieren. Das heißt, wenn jede in Polynomzeit entscheidbare Äquivalenzrelation eine kanonische Polyzeitform hat, dann gilt:

• Ganze Zahlen können in probabilistischer Polyzeit berücksichtigt werden
• Kollisionsfreie Hash-Funktionen, die in ausgewertet werden können, gibt es nicht.$\mathsf{FP}$
• $\mathsf{NP} = \mathsf{UP} = \mathsf{RP}$ (daher )$\mathsf{PH} = \mathsf{BPP}$

Für die meisten dieser Aussagen über Äquivalenzbeziehungen gibt es auch Orakel in beide Richtungen, sowohl für uns als auch für Blass und Gurevich [2].

Wenn Sie anstelle eines "beliebigen" Vertreters nach dem lexikografisch kleinsten Element in einer Äquivalenzklasse fragen, kann das lexikografisch kleinste Element in einer Äquivalenzklasse hart sein (in der Tat -hard) - auch wenn das Die Beziehung hat eine polynomzeitkanonische Form [2].$NP$$P^{NP}$

[1] Lance Fortnow und Joshua A. Grochow. Komplexitätsklassen von Äquivalenzproblemen überarbeitet . Informieren. und Comput. 209: 4 (2011), 748 & ndash; 763. Auch als arXiv erhältlich: 0907.4775v2 .

[2] Andreas Blass und Yuri Gurevich. Äquivalenzbeziehungen, Invarianten und Normalformen . SIAM J. Comput. 13: 4 (1984), 24 & ndash; 42.

Hier ist ein Versuch einer anderen Antwort, bei der die Anforderung an den "Vertreter" gelockert wird. Es muss eigentlich kein Mitglied der Äquivalenzklasse sein, sondern nur eine Funktion, die die Äquivalenzklasse identifiziert.

Angenommen, Sie haben eine Gruppe, in der Sie Mitgliedschaftstests für Untergruppen durchführen können. Das heißt, mit können Sie prüfen, ob in der von generierten Untergruppe enthalten ist . h g 1 , … , g $g_1, g_2, \ldots, g_k$$h$$g_1, \ldots, g_k$

Nehmen Sie Ihre Äquivalenzklassen als Mengen von Elementen , die dieselbe Untergruppe erzeugen. Es ist einfach zu überprüfen, ob zwei Sätze dieselbe Untergruppe erzeugen. Es ist jedoch überhaupt nicht klar, wie Sie eine eindeutige Kennung für jede Untergruppe finden können. Ich vermute, dass dies wirklich ein Beispiel ist, wenn Sie Black-Box-Gruppen mit Subgruppenmitgliedschaftstests annehmen. Ich weiß jedoch nicht, ob es eine Nicht-Orakel-Gruppe gibt, bei der dieses Problem schwer zu sein scheint.$g_1, g_2, \ldots, g_k$

Hier ist ein ausgedachtes Beispiel. Die Objekte sind Paare wobei eine SAT-Formel und eine vorgeschlagene Zuordnung zu den Variablen ist. Sagen Sie wenn und entweder (a) und beide Aufgaben erfüllen oder (b) und beide Aufgaben nicht erfüllen. Dies ist reflexiv, symmetrisch und transitiv. Jedes unbefriedigende hat eine Äquivalenzklasse, die aus allen . Jedes erfüllbare hat eine Klasse von allen mit$(H,X)$$H$$X$$(H,X) \sim (H',X')$$H=H'$$X$$X'$$X$$X'$$H$$(H,X)$$H$$(H,X)$$X$ ist eine befriedigende Aufgabe, und eine andere Klasse mit den nicht befriedigenden.

Prüfen, ob einfach ist, da wir nur prüfen, ob , dann, wenn erfüllt , dann, wenn erfüllt . Aber um ein kanonisches Mitglied einer gegebenen Klasse mit zu berechnen erfüllt durch$(H,X) \sim (H',X')$$H=H'$$X$$H$$X'$$H$$(H,X)$$H$$X$scheint zu hart (ich bin mir nicht sicher, wie ich die Härte am besten beweisen kann). Wir können SAT-Instanzen problemlos mit einer zusätzlichen Lösung ausstatten, sodass wir in der Regel keine andere Lösung finden, geschweige denn eine kanonische auswählen können. (Bearbeiten: Was ich meine ist, dass ich keinen effizienten Algorithmus zum Finden zusätzlicher Lösungen für eine erste Lösung erwarte. Wir könnten ihn verwenden, um SAT-Probleme zu lösen, indem wir zuerst eine zusätzliche Lösung in das Problem "einpflanzen" und es dann zuführen den Algorithmus (siehe Kommentare)

Dies ist zumindest für Grafiken eine offene Frage. Ich glaube, dass der neueste Fortschritt ist

Babai und Kucera, "Kanonische Kennzeichnung von Graphen in linearer Durchschnittszeit", FOCS, 1979

Dies ergibt einen (erwarteten) linearen Zeitalgorithmus für einen kanonischen Graphen, der mit der Wahrscheinlichkeit korrekt ist.$1 - \frac{1}{2^{O(n)}}$

Sie können mehr auf Wikipedia lesen . Beachten Sie, dass eine derandomisierte Version von Babais Algorithmus bedeuten würde, dass es für Diagramme kein solches Beispiel gibt.

Testen, ob zwei Kreise der Größe Kreise äquivalent sind.$\leq N$

Um festzustellen, ob Sie nur an den Eingabepunkten auswerten . Um einen Klassenrepräsentanten zu bestimmen, müsste man wahrscheinlich alle möglichen Schaltkreise testen . Für ausreichend groß ist, ist dies exponentiell schwieriger als das Testen der Schaltungsäquivalenz.2 n 2 Ω ( N log N )$C_1 \sim C_2$$2^n$$2^{\Omega(N \log N)}$$N$

Ein berühmtes Beispiel aus der deskriptiven Mengenlehre:

Definieren wir eine Äquivalenzrelation auf durch $\sim$$\mathbb R$

Dies ist eine eher "einfache" Äquivalenzbeziehung, die insbesondere messbar ist.

Aber Repräsentanten zu finden, bedeutet, ein Vitali-Set zu finden , das das Axiom of Choice erfordert und nicht messbar ist.

Lassen Sie die Objekte in Ihrem Universum die Tripel sein ( wobei ein Erfüllbarkeitsproblem für die Variablen , entweder 0 oder 1 ist und ist Bitfolge der Länge , wobei . Das heißt, ist eine Zuweisung zu , die erfüllt, wenn 1 ist, oder nicht erfüllt, wenn 0 ist. $\Phi, b, i)$$\Phi$$x_0, \ldots, x_{k-1}$$b$$i$$k$$\Phi(i)=b$$i$$x_0, \ldots, x_k$$\Phi$$b$$\Phi$$b$

Zwei Objekte sind äquivalent, wenn sie dasselbe . Einfach zu überprüfen.$\Phi$

Das repräsentative Objekt sei das lexikographisch größte unter allen in der Äquivalenzklasse.

Der Repräsentant ist NP-vollständig zu finden: Es würde SAT lösen, da wenn der lexikographisch größte , dann ist unbefriedigend; wenn es , ist es erfüllbar.$b=0$$\Phi$$b=1$

Scheint, dass die meisten NP-vollständigen Probleme auf diese Weise gestellt werden können; Es geht darum, den Mitgliedsschein in die Kodierung des Elements einzufügen.

Ich dachte, dies sei vielleicht ein Problem mit den Hausaufgaben, weshalb ich die Lösung nicht früher gepostet habe. Ich sollte gemacht haben; Ich hätte die Punkte verwenden können, die @ david-eppstien bekommen hat. Meine Güte, er braucht sie nicht.

Ich nehme an, Sie können das für praktisch jedes Problem der Art, die Sie beschreiben, leicht erreichen.

Triviales Beispiel: Angenommen, Objekte sind Zeichenfolgen und jedes entspricht nur sich selbst. Es ist immer einfach zu bestimmen, ob zwei Elemente äquivalent sind (es ist einfach Gleichheit). Sie können jedoch als Ihre bevorzugte injizierende harte Funktion definieren.f ( $x$$f()$