Sparse parameterized problems

DOI10.1016/0168-0072(95)00069-0zbMath0863.03020OpenAlexW2001859438WikidataQ57360100 ScholiaQ57360100MaRDI QIDQ2564046

Michael R. Fellows, Marco Cesati

Publication date: 13 February 1997

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(95)00069-0

zbMATH Keywords

complexity theory for parametrized problemsMahaney's theorem for sparse sets

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Parameterized circuit complexity and the \(W\) hierarchy ⋮ Confronting intractability via parameters

Cites Work

• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• Relativizations of the P =? NP and Other Problems: Developments in Structural Complexity Theory
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item