Showing 2001Show all
2 papers · 1 filter
cs.CC2001
Using the No-Search Easy-Hard Technique for Downward Collapse
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
The top part of the preceding figure [figure appears in actual paper] shows some classes from the (truth-table) bounded-query and boolean hierarchies. It is well-known that if eith…
cs.CC2001
P-Immune Sets with Holes Lack Self-Reducibility Properties
Lane A. Hemaspaandra, Harald Hempel
No P-immune set having exponential gaps is positive-Turing self-reducible.