On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Analysis of algorithms and problem complexity (68Q25)

Recommendations

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

Cited in

(51)

Polynomial terse sets
Notes on polynomial levelability
On polynomial time one-truth-table reducibility to a sparse set
On polynomial-time Turing and many-one completeness in PSPACE
Polynomial-time compression
On sparse hard sets for counting classes
On 1-truth-table-hard languages
On symmetric differences of NP-hard sets with weakly P-selective 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
Distinguishing conjunctive and disjunctive reducibilities by sparse sets
Hard sets are hard to find
Sparse sets, approximable sets, and parallel queries to NP
On intractability of the classUP
On polynomial-time truth-table reducibility of intractable sets to P-selective sets
Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
On Sparse Complete Sets
Schnorr trivial sets and truth-table reducibility
The Fault Tolerance of NP-Hard Problems
scientific article; zbMATH DE number 4081538 (Why is no real title available?)
On Sets Truth-Table Reducible to Sparse Sets
scientific article; zbMATH DE number 4100610 (Why is no real title available?)
Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
Relating Equivalence and Reducibility to Sparse Sets
On lower bounds of the closeness between complexity classes
Genericity, Randomness, and Polynomial-Time Approximations
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 optimal polynomial time approximations: p-levelability vs. -levelability
Monotonous and randomized reductions to sparse sets
Complete sets and closeness to complexity classes
scientific article; zbMATH DE number 2097995 (Why is no real title available?)
With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets
On sparseness and Turing reducibility over the reals
On the power of parity polynomial time
E-complete sets do not have optimal polynomial time approximations
Reductions to sets of low information content (extended abstract)
Separating NE from Some Nonuniform Nondeterministic Complexity Classes
The fault tolerance of NP-hard problems
On the power of parity polynomial time
The strong exponential hierarchy collapses
Sparse NP-complete problems over the reals with addition
Separating NE from some nonuniform nondeterministic complexity classes
Reducibility classes of P-selective sets
A note on P-selective sets and closeness
Cook reducibility is faster than Karp reducibility in NP
Some consequences of non-uniform conditions on uniform classes
Nonuniform proof systems: A new framework to describe nonuniform and probabilistic complexity classes
\(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP

This page was built for publication: On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets

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