On reductions of NP sets to sparse sets
From MaRDI portal
Publication:1329162
DOI10.1016/S0022-0000(05)80006-6zbMath0806.68046OpenAlexW2066804259MaRDI QIDQ1329162
Publication date: 13 February 1995
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0022-0000(05)80006-6
Related Items (9)
On resource-bounded instance complexity ⋮ Reductions between disjoint NP-pairs ⋮ The complexity of grid coloring ⋮ The complexity of manipulative attacks in nearly single-peaked electorates ⋮ Reductions to sets of low information content ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ Monotonous and randomized reductions to sparse sets ⋮ Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets ⋮ On some FPT problems without polynomial Turing compressions
Cites Work
- Unnamed Item
- Unnamed Item
- Turing machines that take advice
- \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
- Strong nondeterministic polynomial-time reducibilities
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- On Restricting the Size of Oracles Compared with Restricting Access to Oracles
- Complexity Measures for Public-Key Cryptosystems
This page was built for publication: On reductions of NP sets to sparse sets
