8 papers · 1 filter
Translating Equality Downwards
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
Downward translation of equality refers to cases where a collapse of some pair of complexity classes would induce a collapse of some other pair of complexity classes that (a priori…
Query Order and the Polynomial Hierarchy
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] initiated the field of query order, which studies the ways in which computational power is affected by the order in which informa…
A Downward Collapse within the Polynomial Hierarchy
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
Downward collapse (a.k.a. upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downwar…
Self-Specifying Machines
Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung
We study the computational power of machines that specify their own acceptance types, and show that they accept exactly the languages that $\manyonesharp$-reduce to NP sets. A natu…
An Introduction to Query Order
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] raised the following questions: If one is allowed one question to each of two different information sources, does the order in wh…
R_{1-tt}^{SN}(NP) Distinguishes Robust Many-One and Turing Completeness
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel
Do complexity classes have many-one complete sets if and only if they have Turing-complete sets? We prove that there is a relativized world in which a relatively natural complexity…