scientific article; zbMATH DE number 1318517
From MaRDI portal
Publication:4256649
Recommendations
- Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
- Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- On polynomial time one-truth-table reducibility to a sparse set
- On Sets Truth-Table Reducible to Sparse Sets
- Distinguishing conjunctive and disjunctive reducibilities by sparse sets
- CONJUNCTIVE AND DISJUNCTIVE REDUCIBILITIES TO SPARSE AND TALLY SETS REVISITED
- On reductions of NP sets to sparse sets
- Circuit-size lower bounds and non-reducibility to sparse sets
Cited in
(19)- Strong and robustly strong polynomial-time reducibilities to sparse sets
- On polynomial time one-truth-table reducibility to a sparse set
- Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
- On reductions of NP sets to sparse sets
- Geometric sets of low information content
- On hard instances
- Distinguishing conjunctive and disjunctive reducibilities by sparse sets
- Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
- On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
- On Sparse Complete Sets
- Comparing Reductions to NP-Complete Sets
- On the existence of hard sparse sets under weak reductions
- Monotonous and randomized reductions to sparse sets
- Upper bounds for the complexity of sparse and tally descriptions
- On monotonous oracle machines
- Reductions to sets of low information content (extended abstract)
- On random reductions from sparse sets to tally sets
- Some consequences of non-uniform conditions on uniform classes
- Comparing reductions to NP-complete sets
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4256649)
