Sparse selfreducible sets and nonuniform lower bounds
From MaRDI portal
Publication:1755786
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
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.)
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