Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Fixed Structure Complexity
verfasst von : Yonatan Aumann, Yair Dombb
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
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
We consider a non-standard parametrization, where, for problems consisting of a combinatorial structure and a number, we parameterize by the combinatorial structure, rather than by the number. For example, in the
Short-Nondeterministic-Halt
problem, which is to determine if a nondeterministic machine
M
accepts the empty string in
t
steps, we parameterize by |
M
|, rather than
t
. We call such parametrization
fixed structure parametrization
. Fixed structure parametrization not only provides a new set of parameterized problems, but also results in problems that do not seem to fall within the classical parameterized complexity classes. In this paper we take the first steps in understanding these problems. We define fixed structure analogues of various classical problems, including graph problems, and provide complexity, hardness and equivalence results.