Wann tötet eine FO-Eigenschaft die NL-Härte ab?

Kontext: Wir betrachten nur Digraphen. Sei CYCLE die Sprache der Graphen mit einem Zyklus; Es ist ein NL-vollständiges Problem. Sei HASEDGE die Sprache von Graphen mit mindestens einer Kante. Dann ist trivialerweise $\text{CYCLE} \cup \text{HASEDGE}$ nicht mehr NL-hart, während $\text{CYCLE} \cup \overline{\text{HASEDGE}}$ so bleibt.

Tatsächliches Problem: Ich frage mich, ob die Sprache

CYCLE \cup {(V, E) : (\exists u, v, x, y) [E (u, v) \land E (x, y) \land \neg E (u, y) \land \neg E (x, v)]}

$\text{CYCLE} \cup \{(V, E):(\exists u,v,x,y)[E(u, v) \land E(x, y) \land \neg E(u, y) \land \neg E(x, v)]\}$ ist immer noch NL-hart.

Frage: Für welche FO-Formel $\phi$ im Vokabular von Graphen ist

CYCLE \cup {(V, E) : (V, E) ⊨ ϕ}

$\text{CYCLE} \cup \{(V, E) : (V, E) \models \phi\}$ NL-hart? Ist diese Eigenschaft entscheidbar?

Danke für deinen Beitrag!

cc.complexity-theory graph-theory descriptive-complexity Michaël Cadilhac
quelle

Antworten:

Lassen Sie mich die Eigenschaft in Ihrem "Actual Problem" . Die folgende Zuordnung reduziert auf : $\text{NODIAG}$ $\text{CYCLE}$ $\text{CYCLE} \cup \text{NODIAG}$

Ersetzen Sie für ein gegebenes jeden Scheitelpunkt in durch zwei Kopien und , und wenn es eine Kante in , lassen Sie Kanten und $G=(V,E)$ $v$ $G$ $v$ $v'$ $(u,v)$ $E$ $G'$ $(u,v), (u,v'), (u',v)$ . Somiterfülltder Graph für jedes . $(u',v')$ $G$ $G'$ $\neg \text{NODIAG}$

Darüber hinaus hat einen Zyklus, wenn einen Zyklus hat, daher erfüllt wenn erfüllt . Daher ist NL-hart. $G'$ $G$ $G'$ $\text{CYCLE} \cup \text{NODIAG}$ $G$ $\text{CYCLE}$ $\text{CYCLE}\cup \text{NODIAG}$

Ich denke, eine ähnliche Konstruktion würde für jedes rein universelle Eigentum funktionieren.

Jan Johannsen
quelle

Danke für deine Arbeit Jan! Ich bin mir jedoch nicht sicher, ob Sie das Problem vollständig gelöst haben. Wenn eine NODIAG-Struktur in G angezeigt wird, wird sie am Ende Ihrer Konstruktion immer noch angezeigt, AFAIU.

Michaël Cadilhac

