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

10

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 CYCLEHASEDGEnicht mehr NL-hart, während CYCLEHASEDGE¯ so bleibt.

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

CYCLE{(V,E):(u,v,x,y)[E(u,v)E(x,y)¬E(u,y)¬E(x,v)]}
ist immer noch NL-hart.

Frage: Für welche FO-Formel ϕ im Vokabular von Graphen ist

CYCLE{(V,E):(V,E)ϕ}
NL-hart? Ist diese Eigenschaft entscheidbar?

Danke für deinen Beitrag!

Michaël Cadilhac
quelle

Antworten:

4

Lassen Sie mich die Eigenschaft in Ihrem "Actual Problem" . Die folgende Zuordnung reduziert CYCLE auf CYCLE NODIAG :NODIAGCYCLECYCLENODIAG

Ersetzen Sie für ein gegebenes jeden Scheitelpunkt v in G durch zwei Kopien v und v ' , und wenn es eine Kante ( u , v ) in E gibt , lassen Sie G ' Kanten ( u , v ) haben , ( u , v ' ) , ( u ' , v ) und ( u ' , vG=(V,E)vGvv(u,v)EG(u,v),(u,v),(u,v) . Somiterfülltder Graph G ' für jedes G ¬ NODIAG .(u,v)GG¬NODIAG

Darüber hinaus hat einen Zyklus, wenn G einen Zyklus hat, daher erfüllt G ' CYCLE NODIAG, wenn G CYCLE erfüllt . Daher ist CYCLE NODIAG NL-hart.GGGCYCLENODIAGGCYCLECYCLENODIAG

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¬NODIAGGCYCLEGCYCLEGCYCLENODIAGGCYCLEGCYCLEGCYCLENODIAGCYCLECYCLENODIAG
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,yuvxyuy
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. Ge=(u,v)(u,ve)(ve,v)GG
Jan Johannsen
2

Das eigentliche Problem ist in FO. Testen, ob so dass und ist offensichtlich in FO.a,b,c,dV(G)(a,c),(b,d)E(G)(a,d),(b,c)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,dGGabGN(a)N(b)N(a)N(b)N(b)N(a)

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

Also ist dann in wennGCYCLENODIAG(a,b,c,d)[(E(a,b)E(c,d)¬E(a,d)¬E(b,c))(E(a,b)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 , c ) ( b , d ) N - ( a ) = { c } N - ( b ) = { d }a,b,c,d(a,c)(b,d)N(a)={c}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