Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets

Recommendations

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

Cited in

(31)

Polynomial terse sets
On polynomial time one-truth-table reducibility to a sparse set
On polynomial-time Turing and many-one completeness in PSPACE
On sparse hard sets for counting classes
Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
On reductions of NP sets to sparse sets
Space-efficient recognition of sparse self-reducible languages
Geometric sets of low information content
Quasi-linear truth-table reductions to \(p\)-selective sets
Sparse sets, approximable sets, and parallel queries to NP
On polynomial-time truth-table reducibility of intractable sets to P-selective sets
On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
On Sparse Complete Sets
scientific article; zbMATH DE number 4079403 (Why is no real title available?)
scientific article; zbMATH DE number 4081538 (Why is no real title available?)
On Sets Truth-Table Reducible to Sparse Sets
Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
Relating Equivalence and Reducibility to Sparse Sets
scientific article; zbMATH DE number 1304328 (Why is no real title available?)
scientific article; zbMATH DE number 1318517 (Why is no real title available?)
On the existence of hard sparse sets under weak reductions
Monotonous and randomized reductions to sparse sets
scientific article; zbMATH DE number 2097995 (Why is no real title available?)
SPARSE Reduces Conjunctively to TALLY
With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets
On the power of parity polynomial time
Reductions to sets of low information content (extended abstract)
On the power of parity polynomial time
Sparse NP-complete problems over the reals with addition
Some consequences of non-uniform conditions on uniform classes
\(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP

This page was built for publication: Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets

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