On reductions of NP sets to sparse sets

DOI10.1016/S0022-0000(05)80006-6MaRDI QIDQ1329162zbMATH OpenOpenAlexFDO

Authors Luc Longpré, S. Homer

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

Mathematics Subject Classification ID

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

Recommendations

• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• On polynomial time one-truth-table reducibility to a sparse set
• scientific article; zbMATH DE number 1318517

Cites work

• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• scientific article; zbMATH DE number 512798 (Why is no real title available?)
• Complexity Measures for Public-Key Cryptosystems
• On Restricting the Size of Oracles Compared with Restricting Access to Oracles
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Strong nondeterministic polynomial-time reducibilities
• Turing machines that take advice
• \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP

Cited in

(21)

• scientific article; zbMATH DE number 1318517 (Why is no real title available?)
• On the reducibility of sets inside NP to sets with low information content
• On sparseness and Turing reducibility over the reals
• On the existence of hard sparse sets under weak reductions
• Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
• scientific article; zbMATH DE number 1414313 (Why is no real title available?)
• Sparse sets, approximable sets, and parallel queries to NP
• Approximable sets
• On sets bounded truth-table reducible to $P$-selective sets
• Reductions to sets of low information content (extended abstract)
• The complexity of manipulative attacks in nearly single-peaked electorates
• scientific article; zbMATH DE number 4080915 (Why is no real title available?)
• On resource-bounded instance complexity
• Reducing the number of solutions of NP functions
• The complexity of grid coloring
• On some FPT problems without polynomial Turing compressions
• Learning Reductions to Sparse Sets
• On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
• Monotonous and randomized reductions to sparse sets
• Reductions between disjoint NP-pairs
• scientific article; zbMATH DE number 1107624 (Why is no real title available?)

This page was built for publication: On reductions of NP sets to sparse sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1329162)