Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
From MaRDI portal
Publication:3978778
DOI10.1137/0220030zbMath0741.68049OpenAlexW2039334189MaRDI QIDQ3978778
Mitsunori Ogiwara, Osamu Watanabe
Publication date: 25 June 1992
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0220030
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items (36)
Space-efficient recognition of sparse self-reducible languages ⋮ NP-hard sets are superterse unless NP is small ⋮ Sparse sets, approximable sets, and parallel queries to NP ⋮ Nonuniform lowness and strong nonuniform lowness ⋮ The Birth and Early Years of Parameterized Complexity ⋮ Geometric sets of low information content ⋮ Quasi-linear truth-table reductions to \(p\)-selective sets ⋮ Reductions between disjoint NP-pairs ⋮ Separating NE from Some Nonuniform Nondeterministic Complexity Classes ⋮ An observation on probability versus randomness with applications to complexity classes ⋮ Self-reducible sets of small density ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ Autoreducibility, mitoticity, and immunity ⋮ On complexity classes and algorithmically random languages ⋮ On lower bounds of the closeness between complexity classes ⋮ Unnamed Item ⋮ Upper bounds for the complexity of sparse and tally descriptions ⋮ Challenges to complexity shields that are supposed to protect elections against manipulation and control: a survey ⋮ Introduction to Autoreducibility and Mitoticity ⋮ Separating NE from some nonuniform nondeterministic complexity classes ⋮ The complexity of manipulative attacks in nearly single-peaked electorates ⋮ Cook versus Karp-Levin: Separating completeness notions if NP is not small ⋮ A note on P-selective sets and closeness ⋮ Sparse selfreducible sets and nonuniform lower bounds ⋮ Partial bi-immunity, scaled dimension, and NP-completeness ⋮ On the asymmetric complexity of the group-intersection problem ⋮ On sparse hard sets for counting classes ⋮ The fault tolerance of NP-hard problems ⋮ Reductions to sets of low information content ⋮ The Fault Tolerance of NP-Hard Problems ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ Monotonous and randomized reductions to sparse sets ⋮ Sparse hard sets for P: Resolution of a conjecture of Hartmanis ⋮ Resolution of Hartmanis' conjecture for NL-hard sparse sets ⋮ Sparse parameterized problems ⋮ Some structural properties of SAT
This page was built for publication: Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
