An Isomorphism Between Subexponential and Parameterized Complexity Theory

DOI10.1137/070687153zbMath1154.03020OpenAlexW2006337932MaRDI QIDQ3519395

Yijia Chen, Martin Grohe

Publication date: 14 August 2008

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/070687153

zbMATH Keywords

parameterized complexitysubexponential timeexponential time hypothesisexponential time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (8)

A Basic Parameterized Complexity Primer ⋮ Parameterized Complexity and Subexponential-Time Computability ⋮ Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications ⋮ Parameterized and subexponential-time complexity of satisfiability problems and applications ⋮ Parameterized random complexity ⋮ Confronting intractability via parameters ⋮ Refining complexity analyses in planning by exploiting the exponential time hypothesis ⋮ An initial study of time complexity in infinite-domain constraint satisfaction

This page was built for publication: An Isomorphism Between Subexponential and Parameterized Complexity Theory