Elementargrenzen für Parameter in der Traktierbarkeit von Festparametern?

In der Definition der (starken) Traktierbarkeit fester Parameter ist die ein Ausdruck der Form wobei die mit dem Parameter ,

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

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

(x, k)

$(x,k)$

k

$k$

p

$p$ ist Polynom und

ist eine berechenbare Funktion.

f

$f$

Es ist möglich, die Berechenbarkeitsanforderung für durch andere Funktionsklassen zu ersetzen , solange der Begriff der Reduktion ähnlich eingeschränkt ist. (Zum Beispiel decken Flum und Grohe exponentielle und subexponentielle Familien in den Kapiteln 15–16 ihres Lehrbuchs ab, mit den dazugehörigen Reduktionen von erf und serf.) $f$

Hat jemand die Familie der Elementarfunktionen für den Parameter ? $f$

Eine Elementarfunktion kann oben durch einen festen Turm von Exponentialen begrenzt werden, so dass diese Klasse unter Komposition geschlossen ist. Das Wachstum des Parameters in einer Reduktion muss dann auch oben durch eine Elementarfunktion begrenzt werden.

Es gibt interessante Probleme aus der Automatentheorie, die mit festen Parametern verfolgt werden können, deren Parameter jedoch nicht elementar sind (es sei denn, P = NP, siehe Frick und Grohe, doi: 10.1016 / j.apal.2004.01.007 ). Ich frage mich, ob sich jemand mit den Problemen befasst hat, bei denen es sich um Probleme mit festen Parametern handelt, bei denen feste Parameterwerte ausgeschlossen sind, die zu solchen "galaktischen" Konstanten führen (um den Begriff von Richard Lipton und Ken Regan zu verwenden). Wenn man wild spekuliert, könnte eine solche Einschränkung nützliche Verbindungen mit der Finite-Modell-Theorie haben, z. B. durch ein Fragment monadischer Logik zweiter Ordnung gekennzeichnet sein, das nicht zu den nicht-elementaren Konstanten führt, die sich aus der Anwendung des Courcelle-Theorems auf ein Fragment mit ergeben können unbegrenzte Quantifiziererwechsel.

cc.complexity-theory reference-request fixed-parameter-tractable András Salamon
quelle

Was ist ein Beispiel für "interessante Probleme aus der Automatentheorie, die mit festen Parametern verfolgt werden können, bei denen die Parametergrenze jedoch nicht elementar ist."

Suresh Venkat

N P \neq P

$NP\ne P$

Antworten:

Mark Weyer hat in seiner Dissertation " Modi ﬁ zierte parametrische Komplexitatstheorie " unter anderem Hierarchien innerhalb der FPT hinsichtlich der Funktion f und deren Reduktionen untersucht. Er hat diese Unterhierarchien auch tatsächlich mit Fragmenten von FO und MSO in Beziehung gesetzt: In Kapitel 6 geht es im Wesentlichen um die Beziehung zwischen FO / MSO (Anzahl der Quantifikatorwechsel der Formeln) und der Funktion f (w) in Courcelles Theorem (w being) die Baumbreite). Er berücksichtigte sowohl obere als auch untere Schranken und konnte unter Verwendung des oben erwähnten Reduktionsrahmens zwischen bestimmten Hierarchien innerhalb der FPT ziemlich enge Schranken festlegen. Die Prüfer der Arbeit waren Flum und Grohe.

Leider ist die Dissertation in deutscher Sprache verfasst, und mir ist nicht bekannt, ob das Material seiner Dissertation in einer englischen Zeitschrift veröffentlicht wurde. Mir ist daher bewusst, dass sie für Sie möglicherweise von begrenztem Nutzen sind, die darin enthaltenen Verweise jedoch möglicherweise ein guter Ausgangspunkt sind.

Alexander Langer
quelle

Danke, hätte nicht gedacht, diese zu überprüfen. Dies scheint für die von mir erwähnten Anwendungen sehr relevant zu sein. Ich vermisse wahrscheinlich etwas, aber abgesehen von einer kurzen Erwähnung auf Seite 69 scheinen elementare Parametergrenzen für Weyer nicht von Interesse zu sein.

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

Für Elementargrenzen genügt es, nur die Vereinigung aller Exponentialfunktionen zu betrachten. Dies wird von Weyer auf Seite 69 seiner Dissertation erwähnt, aber das Thema scheint nicht weiter behandelt zu werden.

András Salamon