Fixed-parameter decidability: extending parameterized complexity analysis

DOI10.1002/MALQ.201500077MaRDI QIDQ2958220zbMATH OpenOpenAlexFDO

Authors Jouke Witteveen, Leen Torenvliet

Publication date 1 February 2017

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1002/malq.201500077

zbMATH Keywords

parameterized complexityalgorithmic randomness

Mathematics Subject Classification ID

Computational learning theory (68Q32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Computation Models for Parameterized Complexity
• scientific article; zbMATH DE number 512804
• On the space and circuit complexity of parameterized problems: classes and completeness
• Index sets and parametric reductions
• scientific article; zbMATH DE number 512844

Cites work

• scientific article; zbMATH DE number 3342830 (Why is no real title available?)
• scientific article; zbMATH DE number 3342831 (Why is no real title available?)
• A note on bi-immunity and \(p\)-closeness of \(p\)-cheatable sets in \(P\)/poly
• Algorithmic randomness and complexity.
• Classes of Recursively Enumerable Sets and Their Decision Problems
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
• Instance complexity
• Kolmogorov Complexity and Instance Complexity of Recursively Enumerable Sets
• Limiting recursion
• On degrees of unsolvability
• On miniaturized problems in parameterized complexity theory
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Random strings make hard instances
• Semirecursive Sets and Positive Reducibility
• Theory of semi-feasible algorithms
• Trial and error predicates and the solution to a problem of Mostowski
• Weakly computable real numbers

Cited in

(3)

• Decidability and complexity analysis by basic paramodulation
• scientific article; zbMATH DE number 7503138 (Why is no real title available?)
• scientific article; zbMATH DE number 512844 (Why is no real title available?)

This page was built for publication: Fixed-parameter decidability: extending parameterized complexity analysis

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