Elementarne granice parametru w ciągliwości parametrów stałych?

W definicji (silnej) ciągliwości parametrów stałych ustalony czas jest wyrażeniem postaci gdzie instancja wejściowa to z parametrem , jest wielomianem, a jest funkcją obliczalną .

f (k) . p (| x |),

$f(k).p(|x|),$

(x, k)

$(x,k)$

k

$k$

p

$p$

f

$f$

Możliwe jest zastąpienie wymogu obliczeniowego dla innymi klasami funkcji, o ile pojęcie redukcji jest podobnie ograniczone. (Na przykład Flum i Grohe opisują rodziny wykładnicze i podwykładnicze w rozdziałach 15–16 swojego podręcznika, wraz z powiązanymi z nimi ograniczeniami erf i poddańców.) $f$

Czy ktoś badał rodzinę funkcji elementarnych dla parametru związanego ? $f$

Funkcja elementarna może być ograniczona powyżej stałą wieżą wykładniczą, więc ta klasa jest zamknięta w składzie. Wzrost parametru w redukcji musi być następnie ograniczony również przez funkcję elementarną.

Istnieją interesujące problemy z teorii automatów, które można ustalić w oparciu o parametry stałe, ale gdzie parametr jest nieelementowy (chyba że P = NP, patrz Frick i Grohe, doi: 10.1016 / j.apal.2004.01.007 ). Zastanawiam się, czy ktokolwiek spojrzał na możliwe do rozwiązania problemy o ustalonych parametrach, które wykluczają ustalone wartości parametru prowadzące do takich stałych „galaktycznych” (używając terminu Richarda Liptona i Kena Regana). Dzikie spekulacje, takie ograniczenie może mieć użyteczne powiązania z teorią modeli skończonych, na przykład charakteryzuje się fragmentem monadycznej logiki drugiego rzędu, który nie prowadzi do nieelementowych stałych, które mogą wynikać z zastosowania twierdzenia Courcelle'a do fragmentu z nieograniczona zmiana kwantyfikatora.

cc.complexity-theory reference-request fixed-parameter-tractable

— András Salamon
źródło

Jaki jest przykład „interesujących problemów z teorii automatów, które są możliwe do ustalenia ze stałymi parametrami, ale w których parametr nie jest elementarny”.

— Suresh Venkat

N P \neq P

$NP\ne P$

W swojej rozprawie doktorskiej „ Modi ﬁ zierte parametrische Komplexitatstheorie ” Mark Weyer rozważył między innymi hierarchie w ramach FPT dotyczące funkcji f i redukcji między nimi. Rzeczywiście, on również powiązał te podhierarchie do fragmentów FO i MSO: Rozdział 6 dotyczy zasadniczo relacji między FO / MSO (liczba alternatywnych kwantyfikatorów wzorów) a funkcją f (w) w twierdzeniu Courcelle'a (w szerokość). Rozważał zarówno górną, jak i dolną granicę, a stosując wspomniane ramy redukcji między niektórymi hierarchiami w ramach FPT, był w stanie podać dość ścisłe granice. Egzaminatorami pracy byli Flum i Grohe.

Niestety praca jest w języku niemieckim i nie wiem, czy materiał jego pracy został opublikowany w angielskim czasopiśmie. Dlatego jestem świadomy, że mogą one mieć dla ciebie ograniczone zastosowanie, ale mimo to zawarte w nich odniesienia mogą być dobrym punktem wyjścia.

— Alexander Langer
źródło

Dzięki, nie pomyślałem o sprawdzeniu tez. Wygląda to na bardzo istotne dla wspomnianych aplikacji. Prawdopodobnie czegoś mi brakuje, ale poza krótką wzmianką na stronie 69 granice parametrów elementarnych nie wydają się interesujące dla Weyera.

— András Salamon,

E_{t}

$\mathcal E_t$

{Q E}_{t}

$\mathcal{QE}_t$

{P E}_{t}

$\mathcal{PE}_t$

t

$t$

e x p^{t} (\cdot)

$exp^t(\cdot)$

— Alexander Langer

W przypadku granic elementarnych wystarczy wziąć pod uwagę sumę wszystkich funkcji wykładniczych. Wspomina o tym Weyer na stronie 69 swojej pracy, ale wydaje się, że problem ten nie jest dalej rozpatrywany.

— András Salamon,