Czy istnieje algorytm, który wyszukuje zakazanych nieletnich?

Twierdzenie Robertsona-Seymour'a głosi, że każda niewielka, zamknięta rodzina $\mathcal G$ wykresów można scharakteryzować przez skończoną liczbę zakazanych nieletnich.

Czy istnieje algorytm wejściowy $\mathcal G$ wypuszcza zakazanych nieletnich, czy jest to nierozstrzygalne?

Oczywiście odpowiedź może zależeć od tego, w jaki sposób $\mathcal G$ jest opisany na wejściu. Na przykład jeśli $\mathcal G$ jest podany przez $M_\mathcal G$ które mogą decydować o członkostwie, nie możemy nawet zdecydować, czy $M_\mathcal G$ kiedykolwiek coś odrzuca. Gdyby $\mathcal G$ pochodzi od wielu zakazanych nieletnich - cóż, właśnie tego szukamy. Byłbym ciekawy poznać odpowiedź, jeśli $M_\mathcal G$ gwarantuje zatrzymanie się na każdym $G$ w określonym czasie w $|G|$ . Interesują mnie również wszelkie powiązane wyniki $\mathcal G$ okazało się być nieznacznie zamknięte z jakimś innym certyfikatem (jak w przypadku $TFNP$ lub ŹLE PROOF ).

Aktualizacja: Pierwsza wersja mojego pytania okazała się dość łatwa, w oparciu o pomysły Marzio i Kimpela, rozważ następującą konstrukcję. $M_\mathcal G$ akceptuje wykres na $n$ wierzchołki wtedy i tylko wtedy $M$ nie zatrzymuje się $n$ kroki. Jest to niewielkie zamknięcie, a czas działania zależy tylko od $|G|$ .

graph-theory decidability graph-minor domotorp
źródło

Gdyby

G

$\mathcal G$ jest reprezentowany przez zawsze zatrzymującą się TM

M_{G}

$M_\mathcal G$ , możesz zredukować do tego problem zatrzymania: dane

M

$M$ budować

M_{G} (G_{x})

$M_\mathcal G( G_x )$ to daje wynik tak wtedy i tylko wtedy

M

$M$ zatrzymuje się dokładnie w

x

