P-immune sets with holes lack self-reducibility properties.

DOI10.1016/S0304-3975(02)00576-5zbMath1044.68068MaRDI QIDQ1401340

Hemaspaandra, Lane A., Harald Hempel

Publication date: 17 August 2003

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

zbMATH Keywords

Computational complexitySelf-reducibilityImmunityGaps

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Query-monotonic Turing reductions ⋮ The Power of Self-Reducibility: Selectivity, Information, and Approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A result relating disjunctive self-reducibility to P-immunity
• Reductions on NP and p-selective sets
• A comparison of polynomial time reducibilities
• Computation times of NP sets of different densities
• Self-reducibility
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Completeness, Approximation and Density
• ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS
• Easily Checked Generalized Self-Reducibility
• Strong self-reducibility precludes strong immunity

This page was built for publication: P-immune sets with holes lack self-reducibility properties.