Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
For each reduction type \(r\), the concept of ``\(\leq^ P_ r\)- reducibility to sparse sets indicates a certain tractability notion. There are several types of polynomial time reductions \(r\): \(\leq^ P_ T\) (Turing reduction), \(\leq^ P_ m\) (many-one reduction), \(\leq^ P_{k-tt}\) (\(k\)-truth-table reduction), \(\leq^ P_{btt}\) ( bounded truth-table reduction), etc. It is known that: (i) a set has polynomial size circuits iff it is \(\leq^ P_ T\)- reducible to a sparse set, and (ii) if \(P\neq NP\) then no \(NP\)-complete set is \(\leq^ P_ m\)-reducible to a sparse set. The aim of this paper is to extend this last result to \(\leq^ P_{btt}\)-reducibility (which is more general than \(\leq^ P_ T\)- reducibility). It is proved that if \(P\neq NP\) then \(NP\) has a set which is not \(\leq^ P_{btt}\)-reducible to any sparse set. It is also mentioned that the same technique allows one to prove that several number-theoretic problems (such as a factorization problem) either are in \(P\) or are not \(\leq^ P_{btt}\)-reducible to any sparse set, i.e., either these problems are tractable or are ``hardly intractable.
- 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
- On bounded truth-table, conjunctive, and randomized reductions to sparse sets
- An observation on probability versus randomness with applications to complexity classes
- On f-sparse sets in NP-P
- 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
- On sets bounded truth-table reducible to P-selective sets
- 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
- Counting martingales for measure and dimension in complexity classes
- 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)