Kiedy właściwość FO zabija twardość NL?

Kontekst: Rozważamy tylko digrafy. Niech CYKL będzie językiem grafów z cyklem; jest to problem kompletny dla NL. Niech HASEDGE będzie językiem grafów z co najmniej jedną krawędzią. Zatem w sposób trywialny nie jest już trudny dla NL, podczas gdy zostaje. $\text{CYCLE} \cup \text{HASEDGE}$ $\text{CYCLE} \cup \overline{\text{HASEDGE}}$

Rzeczywisty problem: zastanawiam się, czy język jest wciąż trudny do użycia w NL.

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)]\}$

Pytanie: Dla której formuły FO w słowniku wykresów jest NL-hard? Czy ta właściwość jest rozstrzygalna? $\phi$

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

$\text{CYCLE} \cup \{(V, E) : (V, E) \models \phi\}$

Dzięki za wkład!

cc.complexity-theory graph-theory descriptive-complexity

— Michaël Cadilhac
źródło

Odpowiedzi:

Pozwól mi zadzwonić do właściwości w „Rzeczywistym problemie” . Poniższe mapowanie zmniejsza do : $\text{NODIAG}$ $\text{CYCLE}$ $\text{CYCLE} \cup \text{NODIAG}$

Dla danego zamień każdy wierzchołek w na dwie kopie i , a jeśli w jest krawędź , niech ma krawędzie i . Zatem dla każdego wykres spełnia . $G=(V,E)$ $v$ $G$ $v$ $v'$ $(u,v)$ $E$ $G'$ $(u,v), (u,v'), (u',v)$ $(u',v')$ $G$ $G'$ $\neg \text{NODIAG}$

Ponadto, ma cykl iff ma cykl, dlatego spełnia iff satified . Dlatego jest trudny dla NL. $G'$ $G$ $G'$ $\text{CYCLE} \cup \text{NODIAG}$ $G$ $\text{CYCLE}$ $\text{CYCLE}\cup \text{NODIAG}$

Myślę, że podobna konstrukcja działałaby dla każdej czysto uniwersalnej własności.

— Jan Johannsen
źródło

Dzięki za twoją pracę Jan! Ale nie jestem pewien, czy rozwiązałeś ten problem całkowicie, ponieważ jeśli struktura NODIAG pojawi się w G, nadal pojawia się na końcu twojej konstrukcji, AFAIU.

— Michaël Cadilhac

Tak, ale co z tego. Konstrukcja wymusza, że . Więc jeśli , to , stąd . OTOH, jeśli , to , a zatem . W ten sposób konstrukcja redukuje do .

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 Johannsen

Jan, bardzo mi przykro, pomieszałem z treścią mojego pytania; opisany podgraf miał być traktowany jako WYKLUCZONY wykres. Zauważ, że przy poprzednim sformułowaniu wystarczy dodać cztery nowe węzły i krawędzie , i aby wykres był poza NODIAG. Znowu bardzo przepraszam za literówki.

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: Ponieważ jestem ci winien pracę nad źle sformułowanym pytaniem, oto artykuł TCS z ładnym tytułem, który nie pojawia się na twojej liście: Diamonds are Forever (The Variety DA) autorstwa Tesson i Therien.)

— Michaël Cadilhac

W takim razie, co powiesz na dodanie nowego wierzchołka na każdej krawędzi: w zamień każdy na i . Powstały wykres jest cykliczny, jeżeli jest i nie ma wykluczonej struktury. BTW, nie utrzymuję już tej listy.

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

Rzeczywisty problem dotyczy FO. Testowanie, czy istnieje tak że i jest oczywiście w FO. $a,b,c,d \in V(G)$ $(a,c),(b,d) \in E(G)$ $(a,d),(b,c) \notin E(G)$

Załóżmy, że nie ma takiego , a następnie dopuszcza kierowany cykl wtedy i tylko wtedy, gdy dopuszcza ukierunkowany cykl o długości dwa. Można to wywnioskować z tego, że dla dowolnych dwóch wierzchołków i z , ich wyczerpanym sąsiedztwie i są takie, że lub . $a,b,c,d$ $G$ $G$ $a$ $b$ $G$ $N^-(a)$ $N^-(b)$ $N^-(a) \subseteq N^-(b)$ $N^-(b) \subseteq N^-(a)$

Wystarczy więc sprawdzić, czy istnieje tak że , który jest w FO. $a,b \in V(G)$ $(a,b),(b,a) \in E(G)$

Tak więc jest w wtedy i tylko wtedy, gdy $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
źródło

Dzięki Adrien. Czy zechciałby pan dodać argument dotyczący tego, dlaczego sąsiedztwa dowolnych dwóch węzłów są porównywalne? Poczekam chwilę, aby sprawdzić, czy ktoś rozwiązuje cały problem, a jeśli nikt się nie pojawi, poszukaj odpowiedzi.

— Michaël Cadilhac

Nie sądzę, aby porównywalność dzielnic naprawdę się utrzymywała. Weź np. Wykres tylko czterech wierzchołków z krawędziami i . Ten wykres jest zgodny ze wzorem Michaela, ale jest nieporównywalny z .

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: Jeśli się nie mylę, Adrien ma na myśli to, że jeśli wykres <i> nie </i> spełnia drugiej części, to jeśli ma cykl, ma cykl długości 2. Więc jego argumentem jest że jeśli wykres <i> nie </i> spełnia drugiej części, wówczas zachowana jest porównywalność.

— Michaël Cadilhac