An Isomorphism Between Subexponential and Parameterized Complexity Theory
From MaRDI portal
Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
Recommendations
- Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping
- Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping
- On miniaturized problems in parameterized complexity theory
- scientific article; zbMATH DE number 749922
- scientific article; zbMATH DE number 512804
Cited in
(14)- AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly
- On the existence of subexponential parameterized algorithms
- Parameterized random complexity
- A basic parameterized complexity primer
- Parameterized complexity and subexponential-time computability
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- Subexponential Time and Fixed-Parameter Tractability: Exploiting the Miniaturization Mapping
- Subexponential Time and Fixed-parameter Tractability: Exploiting the Miniaturization Mapping
- 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
- Baby PIH: Parameterized inapproximability of min CSP
- Parameterized inapproximability hypothesis under ETH
- Parameterized and subexponential-time complexity of satisfiability problems and applications
This page was built for publication: An Isomorphism Between Subexponential and Parameterized Complexity Theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3519395)
