Self-reducible sets of small density

DOI10.1007/BF02090392zbMATH Open0722.68058OpenAlexW2039379116MaRDI QIDQ3210176FDOQ3210176

Authors: Antoni Lozano, Jacobo Torán 

Publication date: 1991

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02090392

Recommendations

• Sparse selfreducible sets and nonuniform lower bounds
• scientific article
• Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds
• Space-efficient recognition of sparse self-reducible languages
• Natural Self-Reducible Sets

zbMATH Keywords

sparse setslength decreasing self-reducibilityword decreasing self-reducibility

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Title not available (Why is that?)
• Polynomial-Time Bounded Truth-Table Reducibility of NP Sets to Sparse Sets
• On self-reducibility and weak P-selectivity
• A low and a high hierarchy within NP
• The polynomial-time hierarchy and sparse oracles
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• A Note on Sparse Complete Sets
• On Circuit-Size Complexity and the Low Hierarchy in NP
• Lower bounds for the low hierarchy
• Title not available (Why is that?)

Cited In (20)

• Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds
• \(p\)-selective self-reducible sets: a new characterization of P
• Upper bounds for the complexity of sparse and tally descriptions
• Small sets in dense pairs
• Sparse selfreducible sets and nonuniform lower bounds
• On sparse hard sets for counting classes
• Title not available (Why is that?)
• New collapse consequences of NP having small circuits
• Title not available (Why is that?)
• Weak mitoticity of bounded disjunctive and conjunctive truth-table autoreducible sets
• Title not available (Why is that?)
• Natural Self-Reducible Sets
• Easily Checked Generalized Self-Reducibility
• Self-reducibility
• A refinement of the low and high hierarchies
• Space-efficient recognition of sparse self-reducible languages
• Characterizations of some complexity classes between Θ2p and Δ2p
• Geometric sets of low information content
• Title not available (Why is that?)
• Complexity classes between $\Theta _k^P$ and $\Delta _k^P$

This page was built for publication: Self-reducible sets of small density

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