2FA Zustandskomplexität von k-Clique?

15

In einfacher Form:

Kann ein endlicher Zwei-Wege-Automat v Vertex-Graphen erkennen, die ein Dreieck mit o(v3) -Zuständen enthalten?

Einzelheiten

Von Interesse sind hier v Vertex-Graphen, die unter Verwendung einer Folge von Kanten codiert sind, wobei jede Kante ein Paar von unterschiedlichen Ecken von {0,1,,v1} .

Angenommen, (Mv) ist eine Folge von endlichen Zweiwege-Automaten (deterministisch oder nicht deterministisch), so dass k -Clique auf v -Vertex-Eingabegraphen Mverkennt und s ( v ) -Zustände aufweist. Eine allgemeine Form der Frage lautet dann: Ist s ( v ) = Ω ( v k ) ?kvs(v)s(v)=Ω(vk)

Wenn k=k(v)=ω(1) und s(v)vk(v) für unendlich viele v , dann ist NL NL NP. Weniger ehrgeizig setze ich daher fest, dass k fest ist und der Fall k=3 der erste nichttriviale Fall ist.

Hintergrund

Ein Zwei-Wege-Automat (2FA) ist eine Turing-Maschine, die keinen Arbeitsbereich, nur eine feste Anzahl von internen Zuständen hat, sondern ihren schreibgeschützten Eingabekopf hin und her bewegen kann. Im Gegensatz dazu bewegt der übliche endliche Automat (1FA) seinen schreibgeschützten Eingabekopf nur in eine Richtung. Endliche Automaten können deterministisch (DFA) oder nicht deterministisch (NFA) sein sowie einen Einweg- oder Zweiwegzugriff auf ihre Eingabe haben.

Eine Grapheneigenschaft ist eine Teilmenge von Graphen. Lassen Sie Q v bezeichnen die v -eckiges Graphen mit Eigenschaft Q . Für jede Grapheneigenschaft Q kann die Sprache Q v von einem 1DFA mit höchstens 2 v ( v - 1 ) / 2 Zuständen erkannt werden , indem für jeden möglichen Graphen ein Zustand verwendet und gemäß Q bezeichnet wird und Übergänge zwischen Zuständen markiert werden durch Kanten. Q v ist daher eine reguläre Sprache für jede Eigenschaft QQQvvQQQv2v(v1)/2QQvQ. Nach dem Myhill-Nerode-Theorem gibt es dann ein einzigartiges bis zum Isomorphismus kleinstes 1DFA, das erkennt . Wenn dies 2 s ( v ) Zustände hat, ergeben Standard-Blowup-Grenzen, dass ein 2FA, der Q v erkennt, mindestens s ( v ) Ω ( 1 ) Zustände hat. Dieser Ansatz über Standard-Blowup-Grenzen ergibt also höchstens eine quadratische in- v- Untergrenze für die Anzahl der Zustände in einer 2FA für ein Q v (selbst wenn Q hart oder unentscheidbar ist).Qv2s(v)Qvs(v)Ω(1)vQvQ

k -Clique ist die Grapheneigenschaft eines vollständigen -Vertex-Teilgraphen. Das Erkennen von k- Clique v kann durch eine 1NFA erfolgen, die zunächst nicht deterministisch eine von ( vkkv Verschiedene potenziellek-Klassen, nach denen gesucht werden soll, und dann wird die Eingabe einmal gescannt, wobei nach jeder der erforderlichen Kanten gesucht wird, um die Clique zu bestätigen, und diese Kanten werden unter Verwendung von2k(k-1)/2Zuständen für jede von verfolgt die verschiedenen potenziellen Cliquen. Eine solche 1NFA hat ( v(vk)k2k(k1)/2gibt an, dass1cve ist. Wennkfest ist, sind diesΘ(vk)Zustände. Wenn Sie den bidirektionalen Zugriff auf die Eingabe zulassen, können Sie möglicherweise eine Verbesserung dieser unidirektionalen Grenze erzielen. Die Frage lautet dannk=3(vk)2k(k1)/2=(cv2(k1)/2/k)k.vk1cvekΘ(vk)k=3 ob ein 2FA besser kann als diese 1FA Obergrenze.

Nachtrag (16.04.2017): Siehe auch eine verwandte Frage zur deterministischen Zeit und eine schöne Antwort zu den bekanntesten Algorithmen . Meine Frage konzentriert sich auf den ungleichmäßigen nichtdeterministischen Raum. In diesem Zusammenhang ist die Reduktion auf Matrixmultiplikation, die von den zeiteffizienten Algorithmen verwendet wird, schlechter als der Brute-Force-Ansatz.

András Salamon
quelle
Ich mag diese Fragen wirklich! Vielen Dank für das Teilen! :)
Michael Wehar

Antworten:

7

Es scheint mir, dass Dreiecke von einem 2FA A mit (n ist die Anzahl der Eckpunkte).O(n2)

Für lautet die Idee wie folgt:k=3

  1. In Phase 1 wählt eine Kante ( i , j ) und speichert ( p h a s e 1 , i , j ) in ihrem ZustandA(i,j)(phase1,i,j)
  2. In Phase 2 bewegt es sich zu einer Kante der Form oder ( m , i ) und nimmt einen Zustand der Form an ( p h a s e 2 , j , m )(i,m)(m,i)(phase2,j,m)
  3. In Phase 3 wird geprüft, ob eine Kante (j,m) oder und es wird ein akzeptierender Zustand angenommen, wenn eine gefunden wird.(m,j)

Dies kann tatsächlich beinahe von links nach rechts erfolgen (dann könnte sich deterministisch dafür entscheiden, zuerst ( j , m ) oder ( m , j ) in Phase 2 zu wählen). Wenn jedoch die 2. Kante in der Form ( m , i ) vorliegt , muss A zuerst i und dann m lesen , dh hier wird ein einzelner Schritt nach links benötigt.A(j,m)(m,j)(m,i)Aim

Dies sollte zu Automaten mit Zuständen für k - Clique für k > 3 führen, indem zuerst eine Menge S der Größe k - 3 erraten und getestet wird, von der er Knoten hatO(nk1)kk>3Sk3 sind paarweise durch Kanten verbundenund für jeden von i, j, m in der obigen Prüfung, ob sie Kanten zu allen Knoten in S haben .SS

Thomas S
quelle
Ich sehe nicht, wie das ist ? Drei Eckpunkte i , j , m werden verfolgt. O(n2)i,j,m
András Salamon
Nur zwei gleichzeitig. Das Lesen in Phase 2 erfolgt in zwei Übergängen. Beim Lesen von i geht A grundsätzlich von (Phase 1, i, j) zu (Phase 1a, i, j) (was anzeigt, dass es gerade i gesehen hat ) und im nächsten Schritt zu (Phase 2, j, m) über. An diesem Punkt wird es mit i gemacht , da es bereits ( i , j ) und ( i , m ) gesehen hat und nur ( j , m ) überprüft werden muss. (i,m)iAii(i,j)(i,m)(j,m)
Thomas S
Wenn die Anzahl der Kanten und Scheitelpunkte ungefähr gleich ist, funktioniert dies meiner Meinung nach einwandfrei, aber der interessante Fall ist, wenn . Mit anderen Worten, ich glaube , Ihr Ansatz nutzt mindestens v e - Staaten. e=Ω(v2)ve
Michael Wehar
1
Ich glaube, Du hast recht. Wenn die Eingabe in einem netten Format erfolgt, funktioniert dies. :)
Michael Wehar
1
@ Marzio: nein, es heißt (nein, es heißt deterministisch oder nicht deterministisch)
Thomas S