Strong and robustly strong polynomial-time reducibilities to sparse sets

DOI10.1016/0304-3975(91)90070-IzbMath0735.68032OpenAlexW2523974492MaRDI QIDQ1177170

José L. Balcázar, Ricard Gavaldà

Publication date: 26 June 1992

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90070-i

zbMATH Keywords

nondeterminismrobust reducibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (5)

Locating \(P\)/poly optimally in the extended low hierarchy ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Dot operators ⋮ AM\(_{\text{exp}}\nsubseteq (\text{NP} \cap \text{coNP})\)/poly

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some consequences of non-uniform conditions on uniform classes
• On small generators
• A low and a high hierarchy within NP
• Strong nondeterministic polynomial-time reducibilities
• Qualitative relativizations of complexity classes
• On sparse sets in NP-P
• The polynomial-time hierarchy
• Sets with small generalized Kolmogorov complexity
• The polynomial-time hierarchy and sparse oracles
• Quantitative Relativizations of Complexity Classes
• Computational Complexity of Probabilistic Turing Machines

This page was built for publication: Strong and robustly strong polynomial-time reducibilities to sparse sets