Optimal advice
From MaRDI portal
Publication:672755
DOI10.1016/0304-3975(95)00076-3zbMath0872.68042OpenAlexW2914018422MaRDI QIDQ672755
Leen Torenvliet, Hemaspaandra, Lane A.
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(95)00076-3
Related Items
Some connections between bounded query classes and non-uniform complexity., ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES, On sets Turing reducible to p-selective sets, On the reducibility of sets inside NP to sets with low information content
Cites Work
- P-selectivity: Intersections and indices
- On sets Turing reducible to p-selective sets
- Turing machines that take advice
- On self-reducibility and weak P-selectivity
- Qualitative relativizations of complexity classes
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- \(p\)-Selective sets and reducing search to decision vs. self-reducibility
- Circuit-size lower bounds and non-reducibility to sparse sets
- Quantitative Relativizations of Complexity Classes
- Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
- PSPACE SURVIVES CONSTANT-WIDTH BOTTLENECKS
- On the Structure of Polynomial Time Reducibility
- P-selective sets, tally languages, and the behavior of polynomial time reducibilities onNP
- Complexity-Restricted Advice Functions
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
