2FA Zustandskomplexität von k-Clique?

In einfacher Form:

Kann ein endlicher Zwei-Wege-Automat $v$ Vertex-Graphen erkennen, die ein Dreieck mit $o(v^3)$ -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,\dots,v-1\}$ .

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

Wenn $k = k(v) = \omega(1)$ und $s(v) \ge v^{k(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 $Q$$Q_v$$v$$Q$$Q$$Q_v$$2^{v(v-1)/2}$$Q$$Q_v$$Q$. 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).$Q_v$$2^{s(v)}$$Q_v$$s(v)^{\Omega(1)}$$v$$Q_v$$Q$

$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 ($k$$k$$_v$ 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 ($\binom{v}{k}$$k$$2^{k(k-1)/2}$gibt an, dass1≤cv≤e 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=$\binom{v}{k}2^{k(k-1)/2} = (c_v 2^{(k-1)/2}/k)^k.v^k$$1 \le c_v \le e$$k$$\Theta(v^k)$$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.

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

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 Zustand$A$$(i,j)$$(phase 1,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)$$(phase 2,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)$$A$$i$$m$

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 hat$O(n^{k-1})$$k$$k>3$$S$$k-3$ 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 .$S$$S$