Wnioski z odwrotnej siły matematycznej twierdzenia graf moll

Załóżmy, że mamy właściwość grafu, którą można sprawdzić w niedeterministycznym czasie wielomianowym, oraz dowód w słabym systemie formalnym (powiedzmy RCA ₀ ), że właściwość jest nieznacznie zamknięta. Czy możemy powiedzieć coś o sile systemu formalnego, który jest w stanie udowodnić, że dany skończony zestaw wykluczonych nieletnich charakteryzuje daną właściwość graficzną?

Kontekst Dobrze wiadomo, że już prosta wersja (bez dobrze uporządkowanego zestawu etykiet) twierdzenia o drzewie Kruskala jest nie do udowodnienia w ATR _0, a twierdzenie o grafie mniejszym jest uogólnieniem tego twierdzenia, którego nawet nie da się udowodnić w Π ¹ ₁ -CA ₀ . Friedman zastosował tę prostą wersję twierdzenia o drzewku Kruskala, aby skonstruować szybko rosnącą funkcję TREE (n) , i zastosował twierdzenie o grafie mniejszym, aby skonstruować jeszcze szybciej rosnącą funkcję SSCG (n) . To miłe przykłady wniosków dotyczących treści obliczeniowych z odwrotnej siły matematycznej, ale pozostawiają bardziej bezpośrednie pytanie postawione powyżej bez odpowiedzi.

Mianowicie, związane z wykresem małe twierdzenie jest dowodem, że drobne zamknięte właściwości mogą być testowane w deterministycznym czasie sześciennym, jeśli znamy listę wykluczonych nieletnich dla tej właściwości. Dlatego naturalne jest zastanawianie się, jak „niemożliwe” jest udowodnienie, że znaleziono wszystkich wykluczonych nieletnich dla danej „łatwej” (jak wyjaśniono w pytaniu) drobnej zamkniętej własności. Ponieważ jest to zadanie „nierównomierne”, nie jest dla mnie jasne, czy „niemożność” tego zadania w ogóle wiąże się z „trudnością” (tj. Odwrotną siłą matematyczną) udowodnienia samego twierdzenia o grafie mniejszym.

Ponieważ prosta wersja twierdzenia o drzewku Kruskala stawia dokładnie te same pytania, co twierdzenie o grafie mniejszym, odpowiedzi mogą skupić się na tym prostszym problemie, jeśli chcą. Właśnie użyłem twierdzenia o grafie mniejszym, ponieważ pytanie wydaje się w ten sposób bardziej naturalne. (Możliwe, że to pytanie mogłoby być bardziej odpowiednie dla MSE lub MSO, przynajmniej w odniesieniu do uzyskania określonej odpowiedzi. Ale motywacja tego pytania jest bardziej związana z TCS, więc postanowiłem zadać je tutaj).

Nie jestem pewien, czy zrozumiałem twoje pytanie, ale jeśli pytasz, jak trudno jest obliczyć zestaw przeszkód, możesz zainteresować się następującym http://www.jucs.org/doi?doi=10.3217/jucs- 003-11-1194, gdzie udowodniono, że nieobliczalność jest możliwa, nawet jeśli klasa grafu jest definiowalna przez MSOL. W niniejszym artykule http://www.sciencedirect.com/science/article/pii/S0012365X97830798?via%3Dihub obliczalność jest udowodniona, gdy klasa grafu jest podana przez gramatykę HR.