Kann der Isomorphismus eines Graphen mit einem Quadratwurzel-Nichtdeterminismus bestimmt werden?

Der beschränkte Nicht-Determinismus assoziiert eine Funktion mit einer Klasse von Sprachen, die von ressourcenbeschränkten deterministischen Turing-Maschinen akzeptiert werden, um eine neue Klasse - . Diese Klasse besteht aus den Sprachen, die von einer nichtdeterministischen Turing-Maschine akzeptiert werden und dieselben Ressourcengrenzen wie für die Definition von einhalten , wobei jedoch höchstens nichtdeterministische Züge ausführen darf . (Ich benutze die Notation von Goldsmith, Levy und Mundhenk anstelle des Originals von Kintala und Fischer, und ist die Größe der Eingabe.)$g(n)$$C$$g$$C$$M$$C$$M$$g(n)$$n$

Meine Frage:

Gibt es eine Konstante so dass sich GRAPH ISOMORPHISM in - ?$c\ge0$$c\sqrt{n}$$\mathsf{PTIME}$

( Edit: Joshua Grochow wies darauf hin, dass eine positive Antwort auf diese Frage einen Algorithmus für GI implizieren würde, der bessere asymptotische Laufzeitgrenzen aufweist als derzeit bekannt. Ich würde daher gerne die Grenze lockern und nichtdeterministische Züge.)$o(\sqrt{n}\log n)$

Hintergrund

Für jede feste Konstante ist - , da deterministische Bewegungen höchstens eine polynomielle Anzahl von Konfigurationen erzeugen, die deterministisch untersucht werden müssen. Außerdem kann und durch Auffüllen NP-vollständige Sprachen in - für jedes .$c \ge 0$$\mathsf{PTIME} = {c\log n}$$\mathsf{PTIME}$$c\log n$$\mathsf{NP} = \cup_c n^c\text{-}\mathsf{PTIME}$$n^\varepsilon$$\mathsf{P}$$\varepsilon > 0$

Kintala und Fischer beobachteten, dass die Entscheidung, ob ein Eingabegraph mit Eckpunkten eine -Klique hat, -vollständig ist, sich jedoch in - . Um dies zu sehen, verwerfen Sie die Eckpunkte, die höchstens Nachbarn haben. Wenn zu wenig Scheitelpunkte übrig sind, lehnen Sie ab. Ansonsten bilden die verbleibenden Eckpunkte einen Graphen der Größe . Dann errate eine Teilmenge von Vertices mit nichtdeterministische Schritte und überprüfe, ob sie in der Polynomzeit eine Clique bilden.$V$$(|V|/3)$$\mathsf{NP}$$O(\sqrt{n})$$\mathsf{PTIME}$$|V|/3 - 2$$\Omega(|V|^2)$$|V|/3$$|V| = O(\sqrt{n})$

Einige andere Sprachen dichter Graphen in befinden sich ebenfalls in - . Dies ist bei allen Problemen der Fall, bei denen eine Teilmenge der Eckpunkte als Zertifikat dient und die Größe des Eingabegraphen . Beispiele sind die vielversprechenden Versionen von Induced Path oder 3-Coloring für den Fall dichter Grafiken. Andere Probleme scheinen größere Zertifikate zu erfordern, beispielsweise scheint eine Liste von Eckpunkten, die eine Hamilton-Schaltung definieren, Bits zu erfordern . Mir ist nicht klar, ob man ein Maß an Nichtdeterminismus verwenden kann, das zu klein ist, um das Zertifikat zu erraten, um solche Probleme zu entscheiden.$L$$\mathsf{NP}$$O(\sqrt{n})$$\mathsf{PTIME}$$\Omega(|V|^2)$$\Omega(|V| \log |V|)$

Angesichts der Tatsache, dass - NP-vollständige Sprachen enthalten kann, erscheint es interessant zu fragen, wo in der begrenzten Hierarchie des Nichtdeterminismus möglicherweise einfachere Sprachen liegen. Man könnte erwarten, dass GI als eine Sprache, die nicht NP-vollständig zu sein scheint, in der Hierarchie liegt, die näher an - als an - . Das offensichtliche Zertifikat für GI gibt die Karte jedoch mitbits ist .$n^\varepsilon$$\mathsf{P}$$\log n$$\mathsf{P}$$n$$\mathsf{P}$$|V|\log |V|$$\omega(\sqrt{n})$

