Есть ли алгоритм, который находит запрещенных несовершеннолетних?

Теорема Робертсона – Сеймура говорит, что любая минор-замкнутая семья $\mathcal G$ графов можно охарактеризовать конечным числом запрещенных миноров.

Есть ли алгоритм, который для входа $\mathcal G$ выводит запрещенных несовершеннолетних или это неразрешимо?

Очевидно, что ответ может зависеть от того, как $\mathcal G$ описано во входе. Например, если $\mathcal G$ дается $M_\mathcal G$ которые могут решить членство, мы даже не можем решить, $M_\mathcal G$ когда-либо отвергает что-либо. Если $\mathcal G$ дается конечным числом запрещенных несовершеннолетних - ну, это то, что мы ищем. Мне было бы интересно узнать ответ, если $M_\mathcal G$ гарантированно остановится на любом $G$ в какое-то фиксированное количество времени в $|G|$ , Я также заинтересован в любых связанных результатах, где $\mathcal G$ доказано, что он является второстепенным с некоторым другим сертификатом (как в случае $TFNP$ или НЕПРАВИЛЬНО ДОКАЗАТЕЛЬСТВО ).

Обновление: Первая версия моего вопроса оказалась довольно простой, основываясь на идеях Марцио и Кимпела, рассмотрим следующую конструкцию. $M_\mathcal G$ принимает график на $n$ вершины тогда и только тогда, когда $M$ не останавливается в $n$ шаги. Это второстепенное закрытие и время работы зависит только от $|G|$ ,

graph-theory decidability graph-minor domotorp
источник

Если

G

$\mathcal G$ представлена всегда останавливающейся ТМ

M_{G}

$M_\mathcal G$ Вы можете уменьшить проблему остановки: данный

M

$M$ строить

M_{G} (G_{x})

$M_\mathcal G( G_x )$ что выводит да, если и только если

M

$M$ останавливается именно в

x

$x$ шаги (

(G_{1}, G_{2}, . . .

$(G_1,G_2,...$ стандартное перечисление графа).

M_{G} (G_{x})

$M_\mathcal G( G_x )$ принимает не более одного запрещенного несовершеннолетнего, поэтому

G

$\mathcal G$ является закрытой несовершеннолетней семьей; следовательно, проблема неразрешима.

Марцио Де Биаси

@ThomasKlimpel: Упс, я неправильно понял вопрос. Возможно, исправить это:

M_{G} (G_{x})

$M_\mathcal G( G_x )$ искать первый

G_{i}, i \leq x

$G_i, i \leq x$ такой, что

M

$M$ останавливается именно в

i

$i$ шаги затем принять, если

G_{i}

$G_i$ не несовершеннолетний

G_{x}

$G_x$ ; отклонить иначе.

Марцио Де Биаси

@ Марцио Да, чтобы упростить:

M_{G}

$M_\mathcal G$ принимает график на

n

$n$ вершины тогда и только тогда, когда

M

$M$ не останавливается в

n

$n$ шаги. Это второстепенное закрытие и время работы зависит только от

| G |

$|G|$ ,

Домоторп

Ну, я понимаю, что если

M

$M$ останавливается в

2

$2$ шаги, то мы также говорим, что он останавливается в

3

$3$ шаги.

Домоторп

@domotorp Поскольку ваши строительные работы (если я не ошибаюсь) и ответы на один из ваших вопросов (а так как мы с Марцио Де Биаси пытались придумать такую простую конструкцию без успеха), я думаю, вы должны превратить свою конструкцию в правильный ответ. Вы можете сделать это вики-сообществом, если вам неловко отвечать на свой вопрос. Кроме того, вы можете отредактировать свой вопрос и добавить туда ответ.

Томас Климпел

Ответы:

В ответе Мамаду Мустафы Канте (который защитил докторскую диссертацию под руководством Бруно Курселя) на аналогичный вопрос приводятся заметка о вычислимости наборов второстепенных графов для монадических идеалов второго порядка (1997 г.) Б. Курселя, Р. Дауни и М. Товарищи за невычислимый результат (для классов графов, определяемых MSOL , т. Е. Классов , определенных монадической формулой второго порядка) и Препятствия в минор-замкнутом множестве графов, определенных грамматикой без контекста (1998), написанной B Courcelle и G. Sénizergues для результата вычислимости (для HR-определяемых классов графов, то есть классов, определенных грамматикой замены Hyperedge).

Принципиальное различие между вычислимым и невычислимым случаем состоит в том, что (минор-замкнутые) HR-определяемые классы графов имеют ограниченную ширину дерева, в то время как (минор-замкнутые) MSOL-определяемые графы классов не должны иметь ограниченную древовидную ширину. Фактически, если (неосновно замкнутый) класс графов, определяемых MSOL, имеет ограниченную ширину дерева, то он также определяется HR.

Кажется, что ширина дерева действительно важная часть для отделения вычислимых случаев от невычислимых случаев. Другой известный результат (M. Fellows и M􏰊.􏰊 Langston) в основном говорит о том, что если известна оценка максимальной ширины дерева (или ширины пути) конечного набора исключенных миноров, то (конечный) минимальный набор исключенных миноров становится вычислим.

Даже неизвестно, может ли быть вычислен (конечный) минимальный набор исключенных миноров для объединения (которое тривиально минорно-замкнуто) двух классов минор-замкнутых графов, каждый из которых задан их соответствующим конечным набором исключенных миноров, если нет информации о ширине дерева (или ширине пути) доступно. Или, может быть, тем временем было даже доказано, что это вообще не вычислимо.

Томас Климпел
источник

Эта последняя часть довольно интересная. Если хорошо понимать, это подразумевает следующее. Для семейства графов

G

$\mathcal G$ обозначим через

m (G)

$m(\mathcal G)$ размер самого большого запрещенного минимального несовершеннолетнего. Позволять

f (n) = max {m (G_{1} \cup G_{2}) ∣ m (G_{1}), m (G_{2}) \leq n}

$f(n)=\max \{m(\mathcal G_1 \cup \mathcal G_2)\mid m(\mathcal G_1),m(\mathcal G_2)\le n\}$ . Then there is no known recursive upper bound for

f (n)

$f(n)$ . Do you know some examples that show that

f (n)

$f(n)$ grows very fast?

domotorp

@domotorp I agree, good point. I do have some ideas for such examples, but I have the impression that the growth rate of all my examples (which basically try to play with "grid" dimension) will stay within ELEMENTARY. However, I believe that if I wanted to invest time into those questions, then I should first do a literature study about what happened in the years 2000-2018, perhaps by looking at papers that quote the papers that I know about, or by looking at later publications of the authors which worked on those questions.

Thomas Klimpel

I see - well, I'm not desperate to know the answer, just I got surprised and became curious...

domotorp

@domotorp The minimal set of excluded minors for the union has been shown to be computable in 2008: logic.las.tu-berlin.de/Members/Kreutzer/Publications/…

Thomas Klimpel