Fixed Structure Complexity

DOI10.1007/978-3-540-79723-4_5MaRDI QIDQ3503576zbMATH OpenOpenAlexFDO

Authors Yonatan Aumann, Yair Dombb

Publication date 5 June 2008

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-79723-4_5

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) General topics of discrete mathematics in relation to computer science (68R01)

Recommendations

• Computation Models for Parameterized Complexity
• On the structure of parameterized problems in NP
• Machine-based methods in parameterized complexity theory
• A Parameterized Halting Problem
• scientific article; zbMATH DE number 806748

Cites work

• Computation Models for Parameterized Complexity
• scientific article; zbMATH DE number 3727583 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 1550912 (Why is no real title available?)
• scientific article; zbMATH DE number 1775632 (Why is no real title available?)
• The undecidability of the domino problem
• When is the evaluation of conjunctive queries tractable?

Cited in

(3)

• A Parameterized Halting Problem
• A logic for PTIME and a parameterized halting problem
• A parameterized halting problem, _0 truth and the MRDP theorem

This page was built for publication: Fixed Structure Complexity

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