Контекст: мы рассматриваем только орграфы. Пусть CYCLE будет языком графов с циклом; это NL-полная проблема. Пусть HASEDGE будет языком графов с хотя бы одним ребром. Тогда не тривиально, CYCLE∪HASEDGE больше не NL-трудно, в то время как CYCLE∪HASEDGE¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ пребывания так.
Позвольте мне назвать имущество в вашей «Актуальной проблеме» . Следующее сопоставление уменьшает CYCLE до CYCLE ∪ NODIAG :NODIAGCYCLECYCLE∪NODIAG
Для данного замените каждую вершину 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-трудным.G′GG′CYCLE∪NODIAGGCYCLECYCLE∪NODIAG
Я думаю, что подобная конструкция будет работать для каждого чисто универсального свойства.
Спасибо за вашу работу, Ян! Но я не уверен, что вы полностью решили проблему, поскольку если в G появляется структура NODIAG, она все равно появляется в конце вашей конструкции, AFAIU.
Ян, мне очень жаль, я перепутал формулировку своего вопроса; описанный подграф должен рассматриваться как ИСКЛЮЧЕННЫЙ граф. Обратите внимание, что с предыдущей формулировкой вам просто нужно добавить четыре свежих узла и ребра , и чтобы на графике не было NODIAG. Опять же, мне очень жаль за опечатки. u,v,x,yu→vx→yu→y
Михаэль Кадилхак
(PS: Поскольку я в долгу перед вами за работу над неверно сформулированным вопросом, вот документ TCS с хорошим названием, которого нет в вашем списке: « Бриллианты навсегда» (The Variety DA) Тессона и Териена.)
Микаэль Кадилхак,
В этом случае, как насчет простого добавления новой вершины в каждое ребро: в замените каждое на и . Результирующий граф является циклическим, если есть и не имеет исключенной структуры. Кстати, я больше не поддерживаю этот список. Ge=(u,v)(u,ve)(ve,v)G′G
Ян Йоханнсен
2
Актуальная проблема в ФО. Проверка, существуют ли такие, что и явно в FO.a,b,c,d∈V(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,b∈V(G)(a,b),(b,a)∈E(G)
Таким образом, находится в тогда и только тогда, когдаGCYCLE∪NODIAG(∃a,b,c,d)[(E(a,b)∧E(c,d)∧¬E(a,d)∧¬E(b,c))∨(E(a,b)∧E(b,a))]
Спасибо Адриен. Не хотите ли добавить аргумент, почему внешние окрестности любых двух узлов сопоставимы? Я подожду немного, чтобы посмотреть, решит ли кто-нибудь всю проблему, и если никто не появится, я пойду за вашим ответом.
Михаэль Кадилхак
Я не думаю, что сопоставимость окрестностей действительно имеет место. Возьмем, к примеру, график из четырех вершин с ребрами и . Этот граф удовлетворяет формуле Майкла, но несопоставим с . ( 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> удовлетворяет второй части, то сопоставимость справедлива.
Актуальная проблема в ФО. Проверка, существуют ли такие, что и явно в FO.a,b,c,d∈V(G) (a,c),(b,d)∈E(G) (a,d),(b,c)∉E(G)
Предположим, что таких , тогда допускает направленный цикл тогда и только тогда, когда допускает направленный цикл длины два. Это можно сделать из того факта, что для любых двух вершин и группы их окрестности и таковы, что или .a,b,c,d G G a b G N−(a) N−(b) N−(a)⊆N−(b) N−(b)⊆N−(a)
Таким образом, достаточно проверить, существуют ли такие, что , который находится в FO.a,b∈V(G) (a,b),(b,a)∈E(G)
Таким образом, находится в тогда и только тогда, когдаG CYCLE∪NODIAG (∃a,b,c,d)[(E(a,b)∧E(c,d)∧¬E(a,d)∧¬E(b,c))∨(E(a,b)∧E(b,a))]
источник