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$

Odpowiedzi:

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,