Sparse selfreducible sets and nonuniform lower bounds

DOI10.1007/s00453-018-0439-0zbMath1412.68079OpenAlexW2809558868MaRDI 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 complexitysparsenessselfreducibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On self-reducibility and weak P-selectivity
• Relativized circuit complexity
• Quasi-linear truth-table reductions to \(p\)-selective sets
• Separating classes in the exponential-time hierarchy from classes in PH
• \(p\)-selective self-reducible sets: a new characterization of P
• Approximable sets
• Pseudorandomness for approximate counting and sampling
• Self-reducible sets of small density
• On Circuit-Size Complexity and the Low Hierarchy in NP
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
• Analogues of semirecursive sets and effective reducibilities to the study of NP complexity
• Polynomial-Time Membership Comparable Sets
• Mathematical Foundations of Computer Science 2005

This page was built for publication: Sparse selfreducible sets and nonuniform lower bounds