Eine andere Möglichkeit, über diese Frage nachzudenken: Ist die Angabe einer Karte zwischen den Scheitelpunkten ein kürzestmögliches Zertifikat für GI?

Edit: Einige weitere (korrigierte) Bemerkungen folgen, um die Kommentare von Joshua Grochow anzusprechen.

Wenn ein Zertifikat Bits verwendet und in Polynomzeit überprüft werden kann, gibt Brute Force einen Algorithmus für die GI an, der Zeit. Mit einem Zertifikat der Größe gibt Brute Force einen Algorithmus an, der Zeit in , während ein Zertifikat der Größe ergibt einen Brute-Force-Ansatz, der Zeit benötigt. Die langjährige Obergrenze von Luks ist die -Zeit, die zwischen diesen beiden Grenzen bis zu konstanten Exponenten liegt.$f(n) = \Omega(\log n)$$poly(n)2^{O(f(n))} = 2^{O(f(n))}$$O(\sqrt{n})$$2^{O(\sqrt{n})}$$O(\sqrt{n}\log n)$$2^{O(\sqrt{n}\log n)}$$2^{O(\sqrt{n\log n})}$

Diese Überlegungen deuten darauf hin, dass es einen alternativen Ansatz zu GI geben könnte. Der Ansatz von Luks scheint im Kern auf der Identifizierung einer Teilmenge von Generatoren einer assoziierten Gruppe zu beruhen. Eine nicht deterministische Maschine könnte daher eine Teilmenge der Gruppe erraten. Diese Teilmengen könnten dann eingehend geprüft werden, um einen deterministischen Algorithmus zu erhalten. Wenn die Liste der Elemente in Kürze angegeben werden kann, entweder weil die zugeordnete Gruppe nie viel größer als die Größe des Diagramms ist oder weil die Anzahl der erforderlichen Generatoren immer klein ist und die Überprüfung jeder Kandidaten-Teilmenge nicht zu lange dauert, ist dies der Fall könnte einen alternativen Ansatz zu GI ergeben.

• Chandra MR Kintala und Patrick C. Fischer, Verfeinerung des Nichtdeterminismus in der relativierten polynomzeitbegrenzten Berechnung , SIAM Journal on Computing 9 (1), 46–53, 1980. doi: 10.1137 / 0209003
• Judy Goldsmith, Matthew A. Levy, Martin Mundhenk, Begrenzter Nichtdeterminismus , SIGACT News 27 (2), 20–29, 1996. doi: 10.1145 / 235767.235769
• László Babai und Eugene M. Luks, Canonical Labeling of Graphs , STOC 1983, 171–183. doi: 10.1145 / 800061.808746

Erstens würde eine positive Antwort auf Ihre Frage (wie bereits in der Fragestellung beschrieben) den Stand der Technik im schlimmsten Fall für den Graph-Isomorphismus sofort verbessern. Für einen -Algorithmus ergibt sich ein -Zeit-Algorithmus, aber der derzeit bekannteste für GI ist nur$O(\sqrt{n})-\mathsf{PTIME}$$2^{O(\sqrt{n})}$$2^{O(\sqrt{n \log n})}$

Zweitens ist mir nicht einmal sofort klar, ob der derzeit beste Algorithmus tatsächlich ein -Algorithmus ist oder nicht, obwohl der erste Teil davon klar ist, in Etwas Sinn. Der Algorithmus zuerst errät eine Reihe von Eckpunkten Größe zu individualisieren (Zemlyachenko Trick - siehe hier für eine Ausstellung in englischer Sprache), die durch Erraten getan werden kann Bits nichtdeterministisch . Nach dem Erraten dieser Werte und dem Individualisieren (in deterministischer Polyzeit) wird jedoch der bekannteste Isomorphismustest mit beschränktem Grad angewendet, für den die Zeit (Satz 9.1 dieser Arbeit ) gilt es im Falle von$O(\sqrt{n \log n})-\mathsf{PTIME}$$\sqrt{n/\log n}$$\sqrt{n \log n}$$n^{O(d /\log d)}$$d=O(\sqrt{n \log n})$ . Ich muss mir ob der letztgenannte Algorithmus in einen -Algorithmus umgewandelt werden kann (scheint eine interessante Frage zu sein ...)$O(\sqrt{n \log n})-\mathsf{PTIME}$