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

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

zbMATH Keywords

sparse setsBerman-Hartmanis conjecturebounded truth-table reductionpolynomial-time hard sets

Mathematics Subject Classification ID

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