Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets

Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

On Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
On polynomial time one-truth-table reducibility to a sparse set
Two Results on Polynomial Time Truth-Table Reductions to Sparse Sets
On Sets Truth-Table Reducible to Sparse Sets

Cited in

(52)

On polynomial time one-truth-table reducibility to a sparse set
On sparse hard sets for counting classes
Deterministic and randomized bounded truth-table reductions of P, NL, and L to sparse sets
Sparse hard sets for P: Resolution of a conjecture of Hartmanis
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
Resolution of Hartmanis' conjecture for NL-hard sparse sets
Some structural properties of SAT
Sparse selfreducible sets and nonuniform lower bounds
On the reducibility of sets inside NP to sets with low information content
Nonuniform lowness and strong nonuniform lowness
Reductions between disjoint NP-pairs
Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey
Partial bi-immunity, scaled dimension, and NP-completeness
Sparse parameterized problems
NP-hard sets are superterse unless NP is small
The birth and early years of parameterized complexity
Sparse sets, approximable sets, and parallel queries to NP
Introduction to autoreducibility and mitoticity
Self-reducible sets of small density
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 Certain Polynomial-Time Truth-Table Reducibilities of Complete Sets to Sparse Sets
The Fault Tolerance of NP-Hard Problems
scientific article; zbMATH DE number 4075037 (Why is no real title available?)
scientific article; zbMATH DE number 4080915 (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
Relating Equivalence and Reducibility to Sparse Sets
On lower bounds of the closeness between complexity classes
scientific article; zbMATH DE number 1318517 (Why is no real title available?)
An observation on probability versus randomness with applications to complexity classes
scientific article; zbMATH DE number 1107624 (Why is no real title available?)
On sets bounded truth-table reducible to P-selective sets
Monotonous and randomized reductions to sparse sets
scientific article; zbMATH DE number 2097995 (Why is no real title available?)
Upper bounds for the complexity of sparse and tally descriptions
The complexity of manipulative attacks in nearly single-peaked electorates
scientific article; zbMATH DE number 1414313 (Why is no real title available?)
On complexity classes and algorithmically random languages (extended abstract)
Reductions to sets of low information content (extended abstract)
Separating NE from Some Nonuniform Nondeterministic Complexity Classes
The fault tolerance of NP-hard problems
scientific article; zbMATH DE number 7650083 (Why is no real title available?)
Separating NE from some nonuniform nondeterministic complexity classes
Splitting NP-complete sets infinitely
Cook versus Karp-Levin: Separating completeness notions if NP is not small
A note on P-selective sets and closeness
Autoreducibility, mitoticity, and immunity
On the asymmetric complexity of the group-intersection problem

This page was built for publication: Polynomial-Time Bounded Truth-Table Reducibility 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 Q3978778)