Sparse selfreducible sets and nonuniform lower bounds

DOI10.1007/s00453-018-0439-0zbMath1412.68079MaRDI QIDQ1755786

Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin

Publication date: 11 January 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://ir.cwi.nl/pub/27793

zbMATH Keywords

computational complexity; sparseness; selfreducibility

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)