Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
23. The W-Hierarchy
verfasst von : Rodney G. Downey, Michael R. Fellows
Erschienen in: Fundamentals of Parameterized Complexity
Verlag: Springer London
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
We introduce the W-hierarchy of parameterized complexity classes in the tower
Presumably, all the inclusions are proper. The W-Hierarchy gives us means of comparing parameterized problems that are presumably not in FPT, with respect to the “strength” of their parameterized intractability. The key idea is to use a form of circuit depth in defining the classes. We discuss the remarkable fact that “almost all” (or at least a very large percentage) of the natural parameterized problems investigated to date are precisely complete for one of the first three classes in this hierarchy, a remarkable empirical finding that supports the definitional framework. We also introduce a natural generalization called the W
∗[t]-hierarchy, about which only a little (but for exact parameterized complexity analysis, a useful little), is so far known.
$$\mathrm{FPT}=W[0] \subseteq W[1] \subseteq W[2] \subseteq\cdots \subseteq W[t]\subseteq \cdots\subseteq W[\mathrm{SAT}]\subseteq \cdots\subseteq W[\mathrm{P}]. $$