Twierdzenie Courcelle'a stwierdza, że każdą właściwość grafu definiowaną w monadycznej logice drugiego rzędu można rozstrzygać w czasie liniowym na wykresach ograniczonej szerokości . Jest to jedno z najbardziej znanych algorytmicznych meta-twierdzeń.
Zmotywowany twierdzeniem Courcelle, wysunąłem następujące przypuszczenie:
Przypuszczenie : Niech będzie dowolną właściwością definiowaną przez MSO. Jeśli ψ można rozwiązać w czasie wielomianowym na grafach płaskich, to ψ można rozwiązać w czasie wielomianowym na wszystkich klasach mniej istotnych grafów.
Chcę wiedzieć, czy powyższa hipoteza jest oczywiście fałszywa, tj. Czy istnieje właściwość definiowana przez MSO, która jest rozwiązywalna w czasie wielomianowym na grafach płaskich, ale trudna NP na pewnej klasie grafów wolnych od drobnych?
Taka jest motywacja mojego wcześniejszego pytania : czy są jakieś problemy, które można rozwiązać wielomianowo na wykresach rodzaju g, ale NP-trudne na wykresach rodzaju> g.
źródło