¿Cuándo una propiedad FO mata la dureza NL?

Contexto: consideramos solo los dígrafos. Deje que CYCLE sea el lenguaje de gráficos con un ciclo; Es un problema de NL completo. Deje que HASEDGE sea el lenguaje de gráficos con al menos un borde. Entonces, trivialmente, $\text{CYCLE} \cup \text{HASEDGE}$ ya no es NL-hard, mientras que $\text{CYCLE} \cup \overline{\text{HASEDGE}}$ sigue siéndolo.

Problema real: me pregunto si el lenguaje

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)]\}$ sigue siendo NL-hard.

Pregunta: ¿ Para qué fórmula FO $\phi$ en el vocabulario de gráficos es

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

$\text{CYCLE} \cup \{(V, E) : (V, E) \models \phi\}$ NL-hard? ¿Es esta propiedad decidible?

¡Gracias por tu contribución!

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

Respuestas:

Permítame llamar a la propiedad en su "problema real" . El siguiente mapeo reduce a : $\text{NODIAG}$ $\text{CYCLE}$ $\text{CYCLE} \cup \text{NODIAG}$

Para un dado , reemplace cada vértice en por dos copias y , y si hay un borde en , deje que tenga bordes y $G=(V,E)$ $v$ $G$ $v$ $v'$ $(u,v)$ $E$ $G'$ $(u,v), (u,v'), (u',v)$ . Así, para cada el gráfico satisface . $(u',v')$ $G$ $G'$ $\neg \text{NODIAG}$

Además, tiene un ciclo si tiene un ciclo, por lo tanto, satisface si satifica . Por lo tanto, es NL-hard. $G'$ $G$ $G'$ $\text{CYCLE} \cup \text{NODIAG}$ $G$ $\text{CYCLE}$ $\text{CYCLE}\cup \text{NODIAG}$

Creo que una construcción similar funcionaría para cada propiedad puramente universal.

Jan Johannsen
fuente

Gracias por tu trabajo Jan! Pero no estoy seguro de que haya abordado el problema por completo, ya que si una estructura NODIAG aparece en G, todavía aparece al final de su construcción, AFAIU.

Michaël Cadilhac

Sí, pero y qué. La construcción impone que

. Entonces, si

, entonces

, de ahí

. OTOH, si

, entonces , y por lo tanto . Así, la construcción reduce a .

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, lo siento mucho, me equivoqué con la redacción de mi pregunta; el subgrafo descrito se pensaba como un gráfico EXCLUIDO. Tenga en cuenta que con la redacción anterior, solo necesitaría agregar cuatro nodos nuevos y bordes , , y para que el gráfico esté fuera de NODIAG. Nuevamente, siento mucho los errores tipográficos.

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

(PD: Como le debo por trabajar en una pregunta mal redactada, aquí hay un artículo de TCS con un buen título que no aparece en su lista: Diamonds are Forever (The Variety DA) de Tesson y Therien.)

Michaël Cadilhac

En ese caso, ¿qué tal si agrega un nuevo vértice en cada borde: en reemplace cada por y . El gráfico resultante es cíclico si es, y no tiene la estructura excluida. Por cierto, ya no mantengo esa lista.

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

El problema real está en FO. Probar si existe tal que y está obviamente en FO. $a,b,c,d \in V(G)$ $(a,c),(b,d) \in E(G)$ $(a,d),(b,c) \notin E(G)$

Suponga que no existen tales , entonces admite un ciclo dirigido si y solo si admite un ciclo dirigido de longitud dos. Esto puede deducirse del hecho de que para cualquier par de vértices y de , sus fuera barrios y son tales que o . $a,b,c,d$ $G$ $G$ $a$ $b$ $G$ $N^-(a)$ $N^-(b)$ $N^-(a) \subseteq N^-(b)$ $N^-(b) \subseteq N^-(a)$

Por lo tanto, es suficiente verificar si existe tal que , que está en FO. $a,b \in V(G)$ $(a,b),(b,a) \in E(G)$

Entonces, está en si y solo 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
fuente

Gracias Adrien ¿Le importaría agregar un argumento sobre por qué los vecindarios externos de cualquiera de los dos nodos son comparables? Esperaré un poco para ver si alguien aborda el problema completo, y si no aparece nadie, buscaré su respuesta.

Michaël Cadilhac

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: si no me equivoco, el punto de Adrien es que si un gráfico <i> no </i> satisface la segunda parte, entonces si tiene un ciclo, tiene un ciclo de longitud 2. Entonces su punto es que si el gráfico <i> no </i> satisface la segunda parte, entonces la comparabilidad se mantiene.

Michaël Cadilhac