Name für "einheitlich polynomielle" Unterklasse von XP?

10

Angenommen, ist eine parametrisierte Sprache in Bezug auf ein Alphabet . Die Scheibe von ist , die Menge von Instanzen in , die den Parameter . Die Komplexitätsklasse enthält die parametrisierte Sprachen , so dass für jedes , möglicherweise mit einem anderen Algorithmus und Polynom Laufzeit für jeden gebunden . Jede Sprache mit festen Parametern befindet sich in , und es gibt Sprachen inLΣkLLk=L{(x,k)xΣ}LkXPLLkPkkXPXPdas sind nicht in ; Dies ist Proposition 27.1.1 im Lehrbuch von Downey & Fellows 2013.FPT

Allerdings scheint darüber hinaus nicht - triviale Struktur zu haben, da man diese Klasse stratifizieren kann je nachdem , wie schnell sich der Grad des Begrenzungs Polynom wächst mit : für der Grad konstant ist , während für kann beliebig wachsen. Downey & Fellows erwähnt nichts über die Struktur von jenseits von Proposition 27.1.1, und die Diskussion im Lehrbuch von Flum & Grohe 2006 ist nicht viel detaillierter.XPkFPTXPXP

In Anlehnung an meine frühere Frage Grenzen von Varianten von Independent Set? es einen Namen für die Unterklasse von wobei wenn es ein Polynom so dass jede Instanz in höchstens entschieden werden kann Schritte?QXPLQgL(x,k)L|x|gL(k)

Mit anderen Worten, diese Klasse erlaubt nur bis zu Zeit anstelle von Zeit für eine beliebige Funktion wie für .Q|x|poly(k)|x|g(k)gXP

András Salamon
quelle
Das ist eine gute Frage! Ich interessiere mich eigentlich sehr für die Unterklasse, in der das Polynom linear ist. Das heißt, Q erlaubt nur bis zu . |x|O(k)
Michael Wehar

Antworten:

6

Ich glaube nicht, dass diese Unterklasse von in der Literatur untersucht wurde (und einen Namen erhielt).XP

Ein Grund, warum Forscher sich davor scheuen könnten, diese Unterklasse zu studieren, ist, dass sie nicht unter fpt-Reduktionen geschlossen ist (und man sich daher mit einer "nervigen" neuen Art von Reduktionen befassen müsste). Dies liegt daran, dass fpt-Reduktionen es ermöglichen, dass der Parameterwert superpolynomisch explodiert (solange er durch eine berechenbare Funktion des alten Parameterwerts begrenzt ist). Um eine eingeschränkte Vorstellung von fpt-Reduktionen zu erhalten, unter denen Ihre Unterklasse von geschlossen ist, müssten Sie die Einschränkung hinzufügen, dass für fpt-Reduktionen der neue Parameterwert durch ein Polynom des alten Parameterwerts begrenzt werden muss.XP

Ronald de Haan
quelle
1
Die Reduktionen, über die Sie sprechen, wurden im Rahmen der Kernlizaiton unter dem Namen "Polynomparametertransformationen" untersucht, diese müssen jedoch in Polynomzeit ablaufen.
Daniello
Ich denke subjektiv, dass eine neue Art der Reduzierung gut sein könnte (nicht sehr ärgerlich). Ich war immer skeptisch gegenüber fpt-Reduktionen, die es ermöglichen, dass unbegrenzt ist. g(k)
Michael Wehar
Ich habe in der Literatur zwei Begriffe der linearen fpt-Reduktion gesehen, bei denen begrenzt werden muss. g(k)
Michael Wehar