On reductions of NP sets to sparse sets

DOI10.1016/S0022-0000(05)80006-6zbMATH Open0806.68046OpenAlexW2066804259MaRDI QIDQ1329162FDOQ1329162

S. Homer, Luc Longpré

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (19)

• Title not available (Why is that?)
• On the reducibility of sets inside NP to sets with low information content
• Reductions to sets of low information content
• On sparseness and Turing reducibility over the reals
• Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
• Title not available (Why is that?)
• Approximable sets
• On sets bounded truth-table reducible to $P$-selective sets
• The complexity of manipulative attacks in nearly single-peaked electorates
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)