Когда свойство FO убивает NL-твердость?

10

Контекст: мы рассматриваем только орграфы. Пусть CYCLE будет языком графов с циклом; это NL-полная проблема. Пусть HASEDGE будет языком графов с хотя бы одним ребром. Тогда не тривиально, CYCLEHASEDGE больше не NL-трудно, в то время как CYCLEHASEDGE¯ пребывания так.

Актуальная проблема: мне интересно, если язык

CYCLE{(V,E):(u,v,x,y)[E(u,v)E(x,y)¬E(u,y)¬E(x,v)]}
по-прежнему NL-труден.

Вопрос: Для какой формулы FO ϕ на словаре графов

CYCLE{(V,E):(V,E)ϕ}
NL-трудно? Является ли это свойство разрешимым?

Спасибо за ваш вклад!

Михаэль Кадилхак
источник

Ответы:

4

Позвольте мне назвать имущество в вашей «Актуальной проблеме» . Следующее сопоставление уменьшает CYCLE до CYCLE NODIAG :NODIAGCYCLECYCLENODIAG

Для данного замените каждую вершину v в G двумя копиями v и v , и если в E есть ребро ( u , v ) , пусть G имеет ребра ( u , v ) , ( u , v ) , ( u , v ) и ( u , vG=(V,E)vGvv(u,v)EG(u,v),(u,v),(u,v) . Таким образомдля любого G граф G ' удовлетворяет ¬ NODIAG .(u,v)GG¬NODIAG

Кроме того, имеет цикл, если G имеет цикл, поэтому G ' удовлетворяет CYCLE NODIAG, если G удовлетворяет CYCLE . Поэтому CYCLE NODIAG является NL-трудным.GGGCYCLENODIAGGCYCLECYCLENODIAG

Я думаю, что подобная конструкция будет работать для каждого чисто универсального свойства.

Ян Йоханнсен
источник
Спасибо за вашу работу, Ян! Но я не уверен, что вы полностью решили проблему, поскольку если в G появляется структура NODIAG, она все равно появляется в конце вашей конструкции, AFAIU.
Михаэль Кадилхак
G¬NODIAGGCYCLEGCYCLEGCYCLENODIAGGCYCLEGCYCLEGCYCLENODIAGCYCLECYCLENODIAG
Ян, мне очень жаль, я перепутал формулировку своего вопроса; описанный подграф должен рассматриваться как ИСКЛЮЧЕННЫЙ граф. Обратите внимание, что с предыдущей формулировкой вам просто нужно добавить четыре свежих узла и ребра , и чтобы на графике не было NODIAG. Опять же, мне очень жаль за опечатки. u,v,x,yuvxyuy
Михаэль Кадилхак
(PS: Поскольку я в долгу перед вами за работу над неверно сформулированным вопросом, вот документ TCS с хорошим названием, которого нет в вашем списке: « Бриллианты навсегда» (The Variety DA) Тессона и Териена.)
Микаэль Кадилхак,
В этом случае, как насчет простого добавления новой вершины в каждое ребро: в замените каждое на и . Результирующий граф является циклическим, если есть и не имеет исключенной структуры. Кстати, я больше не поддерживаю этот список. Ge=(u,v)(u,ve)(ve,v)GG
Ян Йоханнсен
2

Актуальная проблема в ФО. Проверка, существуют ли такие, что и явно в FO.a,b,c,dV(G)(a,c),(b,d)E(G)(a,d),(b,c)E(G)

Предположим, что таких , тогда допускает направленный цикл тогда и только тогда, когда допускает направленный цикл длины два. Это можно сделать из того факта, что для любых двух вершин и группы их окрестности и таковы, что или .a,b,c,dGGabGN(a)N(b)N(a)N(b)N(b)N(a)

Таким образом, достаточно проверить, существуют ли такие, что , который находится в FO.a,bV(G)(a,b),(b,a)E(G)

Таким образом, находится в тогда и только тогда, когдаGCYCLENODIAG(a,b,c,d)[(E(a,b)E(c,d)¬E(a,d)¬E(b,c))(E(a,b)E(b,a))]

Adrien
источник
Спасибо Адриен. Не хотите ли добавить аргумент, почему внешние окрестности любых двух узлов сопоставимы? Я подожду немного, чтобы посмотреть, решит ли кто-нибудь всю проблему, и если никто не появится, я пойду за вашим ответом.
Михаэль Кадилхак
Я не думаю, что сопоставимость окрестностей действительно имеет место. Возьмем, к примеру, график из четырех вершин с ребрами и . Этот граф удовлетворяет формуле Майкла, но несопоставим с . ( a , c ) ( b , d ) N - ( a ) = { c } N - ( b ) = { d }a,b,c,d(a,c)(b,d)N(a)={c}N(b)={d}
Ян Йоханнсен
@Jan: Если я не ошибаюсь, Адриен считает, что если график <i> не </ i> удовлетворяет второй части, то если у него есть цикл, он имеет цикл длины 2. Таким образом, его точка что если граф <i> не </ i> удовлетворяет второй части, то сопоставимость справедлива.
Микаэль Кадилхак