Computation Models for Parameterized Complexity

DOI10.1002/MALQ.19970430204MaRDI QIDQ4336699zbMATH OpenOpenAlexFDO

Authors Marco Cesati, Miriam Di Ianni

Publication date 14 May 1997

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/2108/260205

zbMATH Keywords

Turing machinesparameterized computational problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)

Recommendations

• scientific article; zbMATH DE number 1161563
• Complexity models for incremental computation
• Fundamentals of parameterized complexity
• Parameterized complexity: the main ideas and connections to practical computing
• scientific article; zbMATH DE number 1956210
• Parameterized Complexity and Logic
• Modified parameterized complexity theory
• scientific article; zbMATH DE number 1424025
• Parametrized complexity theory.

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• On the parameterized complexity of short computation and factorization

Cited in

(26)

• The Turing way to parameterized complexity
• On problems without polynomial kernels
• On the structure of parameterized problems in NP
• Relativization and interactive proof systems in parameterized complexity theory
• On the computational complexity of cost efficiency analysis models
• Modified parameterized complexity theory
• Machine characterizations for parameterized complexity classes beyond para-NP
• A Parameterized Halting Problem
• A parametric analysis of the state-explosion problem in model checking
• Computational complexity in non-Turing models of computation: the what, the why and the how
• Fixed Structure Complexity
• Fundamentals of parameterized complexity
• Computing the complexity for Schelling segregation models
• Polynomial-time versus recursive models
• Fixed-parameter decidability: extending parameterized complexity analysis
• scientific article; zbMATH DE number 2183396 (Why is no real title available?)
• Parameterized complexity: the main ideas and connections to practical computing
• R<scp>OMAN DOMINATION</scp>: a parameterized perspective†
• A parameterized halting problem, the linear time hierarchy, and the MRDP theorem
• A logic for PTIME and a parameterized halting problem
• Complexity of Ehrenfeucht models
• Machine-based methods in parameterized complexity theory
• A multi-parameter analysis of hard problems on deterministic finite automata
• On the efficiency of polynomial time approximation schemes
• On the space and circuit complexity of parameterized problems: classes and completeness
• Perfect Code is \(W[1]\)-complete

This page was built for publication: Computation Models for Parameterized Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4336699)