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