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

DOI10.1016/S0304-3975(02)00576-5MaRDI QIDQ1401340zbMATH OpenFDO

Authors Lane A. Hemaspaandra, Harald Hempel

Publication date 17 August 2003

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

Full work available at URL https://doi.org/10.1016/S0304-3975(02)00576-5

zbMATH Keywords

Computational complexityGapsImmunitySelf-reducibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• A comparison of polynomial time reducibilities
• A result relating disjunctive self-reducibility to P-immunity
• Completeness, Approximation and Density
• Computation times of NP sets of different densities
• Easily Checked Generalized Self-Reducibility
• scientific article; zbMATH DE number 4179363 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 719756 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• ON THE LIMITATIONS OF LOCALLY ROBUST POSITIVE REDUCTIONS
• Reductions on NP and p-selective sets
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Self-reducibility
• Strong self-reducibility precludes strong immunity

Cited in

(2)

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

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

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