Quando uma propriedade FO mata a dureza NL?

Contexto: Consideramos apenas dígitos. Deixe CYCLE ser a linguagem dos gráficos com um ciclo; é um problema NL-completo. Seja HASEDGE o idioma dos gráficos com pelo menos uma aresta. Em seguida, trivialmente, não é mais NL, enquanto permanece assim. $\text{CYCLE} \cup \text{HASEDGE}$ $\text{CYCLE} \cup \overline{\text{HASEDGE}}$

Problema real: Gostaria de saber se o idioma ainda é NL-difícil.

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

Pergunta: Para qual fórmula FO no vocabulário dos gráficos é NL-difícil? Esta propriedade é decidível? $\phi$

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

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

Obrigado pela sua contribuição!

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

Respostas:

Deixe-me chamar a propriedade no seu "Problema real" . O mapeamento a seguir reduz para : $\text{NODIAG}$ $\text{CYCLE}$ $\text{CYCLE} \cup \text{NODIAG}$

Para um dado , substituir cada vértice em por duas cópias e se existe uma aresta em , deixar têm bordas e . Assim, para todo o gráfico satisfaz . $G=(V,E)$ $v$ $G$ $v$ $v'$ $(u,v)$ $E$ $G'$ $(u,v), (u,v'), (u',v)$ $(u',v')$ $G$ $G'$ $\neg \text{NODIAG}$

Além disso, tem um ciclo se tiver um ciclo, portanto satisfaz se satisfizer . Portanto, é NL-difícil. $G'$ $G$ $G'$ $\text{CYCLE} \cup \text{NODIAG}$ $G$ $\text{CYCLE}$ $\text{CYCLE}\cup \text{NODIAG}$

Penso que uma construção semelhante funcionaria para todas as propriedades puramente universais.

Jan Johannsen
fonte

Obrigado pelo seu trabalho Jan! Mas não sei se você resolveu o problema completamente, pois se uma estrutura NODIAG aparecer em G, ela ainda aparecerá no final de sua construção, AFAIU.

Michaël Cadilhac

Sim, mas e daí. A construção impõe que . Portanto, se , , portanto . OTOH, se , então e, portanto, . Portanto, a construção reduz para .

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, sinto muito, eu errei com a redação da minha pergunta; o subgrafo descrito deveria ser pensado como um gráfico EXCLUÍDO. Observe que, com a redação anterior, você só precisará adicionar quatro nós bordas , , e para que o gráfico fique fora de NODIAG. Mais uma vez, sinto muito pelos erros de digitação.

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: Como devo a você por trabalhar em uma pergunta incorreta, aqui está um documento da TCS com um bom título que não aparece em sua lista: Diamonds are Forever (The Variety DA) de Tesson e Therien.)

Michaël Cadilhac,

Nesse caso, que tal apenas adicionar um novo vértice em cada aresta: em substitua todo por e . O gráfico resultante é cíclico se é e não possui a estrutura excluída. Aliás, não estou mais mantendo essa 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

O problema real está no FO. Teste se existe tal que e está obviamente em FO. $a,b,c,d \in V(G)$ $(a,c),(b,d) \in E(G)$ $(a,d),(b,c) \notin E(G)$

Suponha que não exista , então admite um ciclo direcionado se e somente se admite um ciclo direcionado de comprimento dois. Isto pode ser deduzido do facto de que para quaisquer dois vértices e de , as suas out-bairros e são tais 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)$

Assim, é suficiente verificar se existe modo que , que está em FO. $a,b \in V(G)$ $(a,b),(b,a) \in E(G)$

Então, está em se e somente se $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
fonte

Obrigado Adrien. Você gostaria de adicionar um argumento sobre por que as vizinhanças externas de dois nós são comparáveis? Vou esperar um pouco para ver se alguém soluciona o problema completo e, se ninguém aparecer, eu responderei.

Michaël Cadilhac

Não acho que a comparabilidade de bairros externos seja realmente válida. Tome, por exemplo, o gráfico de apenas quatro vértices com arestas e . Este gráfico satisfaz a fórmula de Michael, mas é incomparável com .

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: Se não me engano, o argumento de Adrien é que, se um gráfico não satisfizer a segunda parte, se houver um ciclo, ele terá um ciclo de comprimento 2. Portanto, seu argumento é que, se o gráfico não atender à segunda parte, a comparabilidade será válida.

Michaël Cadilhac