Nazwa podklasy „jednolicie wielomianowa” XP?

Załóżmy, że jest sparametryzowanym językiem w odniesieniu do jakiegoś alfabetu . -slice z jest , zestaw przypadkach w , które mają parametru . Klasa złożoności zawiera sparametryzowane języki takie jak dla każdego , prawdopodobnie z innym algorytmem i wielomianowym czasem działania związanym z każdym . Każdy język traktowany o stałych parametrach znajduje się w , a istnieją języki w $L$ $\Sigma$ $k$ $L$ $L_k = L \cap \{(x,k) \mid x \in \Sigma^{*}\}$ $L$ $k$ $\mathsf{XP}$ $L$ $L_k \in P$ $k$ $k$ $\mathsf{XP}$ $\mathsf{XP}$ których nie ma w ; to jest Propozycja 27.1.1 w podręczniku Downey & Fellows 2013. $\mathsf{FPT}$

Wydaje się jednak, że ma nietrywialną strukturę poza tym, ponieważ można rozwarstwiać tę klasę na podstawie tego, jak szybko rośnie stopień ograniczenia wielomianu z : dla stopień jest stały, podczas gdy dla może rosnąć dowolnie. Downey & Fellows nie wspomina nic o strukturze $\mathsf{XP}$ $k$ $\mathsf{FPT}$ $\mathsf{XP}$ $\mathsf{XP}$ poza Propozycją 27.1.1, a dyskusja w podręczniku Flum & Grohe 2006 nie jest dużo bardziej szczegółowa.

W związku z moim wcześniejszym pytaniem Granice wariantów zestawu niezależnego? czy istnieje nazwa dla podklasy z gdzie jeśli istnieje wielomian tak że o każdej instancji w można zdecydować najwyżej kroki? $\mathsf{Q}$ $\mathsf{XP}$ $L \in \mathsf{Q}$ $g_L$ $(x,k)$ $L$ $|x|^{g_L(k)}$

Innymi słowy, ta klasa dopuszcza tylko zamiast czas na dowolnej funkcji jak dla . $\mathsf{Q}$ $|x|^{\text{poly}(k)}$ $|x|^{g(k)}$ $g$ $\mathsf{XP}$

cc.complexity-theory reference-request parameterized-complexity András Salamon
źródło

To świetne pytanie! Tak naprawdę jestem bardzo zainteresowany podklasą, w której wielomian jest liniowy. To znaczy, Q pozwala tylko

| x |^{O (k)}

$\vert x \vert ^{O(k)}$

Michael Wehar

Odpowiedzi:

Nie sądzę, aby ta podklasa była badana w literaturze (i nadana jej nazwa). $\textsf{XP}$

Jednym z powodów, dla których badacze mogą unikać studiowania tej podklasy, jest to, że nie jest ona zamknięta w ramach obniżek fpt (a więc trzeba będzie poradzić sobie z „irytującym” nowym rodzajem redukcji). Wynika to z faktu, że redukcje fpt pozwalają na wysadzenie wartości parametru wielobiegunowo (o ile jest ograniczona jakąś funkcją obliczeniową starej wartości parametru). Aby uzyskać ograniczone pojęcie redukcji fpt, zgodnie z którymi twoja podklasa jest zamknięta, musisz dodać ograniczenie, że redukcje fpt wymagają ograniczenia nowej wartości parametru przez pewien wielomian starej wartości parametru. $\textsf{XP}$

Ronald de Haan
źródło

Redukcje, o których mówisz, zostały zbadane w kontekście kernlizaitonu pod nazwą „wielomianowe transformacje parametrów”, jednak muszą one działać w czasie wielomianowym.

daniello

Subiektywnie uważam, że nowy rodzaj redukcji może być dobry (niezbyt denerwujący). Zawsze byłem sceptycznie nastawiony do redukcji fpt, pozwalając na nieograniczenie

g (k)

$g(k)$

Michael Wehar

W literaturze widziałem dwa pojęcia liniowej redukcji fpt, które wymagają ograniczenia

g (k)

$g(k)$

Michael Wehar,