G^{'} ⊨ \neg NODIAG

$G'\models \neg \text{NODIAG}$

G ⊨ CYCLE

$G\models \text{CYCLE}$

G^{'} ⊨ CYCLE

$G'\models \text{CYCLE}$

G^{'} ⊨ CYCLE \cup NODIAG

$G'\models \text{CYCLE} \cup \text{NODIAG}$

G ⊭ CYCLE

$G\not\models \text{CYCLE}$

G^{'} ⊭ CYCLE

$G'\not\models \text{CYCLE}$

G^{'} ⊭ CYCLE \cup NODIAG

$G'\not\models \text{CYCLE} \cup \text{NODIAG}$

CYCLE

$\text{CYCLE}$

CYCLE \cup NODIAG

$\text{CYCLE} \cup \text{NODIAG}$

Jan, es tut mir sehr leid, ich habe den Wortlaut meiner Frage durcheinander gebracht. Der beschriebene Untergraph war als AUSGESCHLOSSENER Graph zu betrachten. Beachten Sie, dass Sie mit dem vorherigen Wortlaut nur vier neue Knoten und Kanten , und hinzufügen müssen, damit das Diagramm nicht in NODIAG enthalten ist. Auch hier tut mir der Tippfehler sehr leid.

u, v, x, y

$u,v,x,y$

u \to v

$u \to v$

x \to y

$x \to y$

u \to y

$u \to y$

Michaël Cadilhac

(PS: Wie ich Ihnen schulde, weil Sie an einer falsch formulierten Frage gearbeitet haben, finden Sie hier ein TCS-Papier mit einem schönen Titel, der nicht in Ihrer Liste aufgeführt ist: Diamonds are Forever (The Variety DA) von Tesson und Therien.)

Michaël Cadilhac

In diesem Fall fügen Sie einfach einen neuen Scheitelpunkt in jede Kante ein: Ersetzen Sie in jedes durch und . Der resultierende Graph ist zyklisch, wenn ist, und hat nicht die ausgeschlossene Struktur. Übrigens pflege ich diese Liste nicht mehr.

G

$G$

e = (u, v)

$e = (u,v)$

(u, v_{e})

$(u,v_e)$

(v_{e}, v)

$(v_e,v)$

G^{'}

$G'$

G

$G$

Jan Johannsen

Das eigentliche Problem ist in FO. Testen, ob so dass und ist offensichtlich in FO. $a,b,c,d \in V(G)$ $(a,c),(b,d) \in E(G)$ $(a,d),(b,c) \notin E(G)$

Angenommen, es gibt kein solches , dann lässt genau dann einen gerichteten Zyklus zu, wenn einen gerichteten Zyklus der Länge zwei zulässt. Dies kann aus der Tatsache abgeleitet werden, dass für zwei beliebige Eckpunkte und von ihre Außennachbarschaften und sind, dass oder . $a,b,c,d$ $G$ $G$ $a$ $b$ $G$ $N^-(a)$ $N^-(b)$ $N^-(a) \subseteq N^-(b)$ $N^-(b) \subseteq N^-(a)$

Somit ist es ausreichend zu prüfen, ob so dass , das in FO ist. $a,b \in V(G)$ $(a,b),(b,a) \in E(G)$

Also ist dann in wenn $G$ $CYCLE \cup NODIAG$ $(\exists a,b,c,d)[(E(a,b) \wedge E(c,d) \wedge \neg E(a,d) \wedge \neg E(b,c)) \vee (E(a,b) \wedge E(b,a))]$

Adrien
quelle

Danke Adrien. Würde es Ihnen etwas ausmachen, ein Argument hinzuzufügen, warum die Außenbezirke von zwei beliebigen Knoten vergleichbar sind? Ich werde ein wenig warten, um zu sehen, ob jemand das komplette Problem angeht, und wenn niemand auftaucht, werde ich Ihre Antwort einholen.

Michaël Cadilhac

Ich denke nicht, dass die Vergleichbarkeit von Außenvierteln wirklich gilt. Nehmen Sie zB den Graphen von nur vier Eckpunkten mit den Kanten und . Dieser Graph erfüllt Michaels Formel, aber ist nicht vergleichbar mit .

a, b, c, d

$a,b,c,d$

(a, c)

$(a,c)$

(b, d)

$(b,d)$

N^{-} (a) = {c}

$N^-(a) = \{ c\}$

N^{-} (b) = {d}

$N^-(b) = \{ d\}$

Jan Johannsen

@Jan: Wenn ich mich nicht irre, ist Adriens Punkt, dass wenn ein Graph <i> den zweiten Teil nicht erfüllt, wenn er einen Zyklus hat, dann hat er einen Zyklus der Länge 2. Also ist sein Punkt Wenn der Graph <i> den zweiten Teil nicht erfüllt, gilt die Vergleichbarkeit.

Michaël Cadilhac