Quand une propriété FO élimine-t-elle la dureté NL?

Contexte: Nous considérons uniquement les digraphes. Soit CYCLE le langage des graphes avec un cycle; c'est un problème NL-complet. Soit HASEDGE le langage des graphiques avec au moins un bord. Ensuite, trivialement, n'est plus NL-hard, tandis que reste. $\text{CYCLE} \cup \text{HASEDGE}$ $\text{CYCLE} \cup \overline{\text{HASEDGE}}$

Problème réel: je me demande si la langue est toujours NL-difficile.

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

Question: Pour quelle formule FO sur le vocabulaire des graphiques est NL-hard? Cette propriété est-elle décidable? $\phi$

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

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

Merci pour votre contribution!

cc.complexity-theory graph-theory descriptive-complexity Michaël Cadilhac
la source

Réponses:

Permettez-moi d'appeler la propriété dans votre "Problème réel" . Le mappage suivant réduit à : $\text{NODIAG}$ $\text{CYCLE}$ $\text{CYCLE} \cup \text{NODIAG}$

Pour un , remplacer chaque sommet dans par deux copies et , et s'il y a une arête dans , soit avoir des arêtes et . Ainsi pour tout le graphe satisfait . $G=(V,E)$ $v$ $G$ $v$ $v'$ $(u,v)$ $E$ $G'$ $(u,v), (u,v'), (u',v)$ $(u',v')$ $G$ $G'$ $\neg \text{NODIAG}$

De plus, a un cycle ssi a un cycle, donc satisfait ssi satisfait . Par conséquent, est NL-hard. $G'$ $G$ $G'$ $\text{CYCLE} \cup \text{NODIAG}$ $G$ $\text{CYCLE}$ $\text{CYCLE}\cup \text{NODIAG}$

Je pense qu'une construction similaire fonctionnerait pour chaque propriété purement universelle.

Jan Johannsen
la source

Merci pour votre travail Jan! Mais je ne suis pas sûr que vous ayez résolu le problème complètement, car si une structure NODIAG apparaît en G, elle apparaît toujours à la fin de votre construction, AFAIU.

Michaël Cadilhac

Oui, mais alors quoi. La construction impose que . Donc, si , alors , donc . OTOH, si , alors , et donc . Ainsi, la construction réduit à .

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, je suis profondément désolé, j'ai foiré le libellé de ma question; le sous-graphique décrit devait être considéré comme un graphique EXCLU. Notez qu'avec la formulation précédente, il vous suffirait d'ajouter quatre nouveaux nœuds et arêtes , et pour que le graphique soit hors de NODIAG. Encore une fois, je suis vraiment désolé pour les fautes de frappe.

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: comme je vous le dois pour avoir travaillé sur une question erronée, voici un article TCS avec un joli titre qui n'apparaît pas dans votre liste: Diamonds are Forever (The Variety DA) de Tesson et Therien.)

Michaël Cadilhac

Dans ce cas, que diriez-vous d'ajouter simplement un nouveau sommet dans chaque arête: dans remplacez chaque par et . Le graphe résultant est cyclique si est, et n'a pas la structure exclue. BTW Je ne maintiens plus cette liste.

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

Le vrai problème est dans FO. Tester s'il existe telle sorte que et est évidemment dans FO. $a,b,c,d \in V(G)$ $(a,c),(b,d) \in E(G)$ $(a,d),(b,c) \notin E(G)$

Supposons qu'il n'y ait pas de tels , alors admet un cycle dirigé si et seulement si admet un cycle dirigé de longueur deux. Cela peut être déduit du fait que pour deux sommets et quelconques de , leurs voisinages et sont tels que ou . $a,b,c,d$ $G$ $G$ $a$ $b$ $G$ $N^-(a)$ $N^-(b)$ $N^-(a) \subseteq N^-(b)$ $N^-(b) \subseteq N^-(a)$

Ainsi, il suffit de vérifier s'il existe tel que , qui est dans FO. $a,b \in V(G)$ $(a,b),(b,a) \in E(G)$

Donc, est dans si et seulement si $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
la source

Merci Adrien. Pourriez-vous ajouter un argument expliquant pourquoi les quartiers extérieurs de deux nœuds sont comparables? J'attendrai un peu pour voir si quelqu'un aborde le problème complet, et si personne ne se présente, je vais chercher votre réponse.

Michaël Cadilhac

Je ne pense pas que la comparabilité des quartiers extérieurs soit réelle. Prenons par exemple le graphique de seulement quatre sommets avec des arêtes et . Ce graphique satisfait la formule de Michael, mais est incomparable avec .

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 du

@Jan: Si je ne me trompe pas, le point d'Adrien est que si un graphique <i> ne </i> satisfait pas la deuxième partie, alors s'il a un cycle, il a un cycle de longueur 2. Donc, son point est que si le graphique <i> ne </i> satisfait pas la deuxième partie, alors la comparabilité est vraie.

Michaël Cadilhac