$x$ kroki (

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

$(G_1,G_2,...$ to standardowe wyliczenie wykresu).

M_{G} (G_{x})

$M_\mathcal G( G_x )$ akceptuje co najwyżej jeden zakazany nieletni, więc

G

$\mathcal G$ jest niepełnoletnią rodziną; stąd problem jest nierozstrzygalny.

Marzio De Biasi

@ThomasKlimpel: Ops, źle zrozumiałem pytanie. Być może poprawka to:

M_{G} (G_{x})

$M_\mathcal G( G_x )$ wyszukaj pierwszy

G_{i}, i \leq x

$G_i, i \leq x$ takie, że

M

$M$ zatrzymuje się dokładnie w

i

$i$ kroki, a następnie zaakceptuj if

G_{i}

$G_i$ nie jest nieletni z

G_{x}

$G_x$ ; odrzuć inaczej.

Marzio De Biasi

@Marzio Tak, aby uprościć:

M_{G}

$M_\mathcal G$ akceptuje wykres na

n

$n$ wierzchołki wtedy i tylko wtedy

M

$M$ nie zatrzymuje się

n

$n$ kroki. Jest to niewielkie zamknięcie, a czas działania zależy tylko od

| G |

$|G|$ .

domotorp

Cóż, interpretuję to jako zatrzymanie

M

$M$ zatrzymuje się

2

$2$ kroki, a następnie mówimy, że zatrzymuje się

3

$3$ kroki.

domotorp

@domotorp Ponieważ twoja konstrukcja działa (jeśli się nie mylę) i odpowiada na jedno z twoich pytań (a ponieważ Marzio De Biasi i ja próbowaliśmy wymyślić taką prostą konstrukcję bez powodzenia), myślę, że powinieneś zmienić swoją konstrukcję w właściwa odpowiedź. Możesz zrobić z niej wiki społeczności, jeśli czujesz się niepewnie, odpowiadając na własne pytanie. Alternatywnie możesz edytować swoje pytanie i tam dodać odpowiedź.

Thomas Klimpel,

Odpowiedzi:

Odpowiedź Mamadou Moustapha Kanté (który zrobił doktorat pod nadzorem Bruno Courcelle'a) na podobne pytanie przytacza Notę o możliwości obliczenia zestawów niewielkich przeszkód na wykresie dla ideałów monadycznych drugiego rzędu (1997) B. Courcelle, R. Downeya i M. Stypendyści za wynik niemożliwy do obliczenia (dla klas grafów definiowanych przez MSOL , tj. Klas zdefiniowanych przez formułę Monadic drugiego rzędu) oraz Przeszkody w niewielkim zamkniętym zbiorze grafów zdefiniowanym przez gramatykę bezkontekstową (1998) przez B Courcelle i G. Sénizergues dla wyniku obliczalności (dla klas grafów definiowanych przez HR , tj. Klas zdefiniowanych przez gramatykę zastępczą Hyperedge).

Zasadniczą różnicą między przypadkiem obliczalnym a nieprzeznaczalnym jest to, że (niewielkie-zamknięte) klasy grafów definiowane przez HR mają ograniczoną szerokość, podczas gdy (małe-zamknięte) klasy grafów definiowane przez MSOL nie muszą mieć ograniczonej szerokości. W rzeczywistości, jeśli (nieznacznie zamknięta) klasa grafu definiowana przez MSOL ma ograniczoną szerokość, to jest ona również definiowalna przez HR.

Szerokość grzbietu wydaje się być naprawdę kluczową częścią do oddzielenia obliczeń od przypadków, które nie są obliczalne. Inny znany wynik (M. Fellows i M􏰊.􏰊 Langston) w zasadzie mówi, że jeśli znane jest ograniczenie maksymalnej szerokości (lub szerokości ścieżki) skończonego zestawu wykluczonych nieletnich, wówczas (skończony) minimalny zestaw wykluczonych nieletnich staje się obliczeniowy.

Nie wiadomo nawet, czy (skończony) minimalny zestaw wykluczonych nieletnich dla związku (który jest trywialnie niewielki-zamknięty) dwóch mniejszych zamkniętych klas grafowych, każda podana przez ich odpowiedni skończony zestaw wykluczonych nieletnich, można obliczyć, jeśli nie ma informacji o szerokości (lub szerokości ścieżki) jest dostępna. A może w międzyczasie udowodniono nawet, że ogólnie nie da się go obliczyć.

Thomas Klimpel
źródło

Ta ostatnia część jest dość interesująca. Jeśli dobrze to rozumiesz, oznacza to, co następuje. Dla rodziny grafów

G

$\mathcal G$ , oznaczony przez

m (G)

$m(\mathcal G)$ wielkość największej zabronionej minimalnej nieletniej. Pozwolić

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\}$ . Wtedy nie ma żadnej znanej rekurencyjnej górnej granicy

f (n)

$f(n)$ . Czy znasz jakieś przykłady, które to pokazują

f (n)

$f(n)$ rośnie bardzo szybko?

domotorp

@domotorp Zgadzam się, dobra uwaga. Mam kilka pomysłów na takie przykłady, ale mam wrażenie, że tempo wzrostu wszystkich moich przykładów (które w zasadzie próbują grać w wymiarze „siatki”) pozostanie w granicach ELEMENTARY. Uważam jednak, że jeśli chciałbym zainwestować czas w te pytania, powinienem najpierw zapoznać się z literaturą na temat tego, co wydarzyło się w latach 2000–2018, być może przeglądając artykuły, które cytują artykuły, o których wiem, lub patrząc w późniejszych publikacjach autorów, którzy pracowali nad tymi pytaniami.

Thomas Klimpel,

Rozumiem - cóż, nie desperacko znam odpowiedź, tylko się zdziwiłem i zaciekawiłem ...

domotorp

@domotorp Wykazano, że minimalny zestaw wykluczonych nieletnich dla związku można obliczyć w 2008 r .: logic.las.tu-berlin.de/Members/Kreutzer/Publications/...

Thomas Klimpel